Detect Squares - Leetcode Weekly Contest - Problem 2013 - Python

[@NeetCode]

⭐ MEDIUM Playlist: kzbin.info/www/bejne/oKu9pHpuo5eFb6M

[@ariannalangwang5698]

Thanks so much for compiling the Medium Playlist🙏! I'm just about to finish the Easy list & wonder how I can find all the medium LC on your channel 😃. Neetcode, could you also compile other playlists such as string, heap, array, etc? Your channel is my go-to LC channel now! Thanks again for all your great teaching!!

[@ahmedtremo]

Finally done with Neetcode 150 list :D

[@EduarteBDO]

Finished neetcode 150, thank you for the roadmap, it was super challenging but at same time it was fun. Even if I don't pass any interview I feel like it was worth the time spend on this.

[@scnehal]

To avoid the extra list: class DetectSquares: def __init__(self): self.pts = defaultdict(int) def add(self, point: List[int]) -> None: self.pts[tuple(point)] += 1 def count(self, point: List[int]) -> int: res = 0 px, py = point print('New') for x, y in self.pts: if (abs(px - x) != abs(py - y)) or x == px or y == py: continue if (px, y) in self.pts and (x, py) in self.pts: # Multiply with the number of occurrences of the repeated point represented by self.pts[(x, y)] res += self.pts[(px, y)] * self.pts[(x, py)] * self.pts[(x, y)] return res

[@Kirrozoid]

Thanks for the help mate!

[@chaoticguud]

Beautiful

[@amrutaparab4939]

Thanks much!

[@theSilentPsycho]

For the diagonal equation of a square: We know that the / diagonal of a square parallel to x-axis will make a 45 degree with the x-axis (by Alternate Interior Angles). Slope of a line = m = (y2 - y1)/(x2-x1) = tan(theta) = tan (45 degrees) = 1 Therefore, y2 - y1 = x2 - x1

[@romo119]

This hasn't worked for me but original has. Is this still missing the x != px && y != py?

[@VarunMittal-viralmutant]

If you want to avoid the extra List: --------- def count(self, point): px, py = point res = 0 for x, y in list(self.points): if (abs(px - x) != abs(py - y)) or px == x or py == y: continue res += self.points[(x, y)] * self.points[(px, y)] * self.points[(x, py)] return res

[@duonazhang8324]

brilliant! i forgot to multiply the res by self.points[(x,y)]

[@camoenv3272]

Doesn't seem to resolve the issue, since defaultdict will add values to the dictionary on existence check (which then breaks the loop, since the number of items in the dictionary changes during iteration). We can use '.get', though, which will get around this issue: class DetectSquares: def __init__(self): self.points = {} def add(self, point: List[int]) -> None: self.points[tuple(point)] = self.points.get(tuple(point), 0) + 1 def count(self, point: List[int]) -> int: res = 0 px, py = point for x, y in self.points: if (abs(px - x) != abs(py - y)) or x == px or y == py: continue res += self.points.get((x, y), 0) * self.points.get((x, py), 0) * self.points.get((px, y), 0) return res

[@VarunMittal-viralmutant]

@@camoenv3272 Nope, it does. Notice the list() in the for loop. Once list has been created for iteration, it won't matter if the dictionary changes during iteration

[@Grawlix99]

@@VarunMittal-viralmutant ah, missed that. Makes sense!

[@attkgreenpiggy]

You can also avoid turning it into a list by using collections.Counter() instead of defaultdict(int), as item retrieval doesn't create an entry in a counter.

[@pedroalonsoms]

The solution is missing multiplying by (x,y), they recently added those cases: class DetectSquares: def __init__(self): self.d = defaultdict(int) def add(self, point: List[int]) -> None: self.d[tuple(point)] += 1 def count(self, point: List[int]) -> int: ans = 0 px, py = point for key in self.d: x, y = key dx = abs(px - x) dy = abs(py - y) if dx > 0 and dy > 0 and dx == dy: if (x, py) in self.d and (px, y) in self.d: ans += self.d[(x, py)] * self.d[(px, y)] * self.d[(x, y)] return ans

[@avisternlieb449]

Was still looking at the problems. Holy wow was that fast! Can't wait to watch.

[@MrKulkoski]

I think you could've just multiplied by the count of the diagonal point instead of using a list. Still great video as always!

[@rickyjay10]

right, would be: res += self.points[(x, py)] * self.points[(px, y)] * self.points[(x,y)]

