🇬🇧 706. Design HashMap - Explained

Hi, guys! So let's check the solution for previous problem.

🟢 Easy: 706. Design HashMap
👨‍💻 My solution: Java | Built HashMap Based On Array

👨‍💻 Task
We need to build a simple HashMap: add logic into constructor and put(), get(), and remove() methods.

👨‍💻 Analysis
1. I've added an array of lists of pairs. Pair objects will keep their own keys and values. Lists are used for managing collisions.
The array is used for storing values.
2. Inside constructor [MyHashMap()] I initialize the array of size 100 and create empty lists.
3. Inside get():
- int idx = key % 100 - idx here is a result of pseudo hashing operation. I use remainder as a hypothetical hash here.
- by this idx I grab the list from the array.
- inside the for loop I run through all elements of the list until I find a key of a pair which is equal to the given key [parameter]. When such element exists, then I return the value, else - I return -1 [as it is asked in the task description].
4. Inside put():
- finding idx by the same action above.
- grabbing the list with index of idx.
- creating boolean variable which will say if existing pair is replaced.
- I run through all pairs in the found list. If I find a pair with equal key to the given key, then I replace old value with new [given] one and assign true to existingReplaced boolean variable and break the loop. It means that if a value is replaced, then we don't need to add a new pair. However, if we don't find a pair with equal key to the given key, then we just add new pair of key and value to the list. Why? Because it means that a pair with given key doesn't exist and we need to add new pair.
5. Inside remove():
- finding idx by the same action above.
- grabbing the list with index of idx.
- I run through the list and find a pair with a key equal to the given key. If I find such pair, I remove this pair and stop the loop. If such pair is not found, then the list is not changed.

Basically, this is it. More on Hashtables you can find 👉 here.
I hope everything is was clear.🤓
Cheers!✌️

🇺🇿 706. Design HashMap

Hammaga salom! Keling bugun kechagi masalaning yechimini ko'rib chiqamiz.

🟢 Oson daraja: 706. Design HashMap
👨‍💻 Mening yechimim: Java | Built HashMap Based On Array

👨‍💻 Vazifa
Biz oddiy HashMap yasashmiz lozim. Bu degani uning konstruktori, put(), get() va remove() metodlariga kod yozishimiz kerak :).

👨‍💻 Izoh
1. Men ma'lumotlarni saqlash uchun massivni tanladim. Massivning ichida List-lar bo'ladi. List-lar esa kalit va qiymat juftliklardan iborat bo'ladi. List ishlatilishi sababi - bu kolliziya holatlarida juftliklarni List-ga qo'shib qo'yaman.
2. Konstruktor ichida hajmi 100ga teng bo'lgan massiv yaratib, uni har bi indeksi uchun yangi bo'sh bo'lgan list-larni yarataman.
3. get() metodi ichida:
- int idx = key % 100 - bu psevdo xeshlash operatsiyasi. Men berilgan kalitni 100ga [massivning hajmiga] bo'laman va qoldiqni xeshning qiymati sifatida ishlataman.
- shu idx bo'yicha menga kerak bo'lgan list-ni chiqarib olaman.
- for loop-ning ichida olingan list-ning har bir element-juftlikni olib, ularning kalitini berilgan kalitga tengligini tekshiraman. Agar shunday juftlik bo'lsa, men uning qiymatini qaytaraman. Agar bunday juftlik bo'lmasa, -1 [vazifada berilgan] qaytaraman.
4. put() metodi ichida:
- idx-ni huddi tepadagi operatsiya orqali topaman.
- shu idx bo'yicha menga kerak bo'lgan list-ni chiqarib olaman.
- boolean existingReplaced o'zgaruvchisini yarataman. Uning qiymati false teng bo'ladi. Bu o'zgaruvchi bizning massivimizda mavjud bo'lgan juftlikdagi qiymat almashtirilganligini saqlaydi.
- List-ning har bir juftligini ko'rib chiqaman. Agar berilgan kalitga teng kalitlik juftlik topsam, shu juftlikning eski qiymatini yangi [value parameter sifatida berilgan] qiymatga almashtiraman. Keyin existingReplaced-ning qiymatini true qilaman va loop-dan chiqaman. Bu degani yangi juftlik yaratish kerak emas degani. Agar bunday juftlik topilmasa, existingReplaced-ning qiymati false bo'yicha qolaveradi va biz list-ga yangi juftlikni qo'shib qo'yamiz.
5. remove() metodi ichida:
- idx-ni huddi tepadagi operatsiya orqali topaman.
- shu idx bo'yicha menga kerak bo'lgan list-ni chiqarib olaman.
- List-ni aylanib chiqaman. Loop-ning ichida berilgan key kalitga kaliti teng bo'lgan juftlik qidiraman. Agar bunday juftlik topilsa, bu juftlikni list-dan o'chiraman va loop-ni to'xtataman. Agar topilmasa, list o'zgarmaydi.

