🇺🇿 86. Partition List

Hammaga salom! Bugun yana bitta Linked List-ga oid masala!
Vazifa: list-ni shunday bo'lib chiqish kerakki, berilgan x sonidan kichik sonlar chapda, x-ga teng va undan katta bo'lgan sonlar o'ngda kelishi kerak.

Sizlarga challenge: O(N) tezlikda ishlaydigan algoritm yoza olasizlarmi?

🟡 O'rta daraja: 86. Partition List
👨‍💻 Mening yechimim: Java 100% Faster Solution | O(N)

Omad!✌️

🇬🇧 Happy New Year!
I wish you solving 1 000 problems on LeetCode in 2023! 😁✌️🤓

🇺🇿 Yangi Yil Muborak!
Sizlarga LeetCode-da 2023-yilda 1 000 masala yechishni tilayman! 😁✌️🤓

Oldik! 🥂

🇬🇧 86. Partition List

Haven't seen you for a year, guys.😁

🟡 Medium: 86. Partition List
👨‍💻 My solution: Java 100% Faster Solution | O(N)

Let's see one of the O(N) solutions.

👨‍💻 Task
Your task was to place the nodes with values less than given x first and then place the rest. You should keep the order in which nodes come.

👨‍💻 Solution
Basic idea is to figure out that we need to divide the list into two lists: with nodes less than x and nodes which are equal or greater than x. Then in the end just connect these two lists.

If you pay close attention you can see that this problem's solution has some similarities with the previous one: 328. Odd Even Linked List.

I have dummy cases validation and pointers to the heads and current nodes as in previous solution.

Inside the while loop I by using first if statement I figure out to which list should I append current node. If the value is less than x then I add it to the first list:
lessCurr.next = current;
lessCurr = lessCurr.next;
The second line is used for moving thru the list.

if (lessCurr == null) {
lessCurr = current;
lessHead = lessCurr;
}
This part is used to start off the first list and assign its head node.

