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

😅😄 @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

🇬🇧 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 Salom! Bugun ham masala yechamiz. Bu safar binar daraxtlar mavzusi. 🟢 Oson: 112. Path Sum 🧑‍💻 Mening yechimim: Java DFS in just 0 ms Sizning vazifangiz - bu binar daraxt bo'ylab aylanib chiqishingizda, tugunlar yig'indisi targetSum-ga teng bo'lgan "yo'l" borligini aniqlash. Omad! ✌️😎 @leetcodin

🇬🇧 112. Path Sum Hi! Another day - another Binary tree problem. Let's do it. 🟢 Easy: 112. Path Sum 🧑‍💻 My solution: Java DFS in just 0 ms Your task is to find out if there is a path sum equal to given targetSum. Good luck! ✌️😎 @leetcodin

🇺🇿 875. Koko Eating Bananas 🟡 O'rta daraja: 875. Koko Eating Bananas 🧑‍💻 Mening yechimim: Java O(N + NlogN) Solution Salom! Bugun shu masalaning yechimlaridan bittasini tushuntirib berishga harakat qilaman. 🧑‍💻 Vazifa 🧑‍💻 Sizga bananlar toplamlaridan iborat massiv va h soatlar soni berilgan. k soni bu bir soatda nechta banan yeyillish mumkinligini ko'rsatuvchi son. Siz shunday eng kichik bo'lgan k-ni topshingiz kerakki, hamma banan shu h soat ichida qolmasligi lozim. 🧑‍💻 G'oya 🧑‍💻 Yechimning asosiy g'oyasi - bu k-ni topish uchun binar qidiruvni ishlatmoq. Binar qidiruvning chegaralari sifatida min va max-larni ishlatasiz. min 1ga teng bo'ladi, chunki eng kichik mumkin bo'lgan tezlik (k) bu 1, va max berilgan massivdagi eng katta songa teng bo'ladi. 🧑‍💻 Yechim 🧑‍💻 - min va max o'zgaruvchilarini yaratib, ularning qiymatlarini tepada yozib o'tgan qiymatlarga tenglashtirasiz. - Agar h massivning uzunligiga teng bo'lsa, max qaytariladi. Nimaga bunday bo'lishi haqida o'ylab ko'ring. - Binar qidiruv orqali k-ni topish uchun ikkita loop ishlatasiz: 1. Tashqi while loop binar qidiruv uchun ishlatiladi. Uning ichida tempH o'zgaruvchisini har bir iteratsiya uchun ishlatasiz. mid (potensial k)-ni min va max o'rtasidagi qiymatga tenglashtirasiz. 2. for loop ichida tempH-ni mid uchun hisoblaysiz. 3. Agar tempH h-ga teng yoki kichik va tempH noldan katta bo'lsa, siz qidiruv intervalining tepa chegarasini max = mid - 1 orqali kamaytirasiz. 4. Agar tempH h-dan katta bo'lsa yoki tempH 0-dan kichik bo'lsa, siz qidiruv intervalining past chegarasini min = mid + 1 orqali kattalashtirasiz. - Agar min max-dan katta bo'lib ketsa, tashqi while loop-dan chiqasiz va min-ning qiymatini qaytarasiz. 🧐 S: if (tempH <= h && tempH > 0) ifodasini tushuntirib bering. 👍 J: 1. Keling ifodaning tempH <= h qismini tahlil qilamiz. Agar tempH h-dan kichik bo'lsa, k biz qidirayotgan qiymatdan katta bo'ladi. Agar tempH h-ga teng bo'lsa, bu degani siz mumkin bo'lgan k-lardan bittasini topdingiz. Lekin bu k eng kichik bo'lmasligi mumkin va shuning uchun undan kichikroq qiymatni qidirasiz. 2. tempH > 0 esa k (mid)-ning qiymati juda kichik qiymatga teng bo'lgan holatlar uchun. tempH 0-dan kichik bo'lishi sababi, bu mid kichik son bo'lib va har bir n katta son bo'lsa, tempH += n / mid orqali n / mid qiymatlarini qo'shganimizda, yig'indisi integer-ning tepa chegarasidan oshib ketishi mumkin. Natijada tempH-ning qiymati salbiy bo'ladi. 🧐 S: if (tempH > h || tempH < 0) ifodasini tushuntirib bering. 👍 J: 1. Agar tempH berilgan h-dan katta bo'lsa, hozirgi k (mid) siz qidirayotgan k-dan kichikroq va shuning uchun qidiruv intervalining past chegarasini kattaroq qiymat mid + 1 ga tenglashtirasiz. 2. tempH < 0 - aytib o'tganimdek, agar tempH 0-dan kichik bo'lsa hozirgi k (mid)-ning qiymati juda kichik va tempH asli qiymati integer o'zgaruvchisi chegarasiga sig'maganligi sababli salbiy qiymatga ega. Shuning uchun k uchun kattaroq qiymatlarni ko'rib chiqishingiz lozim. Tushuntira oldim degan umiddaman. Omad! ✌️😎 @leetcodin

