🇬🇧 112. Path Sum

🟢 Easy: 112. Path Sum
🧑‍💻 My solution: Java DFS in just 0 ms

Hi there! Let's see how can you solve the problem above.

🧑‍💻 Task 🧑‍💻
Your task is to find out if there is a path sum equal to given targetSum.

🧑‍💻 Idea 🧑‍💻
The idea is ordinary for such kind of problem: use DFS (Depth First Search) with recursion. If you are not familiar with this algorithm/solving concept, check this link out: Depth First Search (DFS).

🧑‍💻 Solution 🧑‍💻
So, you have a main method hasPathSum() and recursive helper method traverseBT(). Also, you can see a global variable result.

hasPathSum()

:
- Assign default value to the global variable result.
- Call the helper method traverseBT().
- Return the result.

traverseBT()

:
Parameters:
- You have TreeNode as a first parameter. Here node is the reference to the current node in a stack of recursive calls.
- sum parameter keeps the running sum until this call. Since this is a primitive type, sum's value is passed as a value. This means that you don't have to substract node.val in the end of the helper method.
- targetSum is our target sum. Why this is passed as a parameter and not used as a global? We can discuss the best way in the comments.

Method's content:
- if (node == null) return; - this is the base case for recursive method.
- sum += node.val; - you add node values along the way by this action.
- In the second if statement you check if the current node is a leaf node and running sum is equal to targetSum. If it is true, then the result is true.
- Then you need to make recursive calls for left and right nodes for current node.

That's it.
How can you improve this algorithm?

Good luck! ✌️😎

P.S. Sorry for overusing this catchy cat gify emoji 🧑‍💻, but I cannot stop myself from using it. 🧑‍💻🧑‍💻🧑‍💻

@leetcodin

🇺🇿 112. Path Sum

🟢 Oson: 112. Path Sum
🧑‍💻 Mening yechimim: Java DFS in just 0 ms

🧑‍💻 Vazifa 🧑‍💻
Sizning vazifangiz - bu binar daraxt bo'ylab aylanib chiqishingizda, tugunlar yig'indisi targetSum-ga teng bo'lgan "yo'l" borligini aniqlash.

🧑‍💻 G'oya 🧑‍💻
Bu yechim - shunday Depth First Search (DFS) masalalarga xos algoritmdir. Agar DFS tushunchasi notanish bo'lsa, bu postni tekshirinig Depth First Search (DFS).

🧑‍💻 Yechim 🧑‍💻
Sizda asosiy hasPathSum() va yordamchi rekursiv traverseBT() metod bo'ladi. Bulardan tashqari global boolean result o'zgaruvchisi bo'ladi.

hasPathSum()

:
- result o'zgaruvchisiga default qiymat berasiz.
- Yordamchi traverseBT() metodni chaqirasiz.
- result-ning qiymatini qaytarasiz.

traverseBT()

:
Parametrlar:
- TreeNode type-dagi node o'zgaruvchisi chaqiruvlar stack-idagi hozirgi tugunning ko'rsatgichi.
- sum parametri hozirgi tugungacha bo'lgan yig'indini saqlovchi primitiv o'zgaruvchi. Primitiv type-larning qiymati ko'chirilgan holda parametr sifatida yuboriladi. Bu orqali siz dinamik tarzda o'zgaruvchini o'zgartirmaysiz.
- targetSum parametri bu biz qidirayotgan yig'indi. Nimaga bu sonni global o'zgaruvchida saqlamasdan, parametr sifatida yuborganman? Bu savolni comments-da muhokama qilsak bo'ladi.