Hammasi tushunarli bo'ldi degan umiddaman.
Hashtable haqida ko'proq ma'lumot bu yerda 👉 Hastable
Omad!✌️

Not compressed

🇬🇧 1441. Build an Array With Stack Operations

Hi, guys! Let's solve interesting problem today. We need to recover stack operations called based on given array of integers.

🟡 Medium: 1441. Build an Array With Stack Operations
👨‍💻 My solution: Java Simple 0ms Solution

Good luck!✌️

P.S. We will analyze the solution in the next posts as usual.

🇺🇿 1441. Build an Array With Stack Operations

Hammaga salom! Bugun ham qiziqarli masala tayyorlab qo'ydim. Bizning vazifamiz Stack-ning operatsiyalarini berilgan massivga qarab qayta tiklash.

🟡 O'rta daraja: 1441. Build an Array With Stack Operations
👨‍💻 Mening yechimim: Java Simple 0ms Solution

Omad!✌️

P.S. Har doimgidek yechimni keyingi postlarda ko'rib chiqamiz.

🇬🇧 1441. Build an Array With Stack Operations

🟡 Medium: 1441. Build an Array With Stack Operations
👨‍💻 My solution: Java Simple 1ms Solution

Let's solve the problem ;). Before we start I want you to understand count++ from target[count++] expression - link.

👨‍💻 Task
We are given array target and integer n. The array will contain numbers from 1 to n. We need to return the stack operations, using only Push and Pop, needed to build target

👨‍💻 Analysis
You can see that I have a list to keep the actions. On each iteration I add "Push" action.
If target's element with index count is not equal to i (note that i is start from 1), then I add "Pop" action to the list. Why? Because if we have target array filled up with all numbers from 1 to n, then any target[count] will be equal to i. Thus, we will have only "Push" operations added and no "Pop" operation.

However, if target is [1,3], we can see that 2 is missed. It means that we
- push 1,
- push 2,
- pop (2),
- push 3.
In the loop, when i = 2, count is 1.

if (target[count++] != i) {
list.add("Pop");
count--;
}

So, target[1] != 2 is true and we add "Pop" to list and decrement count.
Why? Because target[count++] here count is 1 before operation applied and then it is incremented, i.e. will become 2. When we decrement it, it becomes 1 again.
So, in the next iteration when i = 3, count is 1 again. target[count++] != i here will be false, because target[1] is 3 and this is equal to i. So, we don't add "Pop" operation on this step.

I think this is it and I hope the explanation made it clear.
Peace!✌️

🇺🇿 1441. Build an Array With Stack Operations

🟡 Or'ta daraja: 1441. Build an Array With Stack Operations
👨‍💻 Mening yechimim: Java Simple 1ms Solution

Hammaga salom! Keling shu masalaning yechimini ko'raylik ;). Boshlashimizdan avval target[count++] dagi count++ ni tushunish uchun maqola - havola.

👨‍💻 Vazifa
Bizga integer-lar bilan to'ldirilgan massiv va n soni berilgan. Massiv 1dan n-gacha bo'lgan tartibli sonlar bilan to'ldirilgan. Qaysidir sonlar yo'q bolishi mumkin. Biz shu massivga qarab, Stack-ning Push va Pop operatsiyalarini qaytadan tiklashimiz lozim.