🇬🇧 875. Koko Eating Bananas 🟡 Medium: 875. Koko Eating Bananas 🧑‍💻 My solution: Java O(N + NlogN) Solution Hi! Let's check one of the possible solutions for this problem. 🧑‍💻 Task 🧑‍💻 You are given piles of bananas as an array and h hours. Your task is to find the minimum integer k such that all the bananas can be eaten within h hours. 🧑‍💻 Idea 🧑‍💻 The idea is to calculate k using binary search. I set limits with min and max. min is equal to 1 since it is least possible k (which is speed) and max is the max size of a pile inside given array. 🧑‍💻 Solution 🧑‍💻 Let's look at the code. - First, I create variables min and max and find the max from piles array. - Second, if h is equal to the length of the array, then I just return max. Think about it. - Then I have a nested loop: 1. Outer while loop is used for binary search. I create tempH for current iteration and calculate mid point (possible k) for min and max. 2. Then inside of for loop I calculate h (tempH) for current value of mid. 3. If tempH equals h and tempH is greater than 0, then I just set max as mid - 1. Thus, the upper bound of the interval where we search for k has been cut to half. 4. Else if tempH is greater than h or tempH is less than 0, then I just change the lower bound of search interval by setting min equal to mid + 1. When min becomes greater than max, we stop the while loop and return min. 🧐 Q: if (tempH <= h && tempH > 0) why do we have such a condition? A: 1. Let's have a look at the first part tempH <= h. If tempH is less than h, it means that k is greater than we need. If tempH is equal to h, it means that we found possible k. This k may not be the least possible k, that's why we need to try to find the value even less than the current. 2. The second part has been added for cases when k (mid) is equal to a small number and piles are pretty big numbers, so that while summing tempH += n / mid we can go out of bounds of integer and the value of tempH may become negative. 🧐 Q: Explain this condition if (tempH > h || tempH < 0). A: 1. First part means that our k is less than we need to have, so we increase the lower bound by doing min = mid + 1. 2. tempH < 0 this condition check if we have such a big value, which does not fit the integer limits and became negative. This means we have too small value as k and we need to look for inside of half of search interval with greater numbers. I think I made it clear. Cheers! ✌️😎 @leetcodin

🇺🇿 875. Koko Eating Bananas 🟡 O'rta daraja: 875. Koko Eating Bananas 🧑‍💻 Mening yechimim: Java O(N + NlogN) Solution Salom! Keling ozgina amaliy mashqlar ham bajaraylik. Sizga bananlar toplamlaridan iborat massiv va h soatlar soni berilgan. k soni bu bir soatda nechta banan yeyillish mumkinligini ko'rsatuvchi son. Siz shunday eng kichik bo'lgan k-ni topshingiz kerakki, hamma banan shu h soat ichida qolmasligi lozim. Maqsad - algoritmning tezligi O(N ^ 2)-dan yaxshiroq bo'lishi kerak. Omad! ✌️😎 @leetcodin

🇬🇧 875. Koko Eating Bananas 🟡 Medium: 875. Koko Eating Bananas 🧑‍💻 My solution: Java O(N + NlogN) Solution Hi! Let's have some practice and solve today's daily problem. You are given piles of bananas as an array and h hours. Your task is to find the minimum integer k such that all the bananas can be eaten within h hours. The goal is to write an algorithm which runs faster than O(N ^ 2). Good luck! ✌️😎 @leetcodin

