Count Triplets That Can Form Two Arrays of Equal XOR - Leetcode 1442 - Python

Подписаться 156 тыс.

Просмотров 9 тыс.

50% 1

🚀 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

Опубликовано:

30 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 56

@NeetCodeIO 2 месяца назад

Just so you know, there's a reason that the 4th solution took half the video to explain. You've been warned :)

@satyamjha68 2 месяца назад

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

@jonsneep 2 месяца назад

Love this new format of you covering multiple options with different time-complexities

@nirmalgurjar8181 2 месяца назад

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.

@user-sx7zc3ez4w 2 месяца назад

God damn GENIUS 4th solution. BTW, No need to feel sorry since we can grab your explanation.

@erminiottone 2 месяца назад

Let's suffer together

@satyamjha68 2 месяца назад

4 approaches , amazing problem ! Perfect for a dsa interview!

@redfinance3403 2 месяца назад

i * prev_xor_cnt[prefix] - prev_xor_index_sum[prefix] is certainly a pattern to remember!

@sShield 2 месяца назад

I could not wrap my head around this problem, thanks bro :)

@NeetCodeIO 2 месяца назад

ofcourse, but no promises that my video will gurantee that either, it's a difficult one :)

@SudharsanSankaranarayanaPrasad 2 месяца назад

you just dropped the video at the exact same time when I was looking for it! Awesome explanation!

@theteacher010 2 месяца назад

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!

@NeetCodeIO 2 месяца назад

really appreciate that, thank you :)

@michael._. 2 месяца назад

who else was waiting for neetcode's explanation on O(n) solution

@MP-ny3ep 2 месяца назад

Beautifully explained. Thank you

@chien-yuyeh9386 2 месяца назад

Thanks for sharing! 🎉

@sachethkoushik2265 2 месяца назад

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 :)

@saianuragone828 2 месяца назад

Great Explanation man, Loved it🙌

@mounirkanane8083 2 месяца назад

Thanks bro you've really become a veteran at leetcode and that is reflected in your explanations nowadays

@pastori2672 2 месяца назад

a lot of effort was put into this one thank you

@protodimbo 2 месяца назад

you can also feel good about yourself because I'm about to probably make you feel bad 🤣🤣🤣

@MasterOwen69 2 месяца назад

Exactly what i am about to comment..🤣🤣

@TenzDelek 2 месяца назад

I understood the n2 solution better than the n3,n4 one haha

@rlm3227 2 месяца назад

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.

@Perry-tf2pr 2 месяца назад

last solution res += i * prev_xor_cnt[prefix] - prev_xor_index_sum[prefix] likely summation iterations formula

@nathan_ca 2 месяца назад

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

@melvinbijman2337 2 месяца назад

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

@deadlyecho 2 месяца назад

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 😂

@limsiryuean5040 2 месяца назад

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

@ish90917 2 месяца назад

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.

@evalyly9313 2 месяца назад

Falling in love with your brain❤

@nikhil199029 2 месяца назад

you are codegay

@HuanjiaLiang 2 месяца назад

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!

@ajayprabhu465 2 месяца назад

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.

@mounirkanane8083 2 месяца назад

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?

@thelindayz2087 2 месяца назад

no no no he's fixing k

@GameFlife 2 месяца назад

When i heard neet say hopefully interview they dont ask you to come up with this am just fing froze hahaha

@PhanNghia-fk5rv 2 месяца назад

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