The same actions are applied to the second list [which will contain nodes with values equal or greater than x.

current = current.next; - this line is used to loop through the given list.

if (xCurr != null) xCurr.next = null; - in the beginning I assigned null to almost all variables. So, I need to validate them. If xCurr points to a node, then the next should point to null to show that this is going to be the end of the result list.

if (lessCurr != null) lessCurr.next = xHead; - here I check for null and connect the end of the first list to the start of the second list.

In the end, I have ternary operator, since we might have lists containing values which belong only to one list [which means that the other list will be null].

Good! Another puzzle is puzzled out.😄
Cheers!✌️🤓

🇺🇿 86. Partition List

O'zi ham bir yil ko'rishmagan ekanmiz!😁

🟡 O'rta daraja: 86. Partition List
👨‍💻 Mening yechimim: Java 100% Faster Solution | O(N)

Hammaga salom! Keling bugun shu masalaning O(N) yechimlaridan bittasini ko'raylik.

👨‍💻 Vazifa
List-ni shunday bo'lib chiqish kerakki, berilgan x sonidan kichik sonlar chapda, x-ga teng va undan katta bo'lgan sonlar o'ngda kelishi kerak.

Yechimning asosiy g'oyasi - bu berilgan list-ni ikkita alohida list-ga bo'lish va oxirida ularni bir-biriga ulash.

Agar eslasangiz avvalgi masalamiz bilan ko'p o'xshash joylari bor: 328. Odd Even Linked List.

Boshida "tentak"😁 holatlarni tekshiramiz, huddi oldingi yechimdagidek.
while loop-ning ichida katta if bloki hozirgi element qaysi list-ga tegishligini bilish uchun ishlatamiz: x-dan kichik bo'lsa, birinchi list-ga qo'shamiz, aks holda - ikkinchi list-ga.
lessCurr.next = current;
lessCurr = lessCurr.next;
Ikkinchi qatorda kichiklar list-i bo'ylab aylanish chiqish uchun kerak.

if (lessCurr == null) {
lessCurr = current;
lessHead = lessCurr;
}
Bu blok esa kichiklar list-ni boshini aniqlash uchun ishlataman.

Huddi shu harakatlarni kattalar (x-ga teng yoki kattaroq qiymatli) list-i uchun ham bajaraman.

if (xCurr != null) xCurr.next = null; - boshida shu o'zgaruvchini null-ga tenglashtirganim sababli uni tekshiraman va tekshiruvdan o'tsa, shu elementning keyingi elementga ko'rsatuvchi ko'rsatgichiga null yozaman. Chunki bu natijadagi hosil bo'ladigan list-ni shu yerda tugashini bildiradi.

if (lessCurr != null) lessCurr.next = xHead; - o'zgaruvchini tekshirib, kichiklar list-ini oxirgi elementini kattalar list-ining boshiga ulayman.

Oxirida esa ternary operatorini ishlatganman. Chunki kichiklar yoki kattalar list-larimizdan bittasi bo'sh bo'lishi mumkin. Nimaga deysizmi? Chunki bizga faqat x-dan kichikroq yoki kattaroq sonlar berilishi mumkin. Bu esa bitta list null bo'lish mumkinligini anglatadi.

Yaxshi! Bunisini ham ko'rib chiqdik.🤜🤛
Omad!✌️🤓

🇬🇧 Yay! This year started with this. Let's goooo!

🇺🇿 Yilning boshlanishi chakki emas! Shunday davom etaveramiz!

🇬🇧 Theory

Hi guys! I found one article in about data structures in Uzbek. The article briefly describes Array, Linked List, Stack, and Queue data structures. I hope you guys will enjoy it.

Please, tell me what you want to cover deeply among these 4 data structures. Let me know in the comments below.

Link to the article: Ma’lumot tuzilmalari (data structures), Linked List, Stack, Queue

🇺🇿 Nazariya

Hammaga salom! Sizlar uchun bitta o'zbek tilida yozilgan maqola topdim. Unda Massiv, Linked List, Stack va Queue ma'lumotlar tuzilmalarini qisqacha ko'rib chiqishgan. Sizlarga yoqadi degan umiddaman.

Meni qiziqtirayotgan narsa - shu to'rtta ma'lumotlar tuzilmalari bo'yicha qaysi mavzularni chuqurroq o'rganishni xohlaysiz? Comment-larda yozing.

Maqola: Ma’lumot tuzilmalari (data structures), Linked List, Stack, Queue

🇬🇧 Theory. Linked List.

Hi, guys! Let's start series of posts where I'll try to cover Linked List data structure. I'm going to discuss unidirectional linked list. Don't forget that I use Java and some explanations may be language specific.

In linked list each data element is placed into a special object which we call a list element or node. Since such list contains many elements of the same type, it's more convenient to create a separate class (different from Linked List) for data storage. Often such a class is called Node or Link. Each list node will contain its data and a link to the next node of the list. Usually, this link is named next. The linked list object has the link to the first node.

So, you can imagine it like in the picture below.

Q: Why do we need two classes for Linked List?
A: Together because. Just kidding :). We need a Node class to create a sequential structure of linked nodes. We need Linked List class to manipulate these nodes: add one more node, delete a certain node by index or by value, and other actions.

Q: We put object of the same type inside each other. How a computer (compiler) does not get confused?
A: The thing is that a node will not contain other node. It will just contain a reference (link) to the next object. This reference is the object's address in computer's memory.

References:
1. Data Structures and Algorithms in Java. R. Lafore.
2. Internet.

I think that's it for today :)
Catch you in the next one ✌️🤓

🇺🇿 Nazariya. Linked List.

Hammaga salom! Keling shu Linked List mavzusini yaxshilab o'rganaylik. Bu mavzuni shoshmasdan bir nechta postlarda ko'rib chiqamiz. Men bir tomon yo'naltirilgan list haqida yozmoqchiman.

NB:
1. List - bu ro'yxat. Lekin list deb ishlatilishi qulayroq deb o'ylayman va keyinchalik "list" so'zini ishlataman.
2. Men bu ma'lumotlar tuzilmasiga izoh berayotganimda Java tili nazaridan yozayotgan bo'laman. Shuning uchun boshqa dasturlash tillari bilan farqi bo'lishi mumkin.
3. Nimadirga izoh berganimda soddaroq qilishga harakat qilaman, chunki bu post endi boshlagan dasturchilar ham tushunib olishi mumkin bo'lishi uchun yozilgan.

