Count Number of Teams - Leetcode 1395 - Python

[@freecourseplatformenglish2829]

Starting from middle is very cleaver pattern I saw it in few other problems like Longest Palindromic Substring (LPS). Thanks for reminding this approach.

[@sourabhgurav6665]

I first solved it by brute force, and it did work, but TLE. Later, when I came back here for a solution, within 6 minutes of your video, I knew how to solve it. Thanks for the tricks. Love your content.

[@CheezePie]

This is such a clever approach.. I was thinking along the lines of subsequence and recursion

[@jad_c]

im getting cooked

[@jeezluiz4972]

I feel you brother there's no way anyone comes up with solutions for these types of problems in 20-30 minutes

[@itsjustramblings]

It's not just you. These questions are deliberate to filter those who haven't slogged through leetcode because most companies don't have recruiters or HR anymore and Hiring Manager's don't have time to interview everyone who are selected so the first step is always such hard leetcode questions.

[@inowatchvideos]

I enjoy watching these. That trick is neat. I am bad at dynamic programming, ug. My idea was to generate a list of all pairs, then iterate through the pairs and see what third index satisfy the criteria. Eww.

[@jamestwosheep]

Daaang! I got as far as to think about the middle value, but for some reason just could not take it that last step to the solution. Thank you so much for your explanation!

[@crekso398]

i was solving it by bruteforce three pointer approach . this first solution is really clever . thanks so much

[@rajdeepguha734]

One I got the approach, it felt so easy... But the approach was lovely...kudos to you

[@psydook]

thanks for multiple approaches !!

[@AnkitaNallana]

Bottom up solution is pure evil. Top down is still a lot more intuitive!! The first solution is was so good, omg!

[@hithambasheir3283]

Thought about dp initially, came here to get the intuition and came up with this def numTeams(self, rating: List[int]) -> int: res = 0 for mid in range(1, len(rating) - 1): left_smlr, right_larger = 0, 0 left_larger, right_smlr = 0, 0 for i in range(mid): if rating[i] < rating[mid]: left_smlr += 1 else: left_larger += 1 for i in range(mid + 1, len(rating)): if rating[i] < rating[mid]: right_smlr += 1 else: right_larger += 1 res += left_smlr * right_larger res += left_larger * right_smlr return res

[@ParodyCSEDept]

How on earth did I miss this approach!

[@rahulsbhatt]

I liked the first solution, its very concise and clever!

[@6116_GAURAVKUMAR]

Very nice method

[@gamania0258]

Amazing approach ....

[@SLASH-yv8uz]

i have succesfully failed a coding test..but im not going to stoppp!!!!!!

[@pastori2672]

i got my 2024 200 day badge 🥳 idk why its 11 days late tho

[@aadil4236]

Why didn't I think that before!! I was banging my head with DP. Time limit exceed on n^2 time/space solution. But this solution, wow! so clever. 3:53 Thank you for the hint. I was able to figure it out my self after this without looking at the solution. Thank you.

[@aadil4236]

Why didn't I think of it? It was so simple.

[@plinygg]

was waiting for this 😃😃

[@IK-xk7ex]

Thank you, I was pretty close to greedy solution, but I couldn't code it and find a patter because I don't own technical of 2 separate loops :/. I tried to iterate it in one loop instead of applying 2 loops

[@greatfate]

Personally the only thing that came to my mind was the O(nlogn) approach, probably coz C++ conveniently has a built in self-balancing BST container (std::set), which always comes in handy.

[@finemechanic]

With std::set you will need linear time to count elements smaller or larger than given. So overall time appears to be O(n^2).

[@greatfate]

@@finemechanic idk why my comment got auto deleted (mby coz of link), but this isn't true. I only need to add elements and remove them at most twice (from the two sets I'm maintaining) here is the full code (sending link might get it auto deleted again): int numTeams(vector& rating) { set left(rating.begin(), rating.end() - 2); set right = {rating.back()}; int cnt = 0; for (int j = rating.size() - 2; j > 0; j--) { left.erase(rating[j]); int pos_r = distance(right.begin(), right.upper_bound(rating[j])); int pos_l = distance(left.begin(), left.upper_bound(rating[j])); cnt += (right.size() - pos_r) * pos_l; cnt += pos_r * (left.size() - pos_l); right.insert(rating[j]); } return cnt; }

[@greatfate]

@@finemechanic it turns out you're right here, only coz std::distance on std::set is O(n) (just realized that). But when I switch to __gnu_pbds::tree it does actually allow efficient indexing so it's O(nlogn). At least I had the right idea only lacked knowledge in c++ 🤦🏽🤦🏽

[@lolmes7473]

could you just explain the dp part through a diagram or table or anything other than code itself

[@zaid6527]

i was expecting binary indexed tree solution, the basic n^2 time and constant space i did it in first thinking

[@web-unlocked]

the bottom up solution feels so unnatural and confusing (to me), like what's up with the count thing and having an outer loop that only loops from 2 to 3

[@coolgamertm4411]

I was expecting BIT approach :( because rest every approach i understood by editorial the BIT i am not able to understand which was the most optimal

[@abhinavnarula7300]

i have a doubt, how do know which loop comes first and which loop becomes nested in tabulation. I did the tabulation but my outer loop was ind and inner was count. So how to know which loop will come first.

[@Antinormanisto]

I still don't understand. DP was always hard for me

[@pratyushthakur8478]

cooked

[@karthi7102]

The time complexity for memoization approach is O(2 **N) sir.

[@DeathSugar]

Firs solution was just three embed cycles, lol. It actually worked. Made it speed up up to x10 from initial.

[@aprasath1]

Simple 2 pass O(N*N) worked. It passed at 20 percent run time mark

[@ajayprabhu465]

int n = rating.length; int ans = 0; for(int i = 1; i < n - 1; i++){ int smallerLeft = 0; int greaterRight = 0; int smallerRight = 0; int greaterLeft = 0; for(int j = i - 1 ; j >= 0; j--){ if(rating[j] > rating[i])greaterLeft++; else smallerLeft++; } for(int j = i + 1; j < n; j++){ if(rating[j] > rating[i])greaterRight++; else smallerRight++; } ans += (greaterLeft * smallerRight) + (smallerLeft * greaterRight); } return ans; easier code