👨‍💻 Izoh
Men String-lardan iborat list yarataman.
Loop-ni 1dan boshlab n-gacha qilaman.
Har bir iteratsiyada (takrorlashda) "Push" harakatini bildiruvchi String-ni qo'shaman.
Agar massivning count indeksida joylashgan elementning qiymati i-ga teng bo'lmasa, unda listga "Pop" String-ni qo'shaman va count-ni 1ga kamaytiraman.
Nimaga deb so'raysizmi?
Chunki agar bizga target massivi 1dan n-gacha hamma sonlar bilan to'ldirilgan holatda berilgan bo'lganida, unda target[count] har doim i-ga teng bo'ldardi va list faqat "Push"-lardan iborat bo'lar edi.

Lekin, agar target [1,3] bo'lsa, 2 o'tkazib yuborilgan. Bu degani harakatlar bunday tartibda bo'ladi:
- push 1,
- push 2,
- pop (2),
- push 3.

Loop-ning ichida, i = 2 va count = 1 holatida:

if (target[count++] != i) {
list.add("Pop");
count--;
}



target[1] != 2

- true bo'ladi, listga "Pop" qo'shiladi va count-ning qiymati 1ga kamayadi.
Nimaga?
Chunki, target[count++] ga qaraganda, count-ning qiymati 1ga teng bo'ladi va operatsiya bajarilgandan so'ng 1ga oshib, 2ga tenglashadi.
count--; - bu yerda count-ni 1ga kamaytiramiz.
Keyingi iteratsiyada i = 3 bo'lganida, count yana 1ga teng bo'ladi.
target[count++] != i - bu ifodaning natijasi false bo'ladi, chunki target[i] = 3 va i ham 3ga teng. Shuning uchun biz "Pop" String-ni listga qo'shmaymiz va loop-ni davom etamiz.

Tushuntirib bera oldim degan umiddaman.
Omad!✌️

🇬🇧 83. Remove Duplicates from Sorted List

Hi, guys! Linked List was the top choice yesterday. Then let's start from practice. Try to solve the following LeetCode problem with Linked List.

🟢 Easy: 83. Remove Duplicates from Sorted List
👨‍💻 My solution: Java From 5% To 76% Time | O(N) Solution

Explanation to be provided. 😉
Good luck!🤓

P.S. Write in the comments whom do you root for in the World Cup Final: France or Argentina?😁

🇺🇿 83. Remove Duplicates from Sorted List

Hammaga salom! Kecha Linked List eng ko'p ovozlar soniga ega bo'lgan ma'lumot tuzilmasi bo'ldi. Keling shu mavzuni amaliy mashqdan boshlaymiz. Quyidagi masalani yechib ko'ring.

🟢 Oson daraja: 83. Remove Duplicates from Sorted List
👨‍💻 Mening yechimim: Java From 5% To 76% Time | O(N) Solution

Keyingi postlarda tahlil qilamiz. 😉
Omad! 🤓

P.S. Aytgancha, bugungi Jahon Chempionat Finalida qaysi terma jamoani qo'llab-quvvatlaysiz: Fransiyanimi yoki Argentinanimi? 😁

🇬🇧 83. Remove Duplicates from Sorted List

Hi, guys! Let's analyze the solution for the problem below.

🟢 Easy: 83. Remove Duplicates from Sorted List
👨‍💻 My solution: Java From 5% To 76% Time | O(N) Solution

👨‍💻 Task
We are given a sorted integer Linked List where we may have duplicates. We need to return a sorted list with unique values.

👨‍💻 Analysis
I'll explain the the second solution from the link above.
First I added the null check for silly cases.
Then I declare two variables to keep previous and current [prev and curr] nodes.
I use while loop for running through the each node of the list: while (curr != null) and curr = curr.next - help me to do this.
Inside the if block [in while loop] I check if value of previous node is different to the value of the current node. If yes, I assign current node to prev variable.
Let's see the example when the list is 1->1->2->2:
Step 1: both prev and curr are referring to head. That's why we don't go into if block.
Step 2: now curr is pointing to the 2nd node with value 1. Since prev is pointing to the 1st node and prev.val equals curr.val, then we don't go inside the if block.
Step 3: now curr is pointing to the 3rd node with value 2. prev.val is not equal to 2 and, that's why, we go inside the if block. Here we make prev.next (1st node's next node) point to the curr (or 3rd node). Then we make prev point to this next node. Thus we keep last unique node for each iteration.
Step 4: curr is pointing to the 4th node and we don't go into if block. Here the while loop ends since curr.next is null.