Boshladik!
Linked list-da har bir ma'lumot maxsus obyektlarga joylashtiriladi. Bunday obyektlar element deb ataladi. Linked List-da bir xil elementlar mavjud bo'lganligi uchun, ularga alohida class yaratganimiz ma'qul. Odatda bunday class Node yoki Link deb ataladi. List-ning har bir elementi o'zining ma'lumoti va keyingi elementga ko'rsatgichga ega bo'ladi. Bu ko'rsatgichni nomi odatda - next. Linked List obyektining o'zi esa birinchi elementga ko'rsatuvchi ko'rsatgichni saqlaydi.

Postdan keyin joylashtirilgan rasmga qarab, LInked List-ni taxminan tasavvur qilishingiz mumkin.

S: Nega ikkita har xil class ishlatiladi?
J: Chunki bu ishimizni qulaylashtiradi. Node obyektlarini ketma-ket tuzilmani ko'rsatgichlar orqali qurish uchun ishlatamiz. Linked List class esa shu Node-lar ustida harakatlar oshirish uchun kerak. Masalan: element qo'shmoq, elementni index yoki qiymati bo'yicha o'chirmoq va boshqa harakatlar.

S: Biz bir turdagi obyektlarni bir-birining ichiga joylashtiramiz. Kompilyator qanday qilib adashmaydi?
J: Gap shundaki, element o'zida boshqa elementni saqlamaydi. U boshqa elementga bo'lgan ko'rsatgichni saqlaydi. Bu ko'rsatgich kompyuterning xotirasidagi shu obyektning "manzili"-ni bildiradi.

Havolalar:
1. Data Structures and Algorithms in Java. R. Lafore.
2. Internet.

Bugunga shu :)
Sizlardan layk, sher, Alisher😁
Keyingi postlarda ko'rishamiz ✌️🤓

🇬🇧 Theory. Linked List.
Relationship, Not Position.

Let’s examine one of the major ways in which linked lists differ from arrays. In an array each item occupies a particular position. This position can be directly accessed using an index number. It’s like a row of houses: You can find a particular house using its address.

In a list the only way to find a particular element is to follow along the chain of elements. It’s more like human relations. Maybe you ask Alisher where Bobur is. Alisher doesn’t know, but he thinks Dilafro'z might know, so you go and ask Dilafro'z. Dilafro'z saw Bobur leave the office with Sardor, so you call Sardor’s cell phone. He dropped Bobur off at Jakhongir’s office, so...but you get the idea. You can’t access a data item directly; you must use relationships between the items to locate it. You start with the first item, go to the second, then the third, until you find what you’re looking for.

Another example can be a "football" in local organizations: you call an operator 1, who ask you to call to a person 2. Then the person 2 says that he/she has no idea about the topic and gives you the contact of a person 3 and etc. So, either you don't find the answer to your question (which is null in the end of the list😂😂), either you receive some explanation from a person 5 or 6. 😂😂😂

Sources:
1. Data Structures and Algorithms in Java. R. Lafore.
2. Football played in local companies.

Hope you enjoyed.
Catch you in the next one.✌️🤓

🇺🇿 Nazariya. Linked List.
Pozitsiya (joy) emas, munosabat.

Keling, linked list (bog'langan ro'yxat) massivlardan nima bilan farq qilishini ko'rib chiqamiz. Massivda har bir element ma'lum bir pozitsiyani egallaydi. Ushbu pozitsiyaga indeks raqami orqali to'g'ridan-to'g'ri foydalanish huquqiga ega bo'lish mumkin. Misolda ko'radigan bo'lsak, bu bir qator uylarga o'xshaydi: siz uning manzilidan foydalanib, ma'lum bir uyni topishingiz mumkin.

