@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
@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
@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
@andrewlewis7610
Thanks for the neetcode 150! I completed it today after several months of chipping away at it. It was quite painful experience for me and required a lot of persistence so I'm very happy to say I finished it. Top surprising takeaways are: 1. I know what it feels like to work on a problem too long when not making progress and what it feels like to look up the answer too early. With this experience I feel like I can work on new problems more efficiently. 2. I have a skeleton of knowledge, or a broad high level view map, where even if I don't know the tricks nessecary to solve the problem, it's either a) increasingly possible to "invent" on the spot, or failing that, b) looking up and learning the answer is quicker and easier to comprehend since it's just a variation of some concepts I've already learned. What next for me is: - Reviewing previously solved problems, this time going for speed - Start solving problems where I don't know the "category" of problem ahead of time thanks and good luck everyone
@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.
@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
---
@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!
@TR1TUS3
the GOAT uploaded so fast
@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
@mudd7522
Best leetcode YouTube channel for sure
@olhabahatiuk6009
Thanks!
@MinhNguyen-lz1pg
Simply brilliant, I did not see LC solution published yet for this problem but great explanation my dude!
@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
@alexanderlin2022
Great video and your voice in this video is much more calm, which is great! easier to listen and follow.
@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).
@vritanshpatel3844
AM I MISUNDERSTANDING THIS AND JUST MAKING UP THIS EDGE-CASE ? I am so frustrated and confused because I considered an edge-case which leetcode testcase runner and result checker doesn't consider at all, due to which my answers were wrong for some testcases. and once I commented out that edge-case code block everything ran fine and was able to pass all testcases. The Edge-case : The query point used in count() functionality is already present in the data structure, as it was added through add() functionality before, and so they should be considered as different points due to which the result of count() functionality differs.
@NeetCode