🇬🇧 Sort an array

🤩 Medium: 912. Sort an Array
🧑‍💻 Solution: Java MergeSort Solution

Hi! Since we are learning sorting algorithms and the daily challenge on March 1 was to sort an array, then let's have fun and solve the problem using MergeSort and QuickSort.

Share your results in the comments below.
Cheers! ✌️😎

@leetcodin

🇺🇿 Massiv saralash

🤩 O'rta daraja: 912. Sort an Array
🧑‍💻 Yechim: Java MergeSort Solution

Salom! 1-mart kuni daily challenge sifatida massiv saralash masalasi berilgandi. Qarang-a, biz ham saralash algoritmlarini o'rganayotgan edik. Keling shu masalani Birlashtirish orqali va Tez saralash algoritmlarini ishlatib yechib ko'ramiz.

Natijalarni comments-da yozing - kimda tezroq ishlaganini ko'ramiz.
Omad! ✌️😎

@leetcodin

🇬🇧 Sorting. Short summary.

Hi! 👋 With this post I want to make a small summary of sorting algorithms that were covered so far.

1. Bubble Sort. O(N ^ 2)
2. Selection Sort. O(N ^ 2)
3. Insertion Sort. O(N ^ 2)
4. Merge Sort. O(N * logN)
5. Quick Sort. O(N * logN) to O(N ^ 2)
6. Shell Sort. Average O(N ^ (3/2)).

🧑‍💻 Also, I'll add the link to this post to the pinned content, so that you can easy navigate to necessary topics.

Cheers! ✌️😎

🇺🇿 Saralash algoritmlari. Havolalar.

Salom! 👋 Bu postda o'tilgan saralash algoritmlarga havolalarni bir joyga yig'ib qo'ymoqchiman.

1. Bubble saralash usuli. O(N ^ 2).
2. Selection saralash usuli. O(N ^ 2).
3. Insertion (kiritish) saralash usuli. O(N ^ 2).
4. Birlashtirish orqali saralash usuli. O(N * logN).
5. Quick (tez) saralash usuli. O(N * logN) dan O(N ^ 2) gacha.
6. Shell saralash algoritmi. O'rtacha - O(N ^ (3/2)).

🧑‍💻 O'tilgan mavzularni topish osonroq bo'lishi uchun, pinned post-larga shu post-ning havolasini qo'shib qo'yaman.

Oma✌️😎

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

🇺🇿 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 orqali 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 hajmi uchun to'g'ri h-ni topish uchun ishlatasiz.

2. Keyin esa nested loop ishlatasiz.
- Birinchi tashqi 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:
1. Data Structures and Algorithms in Java. R. Lafore.
2. Geeksforgeeks
3. GIF

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

🇺🇿 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 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! 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

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

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