Linked list-da ma'lum bir elementni topishning yagona yo'li elementlar zanjiri bo'ylab aylanib chiqishdir. Bu ko'proq insoniy munosabatlarga o'xshaydi. Masalan, Alisherdan Bobur qayerdaligini so‘radingiz. Alisher bilmaydi, lekin Dilafro'z bilishi mumkin deb o'ylaydi, siz borib Dilafro'zdan so'raysiz. Dilafro'z Boburni Sardor bilan ofisdan chiqib ketayotganini ko'rganini aytadi, siz Sardorning qo'l telefoniga qo'ng'iroq qilasiz. U Boburni Jahongirning ishxonasiga tashlab ketdi, shuning uchun... Xullas, tushunarli deb o'ylayman. Siz to'g'ridan-to'g'ri ma'lumotlar elementiga foydalanish huquqini ola olmaysiz; uni topish uchun elementlar orasidagi munosabatlardan foydalanishingiz kerak. Siz birinchi elementdan boshlaysiz, ikkinchisiga yo'l tutasiz, keyin uchinchisiga o'tasiz - qidirayotgan elementni topmaguningizcha.

Yana bir misol o'zimizning tashkilotlarimizdagi "futbol" bo'lishi mumkin: siz operator 1ga qo'ng'iroq qilasiz, u sizdan 2-shaxsga qo'ng'iroq qilishingizni so'raydi. Keyin 2-shaxs mavzu haqida hech qanday tasavvurga ega emasligini aytadi va sizga 3-shaxsning kontaktini beradi va hokazo. Demak, yoki savolingizga javob topolmaysiz (bu ro'yxat oxiridagi null😂😂), yoki 5 yoki 6 kishidan qandaydir tushuntirish olasiz. 😂😂😂

Manbalar:
1. Data Structures and Algorithms in Java. R. Lafore.
2. O'zimizning kompaniyalarda o'ynaladigan futbol.

Sizga yoqdi degan umiddaman.
Keyingi postlarda ko'rishamiz ✌️🤓

🇬🇧 Theory. Linked List.
Time complexity.

Yesterday I made an attempt to explain the Linked List as if I was explaining it to a 12 years old kid. Why? Because I want to deeply understand the data structure. Have you ever heard about Richard Feynman? On of the favorite quotes from him sounds something like: If you want to understand that you got deep knowledge on something, you should be able to explain it to a kid.

This is the reason I try to simplify.
Now, let's move on to the operation complexities of Linked List data structure.

Don't forget that we analyze the unidirectional Linked List.

1. Searching for a node in the list. Since we need to loop over elements until we find our node (or find out that such a node does not exist in the list), we need to do N operations. Where N is the number of elements in the list. It means that Time Complexity for searching in worst case scenario would be O(N).

2. Adding a node to the list. It depends on where we want to add a new node.
- If it is the beginning of the list, then only one set of operations is needed. So, it takes O(1) time to insert to the front.
- If we want to insert into the end of the list, then we loop over the entire list, find the last node (whose next pointer is null) and append a new item to it. Since we loop over all elements, the time complexity is O(N).
- If we want to insert an item after some element, we need to keep looping over elements, until we find what we need. The insertion operation itself takes O(1) time [since we just reorganize the references of nodes], but finding the element takes O(N) time. Thus, adding a node after some element has O(N) time complexity.

3. Removing a node. Node removal has the same complexities as insertion possesses. Keep in mind, that removal operation itself takes O(1) time, because we just need to make the element 1 point to element 3. Thus, element 2 will be out of the list chain.
- If removal is in the beginning of the list, then it takes O(1) time to delete in the front.
- If we want to remove in the end of the list, then we loop over the entire list, find the previous to the last node (whose next pointer is null) and make that previous node point to null. Since we loop over almost all elements, the time complexity is O(N).
- If we want to delete an item after some element, we need to keep looping over elements, until we find what we need. The removal operation itself takes O(1) time as we discussed, but finding the element takes O(N) time. Thus, removing a node after some element has O(N) time complexity.

I think that's it for today :)

Sources:
1. Data Structures and Algorithms in Java. R. Lafore.
2. educative.io
3. Feynman's biography.
✌️🤓

