Count Triplets That Can Form Two Arrays of Equal XOR - Leetcode 1442 - Python
HTML-код
- Опубликовано: 25 июн 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/count-t...
0:00 - Read the problem
0:50 - O(n^4) Explanation
4:15 - O(n^4) Coding
6:13 - O(n^3) Explanation
7:58 - O(n^3) Coding
9:25 - O(n^2) Explanation
14:45 - O(n^2) Coding
15:58 - O(n) Explanation
27:28 - O(n) Coding
leetcode 1442
#neetcode #leetcode #python
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!
i * prev_xor_cnt[prefix] - prev_xor_index_sum[prefix] is certainly a pattern to remember!
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 :)
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 :)
you just dropped the video at the exact same time when I was looking for it! Awesome explanation!
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 :)
Beautifully explained. Thank you
who else was waiting for neetcode's explanation on O(n) solution
Thanks for sharing! 🎉
Great Explanation man, Loved it🙌
Thanks bro you've really become a veteran at leetcode and that is reflected in your explanations nowadays
a lot of effort was put into this one thank you
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
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
you can also feel good about yourself because I'm about to probably make you feel bad 🤣🤣🤣
Exactly what i am about to comment..🤣🤣
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
@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.
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
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 😂
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.
When i heard neet say hopefully interview they dont ask you to come up with this am just fing froze hahaha
Falling in love with your brain❤
you are codegay
I gave up trying to understand after second solution, but watched the video anyway. I'm just tired of xor math for this month.
"u like suffering as much as I do" , we on a right path
@NeetCodeIO please add timer and notes on neetcode
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
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.
3143. Maximum Points Inside the Square
bro I think at this point i am in love with suffering with you
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)
how 2 Xor 2 is 2 its 0 not understand the N^4 solution
why why why why why why why whyyyyyyyyyyyy
in your defense, I'll say those who make it till the end of the video would finally get it lol
What the hell is XOR
she grokking on my data structure until i leetcode