LeetCodin

2023-03-15 15:17:02 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 Ochish/sharhlash

2023-03-14 17:19:01 @leetcodin Ochish/sharhlash

2023-03-14 16:18:01 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 Ochish/sharhlash

2023-03-14 15:17:02 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 Ochish/sharhlash

2023-03-12 15:17:00 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 Ochish/sharhlash

2023-03-12 15:17:00 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 Ochish/sharhlash

2023-03-12 07:19:00

@leetcodin Ochish/sharhlash

2023-03-11 19:21:01 Ochish/sharhlash

2023-03-11 18:20:24 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 Ochish/sharhlash

2023-03-11 18:20:24 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 Ochish/sharhlash