[@vasujain1970]

Right!

[@amandaflood]

Yep 👍

[@fsteve6443]

the GOAT uploaded so fast

[@mudd7522]

Best leetcode KZbin channel for sure

[@jkim5118]

Still not quite sure why we need a list? What causes the error?

[@CEOofTheHood]

Exactly , I'm soo unsure. Its eating at me. Mr.Neet please reply.

[@kaylaelortondo4349]

Attempting to access a non-existent key in a defaultdict will add that key (with a value of zero in this case). This causes the dictionary to mutate while we are iterating over it, which throws an error. Below will work, but you have to make two changes. 1) Make a copy of the list of keys before iterating, and 2) Include the diagonal point's count in the multiplication before adding to the result. This is because the call to .keys() will never include duplicates, where as iterating over a list (the approach he switched to) will allow us to come across multiple copies of the diagonal point. def __init__(self): self.points = defaultdict(int) def add(self, point: List[int]) -> None: self.points[tuple(point)] += 1 def count(self, point: List[int]) -> int: result = 0 px, py = point keys = list(self.points.keys()) for x, y in keys: if (abs(x - px) == abs(y - py)) and (x != px and y != py): result += self.points[(x, py)] * self.points[(px, y)] * self.points[(x, y)] return result

[@DavidDLee]

You don't really need the list if you also multiply with the count of the third point from the map.

[@lavanya_m01]

​@@kaylaelortondo4349 bro you're brilliant, I was trying to understand where the heck the dict got mutated but didn't catch the point that it gets mutated when we access a non-existent key

[@wsasobi8195]

To avoid the extra list, we can use Counter instead: --- class DetectSquares: def __init__(self): self.counter = Counter() def add(self, point: List[int]) -> None: self.counter[tuple(point)] += 1 def count(self, point: List[int]) -> int: x1, y1 = point res = 0 for x2, y2 in self.counter: if x1 == x2 or y1 == y2 or abs(x1-x2) != abs(y1-y2): continue res += self.counter[(x1, y2)] * self.counter[(x2, y1)] * self.counter[(x2, y2)] return res ---

[@alexanderlin2022]

Great video and your voice in this video is much more calm, which is great! easier to listen and follow.

[@MinhNguyen-lz1pg]

Simply brilliant, I did not see LC solution published yet for this problem but great explanation my dude!

[@vaibhaviambarkar4359]

To count rectangles instead of squares, we need to change the logic so that it doesnt require the points to be diagonally equidistant. It should just check for points forming opposite corners of rectangle. Only this check - if(px == x || py == y) need to be performed, skip the equidistant check and it should work for counting rectangles

[@_ipsissimus_]

i gotta get the like out early cuz imma forget while im getting my mind blown.

[@brecoldyls]

Thank you! Why did we have to use a list do you think? What's the issue with using a dictionary? I thought the use of a defaultdict was clever.

[@kaylaelortondo4349]

Attempting to access a non-existent key in a defaultdict will add that key (with a value of zero in this case). This causes the dictionary to mutate while we are iterating over it, which throws an error. Below will work, but you have to make two changes. 1) Make a copy of the list of keys before iterating, and 2) Include the diagonal point's count in the multiplication before adding to the result. This is because the call to .keys() will never include duplicates, where as iterating over a list (the approach he switched to) will allow us to come across multiple copies of the diagonal point. def __init__(self): self.points = defaultdict(int) def add(self, point: List[int]) -> None: self.points[tuple(point)] += 1 def count(self, point: List[int]) -> int: result = 0 px, py = point keys = list(self.points.keys()) for x, y in keys: if (abs(x - px) == abs(y - py)) and (x != px and y != py): result += self.points[(x, py)] * self.points[(px, y)] * self.points[(x, y)] return result

[@mehdisaffar]

Can't we make the diagonal points search faster by having a self.diag and self.antidiag which gets populated in add() with self.diag[x-y] and self.antidiag[x+y] (or maybe the opposite), so for each point we know all the diag/antidiag points with which it could form a square?

[@XxRazcxX]

Since you're storing the points in a list as well wont you get duplicates when you iterate through it?

[@MidgarZolom]

Good video and succinct code. I think it would be worth mentioning the HashMap approach as well, since it is more optimal in runtime assuming a random data set (i.e. all points aren't on a line).

[@rishabsharma5307]

How can we extend it to rectangle or any other shape?

[@bluesteel1]

Neetcode 150 Done :)