In the end we make prev.next = null, to make sure that our new unique list ends there. Note that we just change pointers [not the order] inside the nodes of given list. This is done because we keep our result list sorted.

I hope this makes it easier to grasp.
Peace!✌️

🇺🇿 83. Remove Duplicates from Sorted List

Hammaga salom! Keling kechagi masalani tahlil qilib chiqamiz.

🟢 Oson daraja: 83. Remove Duplicates from Sorted List
👨‍💻 Mening yechimim: Java From 5% To 76% Time | O(N) Solution

👨‍💻 Vazifa
Bizga o'sish tartibda integer Linked List berilgan. Uning ichida dublikatlar bo'lishi mumkin. Biz qiymatlari qaytarilmagan va tartiblangan list qaytarishimiz kerak.

👨‍💻 Tahlil
Ikkinchi yechimni tushuntiraman.
Boshida berilgan list-ni null-ga tekshiraman.
Keyin prev [avvalgi] va curr [hozirgi] o'zgaruvchilarini e'lon qilaman.

while (curr != null) va curr = curr.next - Bu kod qismlari list-ni aylanib chiqish uchun ishlatganman.
Keling endi while loop-ning ichidagi if blokga nazar tutamiz. Agar prev.val curr.val-ga teng bo'lmasa, biz if blok-ning ichidagi kodni bajaramiz. prev-ning next ko'rsatgichi curr-ga ko'rsatadigan qilamiz va bundan keyin shu prev-ning o'zi curr-ga ko'rsatadi. Shu harakatlar orqali biz qaytarilmaydigan qiymatli elementlarni bir biri bilan bo'g'laymiz.
Masalan, bizga bunday list berilgan: 1->1->2->2.
1-iteratsiya: prev va curr head-ga ko'rsatib turishibdi. If-ning ichidagi kod bajarilmaydi, chunki prev va curr-larning qiymatlari teng.
2-iteratsiya: endi curr ikkingchi elementni ko'rsatib turibdi. Uning ham qiymati 1ga teng va biz if blok-ning ichidagi kodni bajarmaymiz.
3-iteratsiya: endi curr uchinchi elementni ko'rsatib turibdi. Uning qiymati 2ga teng. Biz if blok-ning ichiga kiramiz, chunki prev.val != curr.val yoki 1 != 2. Bu yerda prev-ning next ko'rsatuvchisini curr-ga ko'rsatib turadigan qilamiz. Boshqa so'zlar bilan aytsak, birinchi elementning next o'zgaruvchisi endi uchinchi element bilan bo'g'laymiz. Keying esa prev o'zgaruvchisini shu uchinchi elementga ko'rsatib turadigan qilamiz. Shu orqali biz qiymati takrorlangan elementlardan faqat bittadan olib qolamiz.
4-iteratsiya: curr to'rtinchi elementga teng va biz if blok-ning ichiga kirmaymiz. Bu yerda iteratsiyalar tugaydi.

Nihoyat, biz prev.next = null ni bajaramiz, chunki yangi list-imiz oxirgi qiymat takrorlanmaydigan elementda tugashi kerak. Biz berilgan tartibda list-ni aylanib chiqib, elementlarni ulaganimiz sababli, yangi list ham o'sish tartibini saqlab qoladi.

Tushunarli bo'ldi degan umiddaman.
Omad!✌️

Sorry, forgot to post this :)
Uzr, buni post qilish esimdan chiqibdi :)

🇬🇧 203. Remove Linked List Elements

Hi, guys! Another day - another Linked List problem :)

🟢 Easy: 203. Remove Linked List Elements
👨‍💻 My solution: Java O(N) solution

Try to write your own O(N) solution.

Good luck!✌️

🇺🇿 203. Remove Linked List Elements

Hammaga salom! Bugun ham Linked List-ga oid masala yechamiz.

🟢 Oson daraja: 203. Remove Linked List Elements
👨‍💻 Mening yechimim: Java O(N) solution

Bu masalada siz list elementlarining qiymati berilgan val-ga teng bo'lmagan elementlardan iborat list qaytarishingiz kerak.
O(N) tezlikka ega yechim yozishga harakat qiling.

Omad!✌️

🇬🇧 203. Remove Linked List Elements

Hi, guys! Let's see the explanation of the solution.

