Count Number of Teams - Leetcode 1395 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
7:42 - Coding Explanation
10:32 - Coding Memoization
13:34 - Coding DP

leetcode 1395

#neetcode #leetcode #python

[freecourseplatformenglish]

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

[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.

[sourabhgurav]

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

[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!

[crekso]

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

[rajdeepguha]

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

[AnkitaNallana]

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

[rahulsbhatt]

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

[IK-xkex]

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

[hithambasheir]

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!

[aadil]

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.

[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.

[lolmes]

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

[abhinavnarula]

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.

[SLASH-yvuz]

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

[coolgamertm]

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

[pastori]

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

[zaid]

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