[@alphonseprakash7459]

thanks so damn fast 😂😂😂😂

[@ahmedadebisi881]

Is there a reason why you didn’t multiply the other diagonal point. Assuming it has a count > 1.

[@brecoldyls]

I think it's because since we are iterating through all the diagonal points anyway, we will add the squares formed from a duplicate diagonal point in another iteration of the loop

[@ahmedadebisi881]

@@brecoldyls thanks

[@dibstuff813]

please do Leetcode 1570: Dot Product of Two Sparse Vectors. I cannot find a good explanation anywhere!

[@yukselpolatakbyk8468]

Hey this is the solution I have. I remember reading discussion solutions to optimize my solution: class SparseVector: def __init__(self, nums: List[int]): self.d = {} for i, n in enumerate(nums): if n != 0: self.d[i] = n # Return the dotProduct of two sparse vectors def dotProduct(self, vec: 'SparseVector') -> int: #n1 #n2 # 0:1 1:3 #3:2 3:4 #4:3 smaller = self.d if len(self.d) < len(vec.d) else vec.d bigger = self.d if len(self.d) >= len(vec.d) else vec.d res=0 for k1, v1 in smaller.items(): if k1 in bigger: res += v1*bigger[k1] return res

[@AymenDaoudi-u6h]

What about "Positive area", I don't think this solution covers this requirement

[@icaryslittle6370]

very helpful ... thank you!

[@yingjun8118]

Good videos, thank you!

[@sammarth2]

we did not need list, we can go through dictionary and multiply what you are trying to by value code: class DetectSquares: def __init__(self): self.points = defaultdict(int) def add(self, point: List[int]) -> None: self.points[(point[0], point[1])] += 1 def count(self, point: List[int]) -> int: result, px, py = 0, point[0], point[1] for indices, val in self.points.items(): x, y = indices if [x,y] != point and (abs(px-x) == abs(py-y)): result += val * self.points.get((x, py), 0) * self.points.get((px, y), 0) return result

[@asdfasyakitori8514]

Great video!

[@gdthegreat]

Bhai, kahase ho tum? Mast channel he, awesome.

[@aadil4236]

nice solution!

[@olhabahatiuk6009]

Thanks!

[@arunsinghin]

Can you talk about the time and space complexity of this problem??

[@MinhNguyen-lz1pg]

dude, he mentioned it in the video: TC: O(n) since we check all possible point in point list, since we use hash map to retrieve count of non-diagonal points, it will be constant time. SC: O(n) since we use hashmap and list to store coordinates

[@ygwg6145]

Time complexity O(1): using hash map of hash map.

[@orellavie6233]

Explain please

[@ygwg6145]

map(x, map(y,count)) Given x, find map(y,count) which has O(1) elements on average. For each element, you can calc number of squares in O(1) time. So O(1) average time in total. Worst case O(n) when map[x] is O(n).

[@AllanBProductions]

May you please do 907 Sum of Subarray Minimums?

[@AnkitSingh-wq2rk]

I am not suggesting any answer but i would recommend try these questions of stack before NGR,NGL,NSR,NSL element (next greater/smaller left/right element) and then try the your question once again it might give you right direction to solve such problems

[@jagatthi]

This solution does not work. We did not take into account of the diagonal point count

[@NeetCode]

Did you try submitting it?

[@Kettlebot]

It should work because we are iterating through all the points, so the diagonal point count is considered later. Hope that helps

[@jayatigoyal7715]

You're right! It worked once I multiplied the diagonal point count as well. Maybe this error was coming because I was not using an extra list to iterate through the elements, when Neetcode is adding elements to the list, he is adding the duplicate elements as well, which is why this error did not occur for him.

[@annsway]

I go this problem in an interview. I failed. Wish I watched your video before 😢

[@olamideabegunde3298]

I'm so sorry to hear but wow this is a hard question for an interview! What company was this?

[@bakrichodhpakistani7196]

Amazing Explanation man You are made for teaching. Just Post vdo regularly for each contest It would be better if you Upload code in either C++ or Java

[@director8656]

idk about the last statement chief, python is pretty universal and looks a lot like psuedo code.

[@Lambyyy]

Python is better for gaining understanding of the concepts.

[@robbyoconnor]

Imagine being that one bitter guy who disliked this video lol...

[@olhabahatiuk6009]

Thanks!