I just have solved one really difficult (but medium level) problem on LeetCode. Here is the link to the problem: https://leetcode.com/problems/3sum/description/

It took several days to write a solution which passes the time requirements for it. Since it is 3Sum task, I could use brootforce approach to solve it, but it didn't work due to time constraints. So, after long-long nights of trying different approaches I came up with the one that worked out.

The complexity of it is beautiful: O(N * log(N) + N * N * log(N)) 😂

Here is the explanation for my solution:
- Sorted the array to be able to use binary search O((N * log(N)).
- Picked two numbers O(N * N) and found the third one by binary searching O(log(N)).
- Added the sorted result to the set to make sure that the combination of 3 numbers is unique.
- Then returned the result.

And yes, here is the link to my solution:
https://leetcode.com/problems/3sum/solutions/2710157/java-o-n-log-n-n-n-log-n-solution/

Subscribe for more.

🇺🇿O'zbekchada pastda⬇️

🇬🇧
So, I was solving easy level problem Problem 88. Merge Sorted Array. I solved it with the first solution which came to my mind and the result was 6.5% faster than other solutions. I was not satisfied with this result and decided to find a faster solution or even come up with 100% faster solution (among Java solutions).

Thus, this resulted in finding 3 more solutions and reaching that goal - 100% faster solution.

You can check them out here -> link

Subscribe for more

🇺🇿 O'zimizchasi

O'zbek tilida matnni yozishdan avval bir narsani aytib o'tishim lozim: men o'zbek tilida o'qimaganman va xatolar qilishim mumkin. Iltimos, postlarimni o'qiyotganda buni inobatga oling. Boshladik!

Xullas, men oson darajali misol yechayotgan edim Problem 88. Merge Sorted Array. Men buni xayolimga kelgan birinchi fikrga ko'ra yechdim va natijada yechimim boshqalarning Java tilida yechimlariga qaraganda 6,5% tezroq edi. Men bu natijadan qoniqmadim va tezroq ishlab beradigan algoritmlik yechimni topishga yoki hatto 100% yechimlardan tezroq yechim topishga qaror qildim.

Shunday qilib, bu masalaga yana 3ta yechim topdim va oxirida o'zimning maqsadimga erishdim - 100% tezroq yechimni topa oldim.

Siz ularni bu yerda tekshirishingiz mumkin -> havola

Obuna bo'ling (follow qiling)

🇺🇿O'zbekchada pastda⬇️

🇬🇧
Today I would like to briefly discuss Depth First Search (DFS). Usually, I use this recursive approach to solve problems with trees. You should consider the repetitive case/action which you apply on each iteration/node. Also, don't forget about the base case, when you should stop your recursive calls.

Basically, DFS recursive method I applied to trees 🎄 usually looks like this:

private void traverseBT(TreeNode node) {
//1. Base case or case when you should stop recursive calls
if (node == nulll) {
return;
}

//2. Some action with node or its value

//3. Apply the same action to the left child
traverseBT(node.left);

//and to the right child
traverseBT(node.right);
}

For example, a problem: Problem 100
And my solution (0️⃣ ms, 1️⃣0️⃣0️⃣% faster in Java ☕️): solution link

As you can see this algorithm is pretty useful for traversing trees. Don't run into StackOverFlow 😁

If you find this useful, then subscribe for more

Tags:
#binarytree binary tree

🇺🇿O'zimizchasi

Hammaga salom.
Bugun Depth First Search (DFS) haqida qisqacha yozmoqchiman. Meningcha, bu LeetCode da juda ham ko'p ishlatiladigan yondashuv. Odatda bu rekursiv yondashuvni men tree (daraxt) lar bilan bog'liq misollarni yechish uchun ishlataman. Bu uslub ishlatganda har bir iteratsiya/tugunda qo'llanadigan takrorlanuvchi holatni/harakatni ko'rib chiqishingiz kerak. Bundan tashqari, rekursiv chaqirishlarni to'xtatish kerak bo'lgan asosiy holat haqida unutmang.

Asosan, men daraxtlarga 🎄 (tree) qo'llaydigan DFS rekursiv usuli odatda shunday ko'rinishga ega:

private void traverseBT(TreeNode node) {
        //1. Asosiy holat
        if (node == nulll) {
            return;
        }
        
        //2. Daraxt tuguni (tree node) yoki uning qiymati bilan ba'zi harakatlar

        //3. Xuddi shu harakatni chap bolasiga rekursiv chaqirish orqali qo'llang
        traverseBT(node.left);

        //va xuddi shu harakatni o'ng bolasiga rekursiv chaqirish orqali qo'llang
        traverseBT(node.right);
}

Shu algoritm uchun misol: Problem 100
Va mening yechimim (Javada 0️⃣ ms, 1️⃣0️⃣0️⃣% tezroq ☕️): yechim havolasi

Ko'rib turganingizdek, bu algoritm daraxtlarni kesib o'tish uchun juda foydali. StackOverFlow haqida unutmang 😁

Agar siz buni foydali deb topsangiz, obuna bo'ling

Tags:
#binarytree binary tree

🇺🇿O'zbekchasi pastda⬇️


🇬🇧English

Today I wanted to share one of the most interesting problems that I have solved on LeetCode. When I found the third solution I literally laughed out loudly for a couple of minutes 😂. Why? Because it has 1 line solution. Coming up with this solution took much more time (than laughing 😂). I felt myself like I was tricked out.

OK. Let's check the problem here first: Problem 877: Stone Game.
At first glance it may seem that this is pretty complicated question. but later I figured out that it wasn't so.

I prepared two O(N) solutions and they worked out. Basically, they were iterating over the array and choosing the largest number (Greedy approach). However, at some point I realized that Alice (who is playing first and the sum of piles of stones are odd, and the number of piles are even) can always make such a choice that she wins. So, this means that we can always return true. And this can be proven by method of mathematical induction. Thus, the third solution consisted of only 1 line, which made my day.

Link to my solutions: Solutions

Subscribe for more

🇺🇿O'zbek tilida

Hammaga salom! Bugun men sizlarga LeetCode da yechgan eng qiziqarli vazifalardan biri haqida aytib bermoqchiman. Uchinchi yechimni topganimda, bu bir-ikki daqiqa kulishimga sabab bo'ldi 😂. Nega deb so'raysizmi? Chunki u 1 qatorli yechimga ega. Ushbu yechimni o'ylab topish ancha ko'proq vaqtni oldi (kulishdan ko'ra 😂). Men o'zimni aldangandek his qildim.

OK. Avval bu yerda vazifaning shartini o'qib chiqsangiz bo'ladi: Problem 877: Stone Game
Bir qarashda, bu murakkab savol bo'lib tuyulishi mumkin, lekin keyinroq unday emasligini angladim.

Men ikkita O(N) yechim tayyorladim va ular hamma testdan o'tdi. Asosan, ulardagi ishlatilgan uslub bu massivning sonlarini ko'rib chiqib, har safar ikkitasidan kattarog'ini tanlash edi (Greedy yondashuv). Biroq, bir nuqtada men Alice har doim g'alaba qozonish uchun (birinchi bo'lib o'ynaydigan va toshlar yig'indisi toq va qoziqlar soni juft) shunday tanlov qilishini angladim. Demak, bu bizga har doim true qaytishini anglatadi. Va buni matematik induksiya usuli bilan isbotlash mumkin. Shunday qilib, uchinchi yechim faqat 1 qatordan iborat edi. Bu holat made my day 😁

Aytib o'tilgan yechimlar bu yerda: havola

Agar siz buni foydali deb topsangiz, obuna bo'ling

🇺🇿O'zbekchasi pastda⬇️

🇬🇧English

Hi, guys! Today I just want to share the optimized algorithm for Fibonacci numbers. The approach is following: using recursion for sum calculation and using memoization to store visited cases. I knew about recursive approach to this problem before, but I didn't use memoization. So, while solving the problem, I had to optimize my algorithm, so that it will pass all test and would not run out of time limits.

The problem: Problem 509. Fibonacci Number
1️⃣0️⃣0️⃣
My solution: 0 ms | 100% faster | Recursive | Memoization

I'll add the code here, but if you want to challenge yourself, then try to write your own solution based on the text above, before seeing the code below:

class Solution {
static HashMap<Integer, Integer> cache = new HashMap<>();

public int fib(int n) {
if (cache.containsKey(n)) {
return cache.get(n);
}

if (n < 2) {
return n;
}
int result = fib(n - 2) + fib(n - 1);
if (!cache.containsKey(n)) {
cache.put(n, result);
}
return result;
}
}

I used HashMap as a key -> value cache for saving input -> result pairs. This makes the performance of the solution really fast, since saving these values allows to omit repetitive calls.

Subscribe for more

🇺🇿O'zbek tilida

Hammaga salom! Bugun men Fibonachchi raqamlari uchun optimallashtirilgan algoritmi haqida yozmoqchiman.

Yondashuv quyidagicha: yig'indini hisoblash uchun rekursiyadan foydalanish va xar bir yig'indi uchun holatlarni saqlash - memoization. Men bu muammoga rekursiv method yozish mumkinligi haqida avval ham bilardim, lekin memoization bilan foydalanganim birinchi marta edi. Chunki, muammoga yechim topishda barcha testlardan chegaralangan vaqt ichida o'tish uchun men algoritmimni optimallashtirishim kerak edi.

Vazifa: Problem 509. Fibonacci Number
1️⃣0️⃣0️⃣
Men yozgan kod: 0 ms | 100% faster | Recursive | Memoization

Men bu gapning tagiga kodni qo'shaman, lekin agar siz o'zingizni sinab ko'rmoqchi bo'lsangiz, quyidagi kodni ko'rishdan oldin yuqoridagi matn asosida o'z yechimingizni yozishga harakat qilib ko'ring.

class Solution {
static HashMap<Integer, Integer> cache = new HashMap<>();

public int fib(int n) {
if (cache.containsKey(n)) {
return cache.get(n);
}

if (n < 2) {
return n;
}
int result = fib(n - 2) + fib(n - 1);
if (!cache.containsKey(n)) {
cache.put(n, result);
}
return result;
}
}

Men HashMap dan kirish -> natija juftlarini saqlash uchun kalit -> qiymat cache i sifatida foydalandim. Bu yechimning ishlashini ancha tezlashtiradi, chunki cache natijalarni saqlab, methodlarning takroriy recursive chaqirishlarini qilmaslikka imkon beradi.

Agar siz buni foydali deb topsangiz, obuna bo'ling

🇺🇿O'zbekchasi pastda⬇️

🇬🇧English

Hi, guys! Today I'd like to answer the comment of one of the subscribers: "What sources do you study which help you to solve LeetCode problems to achieve this number of solved problems?"

First, I graduated WIUT and obtained some knowledge on Data Structures and Algorithms (DSA) there. Just basic things like different kinds of O(N^2) sorting.

During those years my coursemate Sherali Obidov taught us programming in Java during the summer before the last year. I remember that he gave us homework tasks to solve 50 - 100 problems during 1 week, till the next lesson :). All these tasks covered DSA as well. I think he was one of the best mentors who taught me coding.
Go and give a star to his repo on Algorithms

3 years ago I applied to the online course "Algorithms and data structures on C. Interactive course" on geekbrains.ru. I enjoyed the course: we wrote data structures from scratch, covered O(N) compexities of each operation for DS, and etc. This gave me a better understanding of how different data structures work. So, here is common advice: if you want to understand a certain data structure, write its implementation in your programming language.

Since my main language is Java, I try to learn how it works, how the implementations of data structures work in Java. I read the doc or/and just read the code.

I have a daily task to solve 2 problems on LeetCode, so I try to accomplish it.

Also, when I solve a problem and I am not satisfied with the performance results, I try to think of another solution with better performance. But if I don't find it, I go and check other people's solutions. This gives you different points of view on the task. Again, only after I find my own solution, I permit myself to go and see how others approached to solving the problem.

If you want to share your experience or the source where you learn from, then, please, share in the comments 😃

🇺🇿O'zbek tilida

Hammaga salom! Bugun men obunachidan berilgan savolga javob bermoqchiman: "assalomu alekum bunday natijaga qanday erishgansiz ya'ni leetcode dan shuncha masala ishlash uchun qanday kitoblardan, video darsliklardan foydalangansiz, o'rgangansiz.shu haqida ham biror post tayyorlasangiz ancha manfaatli bo'lardi yoki shunchaki javob bersangiz xam bo'ladi"

Men TXVUni o'qiganman va u yerda Data structures and algorithms (DSA) [ma'lumotlar tuzilmalari va algoritmlari] boshlang'ich bilim oldganman. Har xil turdagi O (N ^ 2) sorting (saralash) kabi algorithm lar.

O'sha yillarda kursdoshim Sherali Obidov 3 kursni bitirganimizdan keyin yozda bizga Java tilida dasturlash darslarini tashkillashtirdi. Esimda, u bizga 1 hafta davomida, keyingi darsgacha 50 - 100 ta masalani yechishni uy vazifasi sifatida bergan 😅😂. Bu vazifalarning ichida DSA ham bor edi. Menga kod yozishni o'rgatgan eng yaxshi murabbiylardan biri deb bilaman.
Uning algorithm lar haqidagi repo siga yulduz bering: havola ⭐️. Aytgancha, u Google da ishlaydi.

3 yil oldin geekbrains.ru saytidagi "Algorithm lar va ma'lumotlar tuzilmalari. C tilidagi interaktiv kurs" onlayn kursida o'qidim. Menga kurs yoqdi: biz maʼlumotlar tuzilmalarini noldan yozdik, DS uchun har bir operatsiyaning O(N) murakkabliklarini qamrab oldik va hokazo. Bu menga turli xil maʼlumotlar tuzilmalari qanday ishlashini yaxshiroq tushunish imkonini berdi. Shunday qilib, bu yerda keng tarqalgan maslahatni yozib o'tmoqchiman: agar siz ma'lum bir ma'lumotlar strukturasini tushunmoqchi bo'lsangiz, uni dasturlash tilingizda yozib ko'ring.

Mening asosiy tilim Java bo'lgani uchun men uning qanday ishlashini, Java da ma'lumotlar tuzilmalarini amalda qanday ishlashini o'rganishga harakat qilaman. Men doc o'qiyman va/yoki kodni o'qib chiqaman.

Menda yana kundalik vazifam bor - LeetCode da 2 ta muammoga yechim topish. Shu vazifani bajarishga harakat qilaman.

Bundan tashqari, men muammoni yechganimda va ishlash natijalaridan qoniqmaganimda, men tezroq ishlaydigan yechim topishga harakat qilaman. Ammo topmasam, boshqa odamlarning echimlarini qarab ko'raman. Bu sizga vazifaga turli nuqtai nazarlardan qarash imkonini beradi. E'tibor bering, men o'z yechimimni topgandan keyingina, boshqa odamlarning misollarni yechish uslublarini ko'ra olaman.

Agar siz o'z tajribangiz yoki muammolarni yechishda qo'llaydigan manbalaringiz bilan bo'lishmoqchi bo'lsangiz, kommentariylarda

🇺🇿O'zbekchasi pastda⬇️

🇬🇧English
Hi, guys! Not much text from me today.

I struggled with tasks where you have to do some operations on list: like reverting or joining with different requirements. I used ArrayLists to solve those problems which already were organized into list.

However, after some practice I was able to solve such problems on the go and without using extra data structures.

For example, check Problem 61. Rotate List
And my solution: Solution

Share your solutions in the comments. Let's discuss!

🇺🇿O'zbek tilida

Hammaga salom! Bugun kamroq yozaman, chunki mashq qilamiz!

Bir oz vaqt oldin, List lar ustida baʼzi operatsiyalarni bajarish kerak boʻlgan vazifalarni yechishga qiynalar edim. Bunday operatsiyalar odatda List ni orqadan oldinga o'girish yoki turli xil qoʻshish edi. Bunday muammolarni yechish uchun ArrayList dan foydalanar edim (o'zi List structure da berilgan bo'lsa ham).

Lekin shunday masalalarni yechaverib, tajriba orttirdim va shu muammolarni on the go (buni tarjimasini bilmayman, afsus) va qo'shimcha ma'lumotlar tuzilmalaridan (data structures) foydalanmasdan yecha oladigan bo'ldim.

Mening yechimim: Solution
Masalani o'zi: Problem 61. Rotate List

Yechimlaringiz va fikrlaringiz bilan bo'lishing. Keling, muhokama qilaylik!

🇺🇿O'zbekchasi pastda⬇️

🇬🇧English

Hi, guys! Since today is Saturday👀, then let's just solve some simple problem with 2D arrays. Yes, it has medium difficulty label, but the solution is just straightforward. I think everyone can write a solution for it. You just need to apply certain conditions for each iteration and that, basically, is.

Problem: 289. Game of Life
My solution: Solution

Please, try to solve yourself first and then look up to others' solutions.

You can share your solutions or links to your solutions in comments. Let's upvote solutions that you like.👍

🇺🇿O'zbek tilida

Hammaga salom! Bugun shanba ekan👀, keling, 2D massivlar bilan oddiy masalani yechaylik. Ha, u o'rtacha qiyinchilik belgisiga ega, ammo yechimi oddiy. Menimcha, hamma yechimini topa oladi. Siz har bir iteratsiya uchun ma'lum shartlarni qo'llashingiz kerak xolos.

Masala: 289. Game of Life
Mening yechimim: Solution

Iltimos, avval o'zingiz masalani yechishga urinib ko'ring, keyin esa boshqalarning yechimlarini qarang.

Yechimlaringiz yoki yechimlaringizga havolalarni sharhlarda bo'lishingiz mumkin. Keling, yoqqan yechimlarga ovoz beraylik.👍

🇺🇿O'zbekchasi pastda⬇️

🇬🇧English

Hi, guys! Today is Sunday and it's rainy outside. Let's recover one of previous topics: DFS recursive traversing. I gave basic approach I use to solve such problems [here] and you can easily apply it to the following problem. Let's do it!

Problem: 112. Path Sum
My solution: Solution

Share your results and see whose solution is faster😁