🟢 Easy: 203. Remove Linked List Elements
👨‍💻 My solution: Java O(N) solution

👨‍💻 Task
Your task is to delete all nodes with values equal to the given val.

👨‍💻 Analysis
1. First while loop is used to find a head node which satisfies the conditions.
2. Then I create a pointer for this head -> temp.
3. Inside the second while loop I find nodes whose value is equal to the given val.
Let me give an example here. Let's say we have a list 1->2->2->1 and val = 2.
Since first node's value is not 2, I start the second while loop from the first node.
3.1. Since the second node's val is 2, I make the first node to point to the third node and immediately go to the next iteration. Thus, the first node is not pointing to the second with value = 2.
3.2. Still head is the first node, but next is the third now. In this iteration we have next node's value equal to 2 and, again, I make head.next to point to the next node, i.e. now head (first node) is pointing to the fourth node.
3.3. In the final iteration head.next.val is not 2 and we skip the code block inside if. We just make head = head.next to keep going through the list.
4. Finally, when we go out of the loop, just return temp which is pointing to the new head (if it has changed).

- Why do we need continue inside if block?
- Because in the example above we could finish with list 1->2->1.
- Why?
- Because we check and unmap (delete) a node only once. If there will be several sought values in a row, we would not delete all of them, since we are mapping immediately after one operation instead of check all the following values until we find unequal value to keep.

I hope it made it clear!
Catch you in the next one!✌️😉

🇺🇿 203. Remove Linked List Elements

Hammaga salom! Keling kecha berilgan masalani endi tahlil qilaylik.

🟢 Oson daraja: 203. Remove Linked List Elements
👨‍💻 Mening yechimim: Java O(N) solution

👨‍💻 Vazifa
Vazifamiz berilgan Linked List-dan qiymati val-ga teng bo'lgan hamma elementlarni o'chirish.

👨‍💻 Izoh
1. Birinchi while loop-da takroran list-ning bosh elementini qidiramiz.
2. Keyin shu bosh elementga ko'rsatuvchi ko'rsatgich yarataman temp.
3. Ikkinchi while loop ichida qiymati berilgan val-ga teng elementlarni qidiraman.
Keling shu yerda nima bo'layotganini bitta misolda ko'rib chiqamiz.
Aytaylik, bizga 1->2->2->1 list berilgan va val = 2.
Birinchi elementning qiymati 2ga teng emas va ikkinchi while loop-ni bosh (birinchi elementdan) boshlaymiz.
3.1. Birinchining next yoki ikkinchi elementimizning qiymati 2ga teng. Biz birinchi elementning next ko'rsatgichini keyingisiga ko'rsatadigan qilamiz. Boshqa so'z bilan aytganda, endi birinchi element uchinchiga ko'rsatib turadi. (1->2->1). Continue turgani uchun biz if block-ni ichidanoq keyingi iteratsiyaga ketamiz.
3.2 Keyingi iteratsiyada head hali ham birinchi element va head.next esa uchinchi element. Endi head.next.val ham 2ga teng. Shuning uchun yana head ko'rsatib turgan elementni almashtiramiz. Endi head elementi berilgan listning to'rtinchi elementiga ko'rsatib turadi. (1->1)
3.3. Oxirgi iteratsiyada head.next ning qiymati 2ga teng emas. Shuning uchun if block-ni ichidagi kod bajarilmaydi va head = head.next orqali biz list-ni har doimgidek aylanib chiqish harakatini bajaramiz.
4. Oxirida while loop-dan chiqib bosh elementni (temp orqali saqlab qo'yganmiz) qaytaramiz.

- Nimaga biz continue-ni ishlatdik?
- Chunki agar uni ishlatmaganimizda 1->2->1 list qaytarar edik.
- Nimaga?
- Agar continue ishlatmasak, biz keyingi elementlarni qiymatini faqat bir marta tekshirgan bo'lar edik. Agar bir nechta val ga teng qiymatli element yonma-yon kelsa, biz hammasini o'chirmasligimiz mumkin, chunki biz keyingi qiymati val-ga teng bo'lmagangina elementni hozirgi elementga ulashimiz lozim.

Tushuntira oldim degan umiddaman!
Keyingi postlarda ko'rishguncha!✌️😉