O(n) is simple maths we can derive equation from O(n * n) solution, here is how> Once you code O(n * n) solution and check the line where you are updating the count, by simple maths you will notice that you are updating res count in the loop matching idx times and subtracting each matching index, so that equation comes to count += (number of matching idx * current idx - sum of all matching idx) , once you get this you can convert O(n * n) solution to n solution using 2 hashmaps.
Watched well over 250 of your videos and this is honestly one of THE best ones yet. Thanks for being an ever-helpful presence in my hunt for a new gig!
if anyone's lookin for a lil more pythony but simplified code, here's one res = curr = 0 d = defaultdict(lambda: (0, 0)) d[0] = (1, 0) # count, index sum called as total henceforth for i, x in enumerate(arr): curr ^= x cnt, total = d[curr] res += (i * cnt) - total d[curr] = (cnt + 1, total + i + 1) return res ps: haven't completely wrapped my head and this one still :)
@NeetCodeIO, thanks for another great explanation but one point though. Writing N capitalised would denote it as a global, (stored on the heap) accessible by every function and method. As such lowercase would be correct way.
bro I was searching for this in the morning, even though I later found some bit manipulation concept I didn't remember, as I was looking for some hints which helped me solve this problem.
Good mental exercise! I think the real tricky part is the i * prev_cnt, you could explain that a bit more while you draw, also during interviews I think the most difficult part is to figure out those index + 1 for the index_sum in order for math to work out. BUT nice explanation, if I were to read code myself it would at least 30 mins for me to figure out
The O(n) solution seems like a happy coincidence between array and XOR properties, it is pretty hard to explain a coincidence. But either way your solution is pretty clear and thank you for torturing my brain
Leetcode 560 -> Leetcode 1074 -> Leetcode 1442 def countTriplets(self, ar: List[int]) -> int: res = 0 prefix = {0: [0]} curXor = 0 for i in range(len(ar)): curXor ^= ar[i] if curXor in prefix: for v in prefix[curXor]: res += (i - v) prefix[curXor].append(i + 1) else: prefix[curXor] = [i + 1] return res
Hello, I have a question, in 2:46, shouldn't b be 0 since b = arr[j] XOR arr[k], and arr[j] == arr[k] == 3, so 3 XOR 3 == 0? But in the video it says b == 3, i am confused, thanks!
can anyone help me with a doubt: what was the significance of that x1 ^ x2 ... in commning up with n^2 solution? and why k - i , on what basis? thank you in advance.
Just so you know, there's a reason that the 4th solution took half the video to explain. You've been warned :)
I also took some time to think O(n) approach , I guess I wouldn't be able to code the O(n) during 45 minutes interview
Love this new format of you covering multiple options with different time-complexities
O(n) is simple maths we can derive equation from O(n * n) solution, here is how> Once you code O(n * n) solution and check the line where you are updating the count, by simple maths you will notice that you are updating res count in the loop matching idx times and subtracting each matching index, so that equation comes to count += (number of matching idx * current idx - sum of all matching idx) , once you get this you can convert O(n * n) solution to n solution using 2 hashmaps.
God damn GENIUS 4th solution. BTW, No need to feel sorry since we can grab your explanation.
Let's suffer together
4 approaches , amazing problem ! Perfect for a dsa interview!
Watched well over 250 of your videos and this is honestly one of THE best ones yet. Thanks for being an ever-helpful presence in my hunt for a new gig!
really appreciate that, thank you :)
I could not wrap my head around this problem, thanks bro :)
ofcourse, but no promises that my video will gurantee that either, it's a difficult one :)
you just dropped the video at the exact same time when I was looking for it! Awesome explanation!
i * prev_xor_cnt[prefix] - prev_xor_index_sum[prefix] is certainly a pattern to remember!
Beautifully explained. Thank you
if anyone's lookin for a lil more pythony but simplified code, here's one
res = curr = 0
d = defaultdict(lambda: (0, 0))
d[0] = (1, 0) # count, index sum called as total henceforth
for i, x in enumerate(arr):
curr ^= x
cnt, total = d[curr]
res += (i * cnt) - total
d[curr] = (cnt + 1, total + i + 1)
return res
ps: haven't completely wrapped my head and this one still :)
Thanks bro you've really become a veteran at leetcode and that is reflected in your explanations nowadays
who else was waiting for neetcode's explanation on O(n) solution
a lot of effort was put into this one thank you
Thanks for sharing! 🎉
@NeetCodeIO, thanks for another great explanation but one point though.
Writing N capitalised would denote it as a global, (stored on the heap) accessible by every function and method.
As such lowercase would be correct way.
I understood the n2 solution better than the n3,n4 one haha
last solution res += i * prev_xor_cnt[prefix] - prev_xor_index_sum[prefix] likely summation iterations formula
bro I was searching for this in the morning, even though I later found some bit manipulation concept I didn't remember, as I was looking for some hints which helped me solve this problem.
Good mental exercise! I think the real tricky part is the i * prev_cnt, you could explain that a bit more while you draw, also during interviews I think the most difficult part is to figure out those index + 1 for the index_sum in order for math to work out. BUT nice explanation, if I were to read code myself it would at least 30 mins for me to figure out
Great Explanation man, Loved it🙌
The O(n) solution seems like a happy coincidence between array and XOR properties, it is pretty hard to explain a coincidence. But either way your solution is pretty clear and thank you for torturing my brain
Leetcode 560 -> Leetcode 1074 -> Leetcode 1442
def countTriplets(self, ar: List[int]) -> int:
res = 0
prefix = {0: [0]}
curXor = 0
for i in range(len(ar)):
curXor ^= ar[i]
if curXor in prefix:
for v in prefix[curXor]:
res += (i - v)
prefix[curXor].append(i + 1)
else:
prefix[curXor] = [i + 1]
return res
Falling in love with your brain❤
you are codegay
I think after seeing the code of the 4th solution, it became a little bit easier to understand. So watch the whole thing for a better understanding.
you can also feel good about yourself because I'm about to probably make you feel bad 🤣🤣🤣
Exactly what i am about to comment..🤣🤣
This was definitely hard to come up with the O(n^2) and O(n) solutions
Hello, I have a question, in 2:46, shouldn't b be 0 since b = arr[j] XOR arr[k], and arr[j] == arr[k] == 3, so 3 XOR 3 == 0? But in the video it says b == 3, i am confused, thanks!
Question: 14:14 you say k is also fixed but cant k also = j? So k could either be at index 1 or index 2?
no no no he's fixing k
"u like suffering as much as I do" , we on a right path
I came up with the N^3 first and then the N^2... and then saw the shit that's going through people's minds in the leetcode solutions section 😂
When i heard neet say hopefully interview they dont ask you to come up with this am just fing froze hahaha
I gave up trying to understand after second solution, but watched the video anyway. I'm just tired of xor math for this month.
can anyone help me with a doubt:
what was the significance of that x1 ^ x2 ... in commning up with n^2 solution? and why k - i , on what basis?
thank you in advance.
3143. Maximum Points Inside the Square
@NeetCodeIO please add timer and notes on neetcode
bro I think at this point i am in love with suffering with you
What the hell is XOR
Came up with n^2 solution but was irritated i couldn't come up with n
why a^= arr[j-1] and not j?
portion a starts from i (since first j is i + 1, take j - 1) and it goes up until the index before j (a doesn't include element at index j)
in your defense, I'll say those who make it till the end of the video would finally get it lol
how 2 Xor 2 is 2 its 0 not understand the N^4 solution
still didn't understand o(n) solution
why why why why why why why whyyyyyyyyyyyy
she grokking on my data structure until i leetcode