🇺🇿 Nazariya. Linked List.
Vaqt murakkabligi [Time complexity].

Kecha men Linked list-ni xuddi 12 yoshli bolaga tushuntirayotgandek tushuntirishga harakat qildim. Nimaga? Chunki men shu ma'lumotlar tuzilmasini chuqur tushunmoqchiman. Richard Feynman haqida eshitganmisiz? Uning sevimli iqtiboslaridan biri taxminan quydagicha: Agar biror narsa bo'yicha chuqur bilimga ega ekanligingizni tushunmoqchi bo'lsangiz, uni bolaga tushuntirib bera oladigan holda bo'lishingiz kerak.

Shu sababli men soddalashtirishga harakat qilaman.
Endi Linked list ma'lumotlar tuzilmasining operatsiyalari murakkabliklariga o'tamiz.

Shuni unutmangki, biz bir tomonlama bog'langan list-ni ko'rib chiqamiz.

1. List-dagi tugunni qidirish. Biz tugunimizni topganimizcha (yoki list-da bunday tugun yo'qligini aniqlaganimizcha) elementlarni aylanib o'tishimiz kerakligi sababli biz N-ta amalni bajarishimiz kerak. Bu erda N - bu list-dagi elementlar soni. U eng yomon holatda qidirish uchun vaqt murakkabligi O(N) bo'lishini anglatadi.

2. List-ga tugun qo‘shish. Vaqt murakkabligi yangi tugunni qaerga qo'shmoqchi ekanligimizga bog'liq.
- Agar bu list-ning boshi bo'lsa, unda faqat bitta operatsiyalar to'plami kerak bo'ladi. Shunday qilib, old tomonga kiritish uchun O(1) vaqt kerak bo'ladi.
- Agar biz list-ning oxiriga kiritmoqchi bo'lsak, u holda biz butun list-ni aylanib chiqamiz. Oxirgi tugunni topib (keyingi ko'rsatgichi null), unga yangi element qo'shamiz. Biz barcha elementlarni ko'rib chiqqanimiz sababli vaqt murakkabligi O(N) ga teng.
- Agar biror elementdan keyin element qo'shmoqchi bo'lsak, kerakli tugunni topmaganimizcha, elementlar ustida aylanishni davom ettirishimiz kerak. Qo'shish operatsiyasining o'zi O(1) vaqtni oladi [biz faqat tugunlar ko'rsatgichlarini qayta tashkil qilganimiz uchun]. Lekin elementni topish O(N) vaqtni oladi. Shunday qilib, ba'zi elementdan keyin tugunni qo'shish O(N) vaqt murakkabligiga ega.

3. Tugunni olib tashlash. Tugunni olib tashlash qo'shish bilan bir xil murakkabliklarga ega. Shuni yodda tutingki, olib tashlash operatsiyasining o'zi O(1) vaqtni oladi, chunki biz 1-elementni 3-elementiga ulashimiz kerak. Shunday qilib, 2-element list tarkibidan tashqarida qoladi.
- Agar o'chirish list-ning boshida bo'lsa, bunday o'chirish uchun O(1) vaqt kerak bo'ladi.
- Agar biz list oxirida olib tashlashni istasak, u holda biz butun list-ni aylanib chiqamiz, oxirgi tugundan bir qadam oldingi tugunni topamiz (next ko'rsatgichi null bo'ladi) va oldingi tugun ko'rsatgichini null qilamiz. Deyarli barcha elementlarni aylanib chiqqanimiz uchun vaqt murakkabligi O(N) ga teng.
- Agar biror elementdan keyin turgan elementni o‘chirmoqchi bo‘lsak, kerakli elementni topmaganimizcha, elementlar ustida aylanishni davom ettiraveramiz. Olib tashlash operatsiyasining o'zining murakkabligini biz muhokama qilganimizdek O(1) bo'ladi, ammo elementni topish O(N) vaqtni oladi. Shunday qilib, ba'zi elementdan keyin tugunni olib tashlash O(N) vaqt murakkabligiga ega.

Meningcha, bugunga shu :)

Manbalar:
1. Data Structures and Algorithms in Java. R. Lafore.
2. educative.io
3. Feynmanning tarjimai holi.
✌️🤓