Sifatli kontent yaratuvchi mualliflarni ro’yxatini shakllantirishni rejalashtirdik. Bunda sizning yordamingiz kerak! Siz hurmat qiladigan va kuzatadigan blog va sahifalar mualliflarini kategoriyalar bo’yicha so’rovnomada ko’rsatib o’ting. Imkoni bo’lsa havola bilan. Oldindan rahmat! https://forms.gle/GMkEJHrCeps5wL9x7 Планируем создать список авторов, создающих качественный контент. Для этого нужна ваша помощь! Перечислите авторов блогов и страниц, на которые вы подписаны в соответствии с категориями в опросе. Если можно со ссылкой. Заранее спасибо!

Code @leetcodin

🇺🇿 Shell saralash algoritmi. Salom! Bugun yangi Shell saralash algoritmini ko'rib chiqaman. 😇 Github: ShellSort ⏰ Time complexity: O'rtacha - O(N ^ (3/2)), Eng yomon holatda - O(N ^ 2) 🔎 Space complexity: O(1) 🧑‍💻 G'oya 🧑‍💻 Shell sort, uni 1959-yilda kashf etgan, Donald L. Shell-dan nomini olgan. Shell sort Kiritish orqali saralash usulining asosida ishlaydi. Kiritish orqalis saralash algoritmida siz elementlarni faqat bir pozitsiyaga sura olasiz. Agar element massivning oxiridan boshiga joylashtirilishi kerak bo'lsa, siz ko'p swap operatsiyasini bajarasiz. Shell sort algoritmining g'oyasi - bu uzoq masofada joylashgan elementlarni saralash. Bu algoritm orqali siz elementlarni h uzoqlikda saralangan qilasiz. Shu h-ning qiymati 1ga teng bo'lmagunicha uni kamaytiraverasiz. h uzoqlikda saralangan degani bir biridan h uzoqlikda joylashgan elementlarning har bir ro'yxatda saralangan holatda bo'lishi. 🧑‍💻 Algoritm 🧑‍💻 h = h * 3 + 1 -> bu Knuth-ning Interval ketma-ketliklar uchun formulasi. 1. Birinchi while loop berilgan massiv uchun to'g'ri h-ni topish uchun ishlatasiz. 2. Keyin esa nested loop ishlatasiz. - Birinchi tashki while loop-ni h-ning qiymatini formula bo'yicha kamaytirish uchun ishlatasiz. - Ichki for loop-da esa Kiritish orqali saralash [Insertion sort] algoritmini h uzoqlikda joylashgan elementlar uchun ishlatasiz. - Ichki while loop Kiritish orqali saralashga o'xshab, h uzoqlikda joylashgan elementlar uchun katta elementlarni o'nga suradi va tanlangan elementni o'z joyiga qo'yadi. Manbalar: Sources: 1. Data Structures and Algorithms in Java. R. Lafore. 2. Geeksforgeeks 3. GIF Rahmat! Omad! ✌️😎 @leetcodin

🇬🇧 Shell Sort. Hi! Another day - another sorting algorithm. 😄 😇 Link to Github: ShellSort ⏰ Time complexity: Average O(N ^ (3/2)), Worst case O(N ^ 2) 🔎 Space complexity: O(1) 🧑‍💻 Idea 🧑‍💻 The Shell sort is named for Donald L. Shell, the computer scientist who discovered it in 1959. Shell sort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of Shell sort is to allow the exchange of far items. In Shell sort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element are sorted. 🧑‍💻 Algorithm 🧑‍💻 h = h * 3 + 1 is a formula of Knuth's Interval Sequence. 1. The first while loop is used to find appropriate h for the size of given array. 2. Then we have a nested loop. - Outer while loop is used to decrease the h number till 1. - Inner for loop uses Insertion sort to sort the elements placed h numbers away each other. - Inner while loop does what Insertion sort does: it moves larger elements to the right and puts chosen element to its position, so that elements which are h steps from each other are sorted. Sources: 1. Data Structures and Algorithms in Java. R. Lafore. 2. Geeksforgeeks 3. GIF Thanks for reading! Good luck! ✌️😎 @leetcodin