Metod:
- if (node == null) return; - bu rekursiyaning asosiy holati.
- sum += node.val; - bu harakat orqali yo'l-yo'lakay hozirgi tugungacha bo'lgan qiymatlarining yig'indisini hisoblaysiz.
- Ikkinchi if ifodasi ichida hozirgi tugun barg tugunligini va hozirgi yig'indi targetSum-ga tengligini tekshirasiz. Agar shu ifoda true bo'lsa, siz qidirilayotgan path-ni (yo'lni) topdingiz.
- Yordamchi metodning ichida o'zini (rekursiv chaqirish) chap va o'ng tugunlar uchun chaqirasiz.

Shu algoritmni yanada yaxshilash/tezlashtirish iloji bormi?
Comments-da bo'lishing.

Omad! ✌️😎

P.S. Dasturchi mushuk gif 🧑‍💻 emoji-sini ko'p ishlataman va uzr so'rayman, ammo bu emoji-ni baribir ishlataman. 🧑‍💻🧑‍💻🧑‍💻

@leetcodin

🇬🇧 113. Path Sum II

Hi! Let's practice binary tree today again. This time it is another Path Sum problem.

🟡 Medium: 113. Path Sum II
🧑‍💻 My solution: Java O(N) | DFS | 100% Faster Solution

Your task is to find out all paths with path sum equal to given targetSum.

Good luck! ✌️😎

@leetcodin

🇺🇿 113. Path Sum II

Salom! Keling bugun ham binar daraxtlar mavzusiga oid masala yechamiz. Kechagi Path Sum masalasining davomi.

🟡 O'rta daraja: 113. Path Sum II
🧑‍💻 Mening yechimim: Java O(N) | DFS | 100% Faster Solution

Sizning vazifangiz - bu binar daraxt bo'ylab aylanib chiqishingizda, tugunlar yig'indisi targetSum-ga teng bo'lgan har bir "yo'l"-ni topish.

Omad! ✌️😎

@leetcodin

🇬🇧 113. Path Sum II

🟡 Medium: 113. Path Sum II
🧑‍💻 My solution: Java O(N) | DFS | 100% Faster Solution

🧑‍💻 Task 🧑‍💻
Your task is to find out all paths with path sum equal to given targetSum.

🧑‍💻 Idea 🧑‍💻
The idea and the solution is pretty the same as for 112. Path Sum.

🧑‍💻 Solution 🧑‍💻
I'll focus on those parts of the code which are different from 112. Path Sum.

- Inside main pathSum() there is a list of lists of integers. You need this list to store paths with sum equal to targetSum.

- Helper goDFS() method has 2 more parameters:
1. list - a list which keeps values from the root to the current node.
2. listResult - a list of lists which keeps paths with path sum equal to targetSum.

- On each recursive call you add node.val to list.

- If current node is a leaf node and currSum is equal to targetSum, then you add current list to the listResult. Note that you new to add a copy of the list by new ArrayList<>(list). If you don't do this, all your sublists will be pointing at one list.

- In the end of the helper method you need to remove the element added during current recursive call. This keeps the correct order of node values for the path.

That's it.
Good luck! ✌️😎

@leetcodin

🇺🇿 113. Path Sum II

🟡 O'rta daraja: 113. Path Sum II
🧑‍💻 Mening yechimim: Java O(N) | DFS | 100% Faster Solution

🧑‍💻 Vazifa 🧑‍💻
Sizning vazifangiz - bu binar daraxt bo'ylab aylanib chiqishingizda, tugunlar yig'indisi targetSum-ga teng bo'lgan har bir "yo'l"-ni topish.

🧑‍💻 G'oya 🧑‍💻
Bu masalaning yechimi huddi 112. Path Sum masalaning yechimiga o'xshaydi. Farqli joylarini tushuntirib chiqaman.

🧑‍💻 Yechim 🧑‍💻
112. Path Sum -dan farqli joylarini tushuntirib chiqaman.

- Asosiy pathSum() metodi ichida list-lardan iborat list yaratasiz. Bu listResult o'zgaruvchisi sizga javoblarni saqlash uchun kerak bo'ladi.

- Yordamchi goDFS() metodi 2 yangi parametrga ega:
1. list - bu hozirgi "yo'l"-dagi bo'lgan tugunlarning qiymatlarini saqlobchi list.
2. listResult - o'zida javoblarni, ya'ni yig'indisi targetSum-ga teng bo'lgan list-larni saqlovchi list.

- Har bir rekursiv chaqiruv davomida currSum-ni hisoblashdan tashqari node.val-ni list-ning ichiga qo'shib qo'yasiz.

- Agar hozirgi tugun "barg" bo'lsa va shu tugungacha bo'lgan "yo'l"-dagi tugunlarning qiymatlarining yig'indisi targetSum-ga teng bo'lsa, shu list-ni natijaga qo'shib qo'yasiz. E'tibor bering, siz list-ning nusxasini qo'shashiz [new ArrayList<>(list)]. Agar bunday qilmasangiz, siz har safar bir xil list-ga ko'rsatuvchini qo'shgan bo'lasiz.

- Yordamchi rekursiv metodning oxirida tugunning qiymatini olib tashlaysiz. Shu orqali "yo'l"-dagi tugunlarning qiymatlarining tartib to'g'ri saqlanadi.

Omad! ✌️😎

@leetcodin

🇬🇧 Summary

Hi, guys! Let me summarize what we covered so far and share the links to the posts one more time, so that it would be easier to navigate.

1. 3 types of binary tree traversal.
2. Recursion. Theory.
3. Breaking the [bad] habit. Triggers.
4. Data Structure: Array.
5. Hashtable in Java. Inside out.
6. Data Structure: Linked list.
7. Data Structures: Stack and Queue.
8. Sorting Algorithms.

Thanks for reading this blog! ✌️😎

@leetcodin

🇺🇿 Summary

Hammaga salom! Bu postda men yozilgan mavzularga havolalarni qoldirmoqchiman. Maqsad - mavzularni tez topa olish.

1. Binar daraxtni aylanib o'tishning 3 xili.
2. Rekursiya. Nazariya.
3. Breaking the [bad] habit. Triggerlar.
4. Ma'lumotlar tuzilmasi: Massiv.
5. Java-da Hashtable. To'liq tahlil.
6. Ma'lumotlar tuzilmasi: Linked list.
7. Ma'lumotlar tuzilmasi: Stack va Queue.
8. Saralash algoritmlari.

Shu blogni o'qib borayotganingiz uchun rahmat! ✌️😎

@leetcodin

🇬🇧 2579. Count Total Number of Colored Cells

Hi! Let's solve one interesting problem using Mathematics.

🟡 Medium: 2579. Count Total Number of Colored Cells
🧑‍💻 My solution: Java 1 Line | Math | 100% Faster | Explained

Your task is to find the number of cells which you will have after n minutes by drawing touching cells.

Good luck! ✌️🧐

@leetcodin

🇺🇿 2579. Count Total Number of Colored Cells

Salom! Keling bugun matematika yordamida yechiladigan masalani ko'rib chiqamiz.

🟡 O'rta daraja: 2579. Count Total Number of Colored Cells
🧑‍💻 Mening yechimim: Java 1 Line | Math | 100% Faster | Explained

Sizning vazifangiz - bu har bir daqiqada (n daqiqa davomida) kataklarga, agar qo'shnisi bo'lmasa, qo'shni katak chizish va ularning sonini topish.

Omad! ✌️🧐

@leetcodin

🇬🇧 2579. Count Total Number of Colored Cells

🟡 Medium: 2579. Count Total Number of Colored Cells
🧑‍💻 My solution: Java 1 Line | Math | 100% Faster | Explained

Hi! Here is the one of possible solutions for the problem.

🧑‍💻 Task 🧑‍💻
Your task is to find the number of cells which you will have after n minutes by drawing touching cells.

🧑‍💻 Idea 🧑‍💻
If you pay attention and try drawing and counting cells, you will see that the number of colored cells is somehow connected to arithmetic progression sum.
The difference of each row is 2 (d = 2).

- I found out that the number of cells is the arithmetic progression sum for n plus arithmetic progression sum for n minus an or

Sum(n) + Sum(n) - an => 2 * Sum(n) - an. (a👋)

You know the first number [a1] of the arithmetic sequence [and it is 1].

If Sum(n) = ((a1 + an) * n ) / 2, then the formula (a👋) above will be

2 * Sum(n) - an = 2 * ((a1 + an) * n ) / 2 - an = (a1 + an) * n - an. (b👋)

Now, let's find an. According to the formula an = a1 + (n - 1) * d and this will be
an = 1 + (n - 1) * 2 = 1 + 2n - 2 = 2n - 1 => an = 2n - 1.

Finally, we put an into the formula (b👋)
(a1 + an) * n - an = (a1 + 2 * n - 1) * n - (2 * n - 1) = 2 * n * n - 2 * n + 1 = 2 * n * (n - 1) + 1.

So, the solution is 2 * n * (n - 1) + 1.

Good luck! ✌️🧐

@leetcodin

🇺🇿 2579. Count Total Number of Colored Cells

🟡 O'rta daraja: 2579. Count Total Number of Colored Cells
🧑‍💻 Mening yechimim: Java 1 Line | Math | 100% Faster | Explained

Salom! Kechagi masalaga yechim topamiz.

🧑‍💻 Vazifa 🧑‍💻
Sizning vazifangiz - bu har bir daqiqada (n daqiqa davomida) kataklarga, agar qo'shnisi bo'lmasa, qo'shni katak chizish va ularning sonini topish.

🧑‍💻 G'oya 🧑‍💻
Agar har xil n uchun kataklarni chizib va hisoblab ko'rsangiz, kataklarning yig'indisi arifmetik progressiyaning yig'indisi bilan bog'liqligini ko'rasiz.
NB: arifmetik progressiyaning d (qo'shni elementlarning farqi) 2ga teng.

Hisoblab chiqqanimdan keyin, kataklar soni nta elementning arifmetik yig'indisi va n-1 ta elementning arifmetik yig'indisi Sum(n) + Sum(n - 1) yoki

Sum(n) + Sum(n) - an => 2 * Sum(n) - an. (a👋)

Arifmetik progressiyaning birinchi elementi ma'lum bo'lgani uchun yig'indini topish uchun keyingi formulani ishlatsangiz bo'ladi:

Sum(n) = ((a1 + an) * n ) / 2.

Bu formulani (a👋) formulaga qo'ysangiz

2 * Sum(n) - an = 2 * ((a1 + an) * n ) / 2 - an = (a1 + an) * n - an. (b👋)

Keling, endi an (oxirgi element)ni topaylik. an = a1 + (n - 1) * d formulasini ishlatsangiz

an = a1 + (n - 1) * d = 1 + (n - 1) * 2 = 1 + 2n - 2 = 2n - 1 => an = 2n - 1.

Va an uchun topilgan ifodani (b👋) formulasiga qo'ysangiz

(a1 + an) * n - an = (a1 + 2 * n - 1) * n - (2 * n - 1) = 2 * n * n - 2 * n + 1 = 2 * n * (n - 1) + 1.

Xullas, javob 2 * n * (n - 1) + 1 bo'ldi.

Tushunarli bo'ldi degan umiddaman.
🧑‍💻 = 🧑‍💻 [Dasturlash = Dasturlashga]

Omad! ✌️🧐

@leetcodin

LeetCode 700.

Achieved another milestone of 700 solved problems on LeetCode.

What went better during these 100 problems:
- Finally reached 75% threshold which means that 75% of solved problems were of medium and hard levels.
- Seeing patterns and applying them to solve problems. Hence, spending less time to find solution.

Let's gooo! 🧑‍💻🎆

@leetcodin