🇬🇧 Practice. 535. Encode and Decode TinyURL.

Hi, guys! Let's just have a practice as well. We, as LeetCoders, have try to solve different kinds of problems. So, we will encode and decode URLs today.

🟡 Medium: 535. Encode and Decode TinyURL
👨‍💻 My solution: Java Straightforward Solution | HashMap

I think this one is pretty solveable.
Good luck!✌️🤓

🇺🇿 Amaliyot. 535. Encode and Decode TinyURL.

Hammaga salom! Keling bu safar amaliy mashq ham bajaraylik. Biz LeetCode-chilar sifatida turli xil masalalarni yechishga harakat qilishimiz lozim. Shuning uchun bugun biz URL-larni kod/dekodlaymiz.

🟡 O'rta daraja: 535. Encode and Decode TinyURL
👨‍💻 Mening yechimim: Java Straightforward Solution | HashMap

Bu masalani hamma yecha olishga qodir.
Omad! ✌️🤓

🇬🇧 Practice. 535. Encode and Decode TinyURL.

🟡 Medium: 535. Encode and Decode TinyURL
👨‍💻 My solution: Java Straightforward Solution | HashMap

Hi, guys! Let's check one of the solutions for the problem.

👨‍💻 Task
This is simplified kind of System Design questions. Your task is to build TinyURL encoder and decoder.

👨‍💻 Solution
So, I use a map and an integer counter count to solve the problem. Here, the counter plays a role of database autoincrement.

1. Inside constructor I initialize the map and the counter.
2. Inside encode() method I compose shortUrl (key for the map) which actually is the value of the counter. I put longUrl under this key (shortUrl). Then I increment the counter and return the shortUrl (encoded).
3. Inside decode() I just retrieve and return longUrl by shortUrl.

This is it :)

P.S. You may say:
Q: Why such easy task has medium difficulty?
A: Because finding this solution is more complicated, when you don't know the solution. The perception of this situation is pretty much like Egg of Columbus story. If you read the article or watch a video about this idea, you will know what I mean.

Sources:
1. System Design Interview. Alex Xu. (Chapter 8).

Cheers!✌️🤓

🇺🇿 Amaliyot. 535. Encode and Decode TinyURL.

🟡 O'rta daraja: 535. Encode and Decode TinyURL
👨‍💻 Mening yechimim: Java Straightforward Solution | HashMap

Hammaga salom! Keling bugun kechagi masalamizning yechimlaridan bittasini ko'rib chiqamiz.

👨‍💻 Vazifa
Bizga System Design savollarining soddalashtirilgani berilgan. Bizning vazifamiz - bu URL-ni kodlaydigan va dekodlaydigan class yozishdir.

👨‍💻 Yechim
Men yechimimda map va counter (hisoblagich) ishlataman. Counter strike klassning ichida ma'lumotlar bazasidagi autoincrement kabi vazifani bajaradi.

1. Konstruktor ichida men map va counter o'zgaruvchilarini yarataman.
2. encode() metodi ichida qisqa URL-ni yarataman count + "". Buning qiymati map uchun kalit bo'ladi. Keying map-ning ichida shu kalit va berilgan longUrl-larni joylashtiraman. Bundan so'ng hisoblagichni 1ga oshiraman [bu keyingi longURL uchun kerak]. Va nihoyat kalitni (encoded) qaytaraman.
3. decode() ichida men shortURL kalit bo'yicha map-dan longURL-ni chiqarib olaman va qaytaraman.

Ana shu xolos :)

P.S. Siz so'rashingiz mumkin:
S: Nimaga bunday oson yechimga ega bo'lgan masalaga o'rta qiyinlik darajasi berilgan?
J: Chunki agar yechimni bilmasangiz, uni topish jarayoni qiyinroq kechadi. Bu holat juda ham Egg of Columbus hikoyasini eslatadi. Qiziqib o'qib ko'ring va siz meni tushunasiz degan umiddaman.

Manba:
1. System Design Interview. Alex Xu. (8-bob).

Omad!✌️🤓