Ikki ko'rsatkich (two pointers): ichma-ich siklni bitta siklga aylantirish

Qisqacha: Ikki ko'rsatkich — massivda ikkita indeksni bir vaqtda yuritish usuli. Qarama-qarshi ko'rsatkichlar ikki uchdan markazga yuradi: saralangan narxlarda yig'indisi aniq summaga teng juftlikni O(n²) o'rniga O(n) da topadi. Bir yo'nalishdagi ko'rsatkichlar (o'qish va yozish) takrorlarni yoki keraksiz elementlarni joyida, O(1) qo'shimcha xotira bilan o'chiradi. Tez/sekin ko'rsatkichlar zanjirdagi aylanani xotirasiz topadi. Asosiy shart: har qadamda kamida bitta ko'rsatkich oldinga yuradi va hech qachon orqaga qaytmaydi.

Bu darsda

• Saralangan massivda yig'indisi berilgan songa teng juftlikni ikki ko'rsatkich bilan O(n) da topasiz va nega to'g'ri ishlashini tushuntira olasiz.
• O'qish/yozish ko'rsatkichlari bilan takrorlarni va bekor qilingan buyurtmalarni joyida o'chirasiz.
• Ikki saralangan ro'yxatni bitta tartibli ro'yxatga birlashtirasiz.
• Tez va sekin ko'rsatkich bilan aylanma zanjirni qo'shimcha xotirasiz aniqlaysiz.

Oldin bilishingiz kerak: Massiv xotirada va joyida amallar, Kodning murakkabligini hisoblash, while va do...while, Massiv destructuring.

1. Nega bu kerak?

Mehmon Dilshod aka «Bahor»ga keldi va g'alati iltimos qildi: "Menda 58 000 so'mlik sovg'a kartasi bor. Qoldiq qolmasin — aynan ikkita taom bering, narxi jami 58 000 bo'lsin." Sardor menyuni ochdi. Narxlar arzondan qimmatga qarab yozilgan.

Birinchi xayolga keladigan yechim — hamma juftlarni sinash: birinchi taomni har biri bilan, ikkinchisini har biri bilan... Big-O notatsiyasi darsidan bilamiz: bu taxminan n² ÷ 2 ta solishtirish, O(n²). Menyuda 8 ta taom bo'lsa — 28 ta juft, muammo yo'q. Lekin xuddi shu masala kassa tizimida 16 000 ta to'lov ichida ham chiqadi. U yerda juftlar soni 128 milliondan oshadi.

Bugungi usul shu masalani O(n) ga tushiradi. Bunda bitta muhim narsadan foydalanamiz: narxlar saralangan. O'tgan darsda teskari aylantirishda ikki indeks — left va right — chetlardan markazga yurgan edi. Bugun shu g'oyani butun bir usulga aylantiramiz.

Ko'rsatkich (pointer) — massivdagi joyni eslab turadigan oddiy indeks o'zgaruvchisi (left, right, i). Kitob o'qiyotganda satr ustida turgan barmog'ingizni tasavvur qiling: barmoq — ko'rsatkich, uni surasiz, matn esa joyida qoladi. Ba'zi tillarda (C, C++) "pointer" xotira manzilini bildiradi — bu kursda esa u shunchaki indeks.

2. Qarama-qarshi ko'rsatkichlar

2.1 Sodda yechim

Avval to'g'ri, lekin sekin yechim. U ham kerak: tez yechimni tekshirishda "haqiqat manbai" bo'ladi.

function findPairSlow(prices, target) {
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      if (prices[i] + prices[j] === target) {
        return [prices[i], prices[j]];
      }
    }
  }
  return null; // bunday juft yo'q
}

const prices = [5, 12, 18, 25, 28, 30, 35, 42]; // ming so'm
console.log(findPairSlow(prices, 58)); // [ 28, 30 ]

Ichma-ich ikki sikl, ikkalasi n gacha — O(n²) vaqt, O(1) xotira. E'tibor bering: bu yechim saralanganlikdan umuman foydalanmayapti. Aralash menyuda ham xuddi shunday ishlaydi. Demak, bizda ishlatilmagan ma'lumot bor.

2.2 G'oya: har qadamda bitta narxni chiqarib tashlash

Eng arzon (5) va eng qimmat (42) taomni olaylik: 5 + 42 = 47. Bu 58 dan kam. Endi savol: 5 ming so'mlik taom kim bilan 58 berishi mumkin? Uning eng qimmat sherigi — 42, va u bilan ham yetmadi. Boshqa har qanday sherik 42 dan arzon — yig'indi yanada kichik. Demak, 5 hech kim bilan 58 bermaydi. Uni butunlay tashlaymiz: left++.

Teskari holat ham shunday. Yig'indi 58 dan katta bo'lsa, o'ngdagi taom eng arzon sherigi bilan ham oshib ketdi. U hech kim bilan to'g'ri kelmaydi — right--.

Har qadamda bitta narx butunlay chiqib ketadi. Oynani kuzating — bu hali "shubhali" narxlar oralig'i:

8 ta narxdan 7 qadamda topildi. Hamma juftlar usuli 28 ta juftni ko'rishi mumkin edi. Har qadamda oyna bittaga torayadi, shuning uchun eng yomon holatda ham n − 1 qadam: O(n) vaqt, ikki son — O(1) xotira.

2.3 Nega hech narsani o'tkazib yubormaymiz?

Bu savol muhim: tez yechim faqat to'g'ri bo'lsa qadrli. Isbot g'oyasi oddiy. Biz faqat "aniq javob bo'la olmaydigan" narxni tashlaymiz. Yuqoridagi mulohaza har tashlangan narx uchun ishlaydi: chap narx eng katta sherigi bilan yetmasa, kichikroqlari bilan ham yetmaydi. Demak, javob mavjud bo'lsa, uning ikkala narxi ham oynada qoladi va bir kun left va right aynan ularga keladi.

Bu mulohaza saralanganlikka tayanadi. Saralanmagan massivda "o'ngdagi — eng katta" degan gap yolg'on, usul jimgina xato javob beradi. Saralanmagan ro'yxat uchun ikki yo'l bor: avval saralash (O(n log n) + O(n)) yoki hash bilan yechish — Hash map naqshlari darsida.

2.4 O'lchov

Eng yomon holatni o'lchadik: juftlik yo'q (hamma narx juft son, maqsad — toq son), olcha, har n alohida jarayonda:

Chap ustunda n ikki baravar — vaqt aniq to'rt baravar (× 4,04, × 4,06, × 4,32): kvadratik. O'ng ustunda — taxminan ikki baravar, chiziqli (bu raqamlar juda kichik, shuning uchun tebranadi). 16 000 da farq 900 baravar. Ikki ko'rsatkich million narxda ≈ 7,7 ms, 4 millionda ≈ 28 ms oldi — hamma juftlar usuli bunday hajmda soatlab ishlardi.

2.5 Variant: byudjetdan oshmaydigan eng yaxshi juft

Ertasi kuni Dilshod aka boshqacha so'radi: "Kartamda 50 000 so'm. Aniq 50 bo'lmasa ham mayli — ikkita taom, pulimga sig'sin va iloji boricha ko'p ishlatilsin." Endi "aniq teng" emas, "≤ byudjet ichida eng kattasi" kerak.

Usul deyarli o'sha. Yig'indi sig'sa — uni eslab qolamiz va kattarog'ini izlab left++ qilamiz. Oshib ketsa — right--:

function bestPairWithin(sorted, budget) {
  let left = 0;
  let right = sorted.length - 1;
  let best = null;
  while (left < right) {
    const sum = sorted[left] + sorted[right];
    if (sum <= budget) {
      if (!best || sum > best[0] + best[1]) {
        best = [sorted[left], sorted[right]];
      }
      left++; // sig'di — kattaroq yig'indini sinaymiz
    } else {
      right--; // oshib ketdi — qimmatini tashlaymiz
    }
  }
  return best;
}

const prices = [5, 12, 18, 25, 28, 30, 35, 42];
console.log(bestPairWithin(prices, 50)); // [ 18, 30 ]
console.log(bestPairWithin(prices, 16)); // null

Nega left++ xavfsiz? Yig'indi sig'di, demak shu chap narx uchun eng yaxshi sherik — aynan hozirgi right: undan o'ngdagilar allaqachon "oshib ketadi" deb tashlangan. Chap narxning ishi tugadi. Yana O(n) vaqt va O(1) xotira. 16 000 so'mga esa juft yo'q: eng arzon ikkitasi ham 17 000 — null.

Tekshirib ko'ring: Narxlar [5, 12, 18, 25], maqsad 100. findPair necha qadam qiladi va nima qaytaradi?

3. Bir yo'nalishdagi ko'rsatkichlar: o'qish va yozish

3.1 Takrorlarni joyida o'chirish

Kassa tizimi buyurtma raqamlarini tartib bilan yozadi, lekin internet uzilib qolsa, ba'zi raqamlar ikki-uch marta yozilib qoladi. Takrorlarni olib tashlash kerak — yangi massivsiz, chunki ro'yxat juda katta.

Bu safar ikki ko'rsatkich bir tomonga yuradi. Birinchisi — read: u har elementni o'qiydi va har qadamda oldinga yuradi. Ikkinchisi — write: "toza" qismning chegarasi, faqat yangi raqam topilganda oldinga yuradi. Yozish ko'rsatkichi doim o'qishdan orqada yoki teng. Shuning uchun yozish hali o'qilmagan ma'lumotni buzmaydi:

read massivni bir marta aylanib chiqdi: O(n). Qo'shimcha xotira — ikki son: O(1). Saralanganlik bu yerda ham kerak: takrorlar yonma-yon turgani uchun faqat oxirgi yozilgan raqam bilan solishtirish yetadi.

Natija — massiv uzunligi emas, son (count). Birinchi count ta katak — javob, qolganlari ahamiyatsiz. Ko'p tillarda va LeetCode masalalarida shunday qabul qilingan. Massivning o'zini ham qisqartirmoqchi bo'lsangiz — ids.length = count (Massiv xotirada).

3.2 Shart bo'yicha joyida siqish

O'tgan darsda va'da bergan edik: siklda splice bilan o'chirish O(n²), yozish indeksi bilan esa O(n). Mana o'sha usul — bekor qilingan buyurtmalarni olib tashlash:

function removeCancelled(orders) {
  let write = 0;
  for (const order of orders) {
    if (!order.cancelled) {
      orders[write] = order; // keraklisini oldinga suramiz
      write++;
    }
  }
  orders.length = write; // ortiqcha dumni kesamiz
  return orders;
}

const orders = [
  { id: 101, cancelled: false },
  { id: 102, cancelled: true },
  { id: 103, cancelled: false },
  { id: 104, cancelled: true },
];
console.log(removeCancelled(orders).map((o) => o.id)); // [ 101, 103 ]

Bu — filter ning joyida ishlaydigan ko'rinishi. Tartib saqlanadi: kerakli buyurtmalar o'z ketma-ketligida oldinga suriladi. Har element bir marta ko'chadi — O(n). filter ham O(n), lekin yangi massiv yasaydi. Odatda filter o'qishga qulayroq. Joyida usul massiv juda katta bo'lganda yoki boshqa kod aynan shu massivni ko'rib turganda kerak.

Tekshirib ko'ring: dedupeSorted da ids[read] !== ids[write - 1] o'rniga ids[read] !== ids[read - 1] yozsak, natija o'zgaradimi?

4. Ikki massiv, ikki ko'rsatkich: birlashtirish

Tushlik va kechki smenaning buyurtmalari alohida, har biri vaqt bo'yicha tartiblangan. Kun hisoboti uchun bitta tartibli ro'yxat kerak. Sodda yo'l — birlashtirib, qayta saralash: O((a + b) log(a + b)). Lekin ikkala ro'yxat allaqachon tartibli. Har birida bittadan ko'rsatkich yuritamiz va har qadamda kichigini olamiz:

function mergeSorted(a, b) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) result.push(a[i++]);
    else result.push(b[j++]);
  }
  while (i < a.length) result.push(a[i++]); // a dan qolgani
  while (j < b.length) result.push(b[j++]); // b dan qolgani
  return result;
}

const lunch = ["11:30", "12:00", "13:15"]; // buyurtma vaqtlari
const dinner = ["12:30", "18:00", "19:45"];
console.log(mergeSorted(lunch, dinner).join(" "));

Konsolda:

11:30 12:00 12:30 13:15 18:00 19:45

Vaqtlar "HH:MM" ko'rinishidagi satr: ikki xonali soat va daqiqa bo'lgani uchun satrlarni <= bilan solishtirish vaqt tartibini beradi (Taqqoslash operatorlari). a[i++] — avval a[i] ni oladi, keyin i ni oshiradi (Arifmetik operatorlar). Har qadamda bitta element natijaga o'tadi: jami a + b qadam — O(a + b). <= belgisi muhim: qiymatlar teng bo'lsa, birinchi ro'yxatdagisi oldin keladi — tartib barqaror. Bu birlashtirish — Merge sort algoritmining yuragi.

5. Tez va sekin ko'rsatkich

5.1 Aylanma zanjir

«Bahor» kuryerlari uchun yo'riqnoma: har manzilda "keyingi manzil" yozilgan. next[i] — i-manzildan keyin qayerga borish. −1 — "yo'l tugadi". Kimdir xato yozib qo'ysa, zanjir aylanaga tushadi va kuryer cheksiz aylanib yuradi. Zanjirda aylana bormi?

Sodda yechim — ko'rilgan manzillarni Set ga yozish: takror ko'rsak — aylana. Bu O(n) vaqt va O(n) xotira. Ikki ko'rsatkich bilan xotirani O(1) ga tushirish mumkin. Sekin ko'rsatkich har qadamda bitta manzil yuradi, tez ko'rsatkich — ikkita. Yo'l oxiri bo'lsa, tez ko'rsatkich unga birinchi yetadi. Aylana bo'lsa, ikkalasi aylanaga kiradi. Tez sekinni har qadamda bitta manzilga quvib yetadi — va ular albatta uchrashadi. Bu usul Floyd algoritmi ("toshbaqa va quyon") deb ataladi:

function hasLoop(next, start = 0) {
  let slow = start;
  let fast = start;
  while (fast !== -1 && next[fast] !== -1) {
    slow = next[slow]; // bir qadam
    fast = next[next[fast]]; // ikki qadam
    if (slow === fast) return true; // quvib yetdi — aylana
  }
  return false; // tez ko'rsatkich yo'l oxiriga yetdi
}

console.log(hasLoop([1, 2, 3, -1])); // false
console.log(hasLoop([1, 2, 3, 1])); // true

Ikkinchi misolda yo'l 0 → 1 → 2 → 3 → 1 → 2 → … aylanadi. Tez ko'rsatkich aylana ichida sekinni bir necha qadamda quvib yetadi. Vaqt — O(n): sekin ko'rsatkich aylanaga kirgach, uchrashuvgacha aylana uzunligidan ko'p yurmaydi. Xotira — ikki son.

5.2 Qayerda uchraydi

Tez/sekin ko'rsatkichlar asosan Linked list masalalari da ishlatiladi: zanjirda aylana, ro'yxat o'rtasi (tez oxiriga yetganda sekin — o'rtada), oxiridan k-chi element. Hozir g'oyani massivda ko'rdik — u yerda ham xuddi shunday ishlaydi.

6. Qaysi turini tanlash kerak?

To'rt xil ko'rinishni ko'rdik. Ularning hammasida bitta umumiy qoida bor: ko'rsatkichlar faqat oldinga yuradi va har qadamda kamida bittasi qo'zg'aladi. Shuning uchun jami qadamlar soni ko'rsatkichlar bosib o'tadigan yo'ldan oshmaydi — O(n). Farq — qayerdan boshlashlari va nimaga qarab yurishlarida:

Masala shartidagi so'zlar ham yordam beradi. "Saralangan" va "juft" birga kelsa — qarama-qarshi ko'rsatkichlar haqida o'ylang. "Joyida", "qo'shimcha xotirasiz", "takrorlarni olib tashlang" — o'qish/yozish. "Ikki tartibli ro'yxat" — ikki massivli ko'rinish. "Zanjir", "keyingisi", "aylana" — tez/sekin.

Va eng muhim savol: saralanganlik kerakmi? Qarama-qarshi ko'rsatkichlar va takrorlarni o'chirish — ha, ular tartibga tayanadi. O'qish/yozish bilan shart bo'yicha siqish (removeCancelled) va tez/sekin — yo'q. Massiv saralanmagan bo'lsa, ikki yo'l bor: avval saralash (O(n log n) — umumiy narx shu bo'ladi) yoki hash bilan yechish. Qaysi biri yaxshiroq — xotiraga bog'liq: saralash joyida bo'lishi mumkin, hash esa O(n) xotira oladi.

Tekshirib ko'ring: Kassada bugungi 10 000 ta to'lov bor, tartibsiz. "Yig'indisi aniq 100 000 bo'lgan ikki to'lov bormi?" Ikki ko'rsatkich bilan yechish uchun nima qilish kerak va umumiy murakkablik qancha bo'ladi?

7. Chegaraviy holatlar

Ikki ko'rsatkichli kod chetlarda ko'p sinadi. Har funksiya uchun quyidagilarni tekshiring:

• Bo'sh massiv. findPair([], 58): right = -1, left < right darhol yolg'on — null. dedupeSorted([]) uchun alohida qator yozdik: aks holda write = 1 noto'g'ri javob bo'lardi.
• Bitta element. Juft yo'q — left < right sharti left === right holatni chiqarib tashlaydi. <= yozsangiz, bitta taomni "o'zi bilan juft" deb olishingiz mumkin: [29] va 58 → xato javob.
• Takrorlar. [29, 29] va 58 — bu ikki xil taom, javob [29, 29] to'g'ri. dedupeSorted([7, 7, 7]) → 1.
• Manfiy sonlar. Narx manfiy bo'lmaydi, lekin chegirma yoki kassa tuzatishi bo'lishi mumkin: [-5000, 1000, 9000]. Saralangan bo'lsa, usul o'zgarishsiz ishlaydi — u faqat tartibga tayanadi.

function findPair(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;
  while (left < right) {
    const sum = sorted[left] + sorted[right];
    if (sum === target) return [sorted[left], sorted[right]];
    if (sum < target) left++;
    else right--;
  }
  return null;
}

console.log(findPair([], 58)); // null
console.log(findPair([29], 58)); // null
console.log(findPair([29, 29], 58)); // [ 29, 29 ]
console.log(findPair([-5000, 1000, 9000], 4000)); // [ -5000, 9000 ]

8. Ko'p uchraydigan xatolar

8.1 Saralanmagan massivda qarama-qarshi ko'rsatkichlar

Xato xabari yo'q — shunchaki noto'g'ri null. findPair([30, 5, 28, 42], 58) → null, garchi 30 + 28 = 58 bo'lsa ham. Tuzatish: saralanganlikni shartda yozing (yoki avval toSorted), yoki hash bilan yeching.

8.2 <= va < ni chalkashtirish

while (left <= right) — bitta elementni o'zi bilan juftlaydi. Tuzatish: ikkita turli element kerak bo'lsa — left < right.

8.3 Ko'rsatkichni surishni unutish

Biror tarmoqda left++ yoki right-- yo'q bo'lsa — cheksiz sikl. Tuzatish: har tarmoqda kamida bitta ko'rsatkich yurishini tekshiring. Bu usulning "kafolati" aynan shu.

8.4 Ikkinchi ro'yxat qoldig'ini unutish

mergeSorted da asosiy sikl tugagach, bir ro'yxatda elementlar qolishi mumkin. Oxirgi ikki while siz ular yo'qoladi. Tuzatish: testda uzunliklari har xil ro'yxatlarni sinang.

9. Mashqlar

1-mashq (oson): Qadamlarni qo'lda yuring

Narxlar [8, 15, 22, 30, 41], maqsad 52. findPair ning har qadamida left, right va yig'indini yozing. Nechta qadamda topiladi?

2-mashq (o'rta): Harorat farqlarining kvadratlari

Muzlatgich datchigi kun davomida haroratning me'yordan farqini yozadi, o'sish tartibida: [-7, -3, 0, 2, 5]. Muhandisga shu farqlarning kvadratlari ham o'sish tartibida kerak: [0, 4, 9, 25, 49]. sortedSquares(nums) ni O(n) da yozing — sort siz.

Ishora: eng katta kvadrat doim chetlarning birida (eng manfiy yoki eng musbat). Ikki ko'rsatkichni chetlarga qo'ying va natijani oxiridan to'ldiring: result[pos--]. Mutlaq qiymat — Math.abs (Math obyekti).

function sortedSquares(nums) {
  const result = new Array(nums.length);
  let left = 0;
  let right = nums.length - 1;
  for (let pos = nums.length - 1; pos >= 0; pos--) {
    if (Math.abs(nums[left]) > Math.abs(nums[right])) {
      result[pos] = nums[left] ** 2;
      left++;
    } else {
      result[pos] = nums[right] ** 2;
      right--;
    }
  }
  return result;
}

console.log(sortedSquares([-7, -3, 0, 2, 5])); // [ 0, 4, 9, 25, 49 ]
console.log(sortedSquares([])); // []

3-mashq (qiyin): Ikki ko'rsatkich testlari

kurs/mashqlar/14/07-ikki-korsatkich/ikki.test.mjs faylida darsdagi findPair, dedupeSorted va mergeSorted ni yozing. Ularni sodda yechimlar bilan solishtiring — sodda yechim "haqiqat manbai" (node:test):

1. findPair chegaralar: bo'sh, bitta element, [29, 29], juft yo'q.
2. 200 ta urug'li tasodifiy saralangan massivda (uzunligi 0–30) findPair va findPairSlow juft bor-yo'qligida bir xil javob beradi. Ishora: juftlar bir nechta bo'lsa, ikkalasi har xil juftni qaytarishi mumkin — shuning uchun faqat === null ni solishtiring, yoki topilgan juft yig'indisini tekshiring.
3. dedupeSorted natijasi [...new Set(ids)] bilan bir xil (saralangan massivda).
4. mergeSorted natijasi [...a, ...b].sort((x, y) => x - y) bilan bir xil, uzunliklar har xil.

Urug'li generator — Asosiy murakkablik sinflari darsidagi makeRandom.

// kurs/mashqlar/14/07-ikki-korsatkich/ikki.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

function findPair(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;
  while (left < right) {
    const sum = sorted[left] + sorted[right];
    if (sum === target) return [sorted[left], sorted[right]];
    if (sum < target) left++;
    else right--;
  }
  return null;
}

function findPairSlow(prices, target) {
  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      const sum = prices[i] + prices[j];
      if (sum === target) return [prices[i], prices[j]];
    }
  }
  return null;
}

function dedupeSorted(ids) {
  if (ids.length === 0) return 0;
  let write = 1;
  for (let read = 1; read < ids.length; read++) {
    if (ids[read] !== ids[write - 1]) ids[write++] = ids[read];
  }
  return write;
}

function mergeSorted(a, b) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < a.length && j < b.length) {
    result.push(a[i] <= b[j] ? a[i++] : b[j++]);
  }
  while (i < a.length) result.push(a[i++]);
  while (j < b.length) result.push(b[j++]);
  return result;
}

function makeRandom(seed) {
  return () => (seed = (seed * 16807) % 2147483647);
}
const random = makeRandom(2026);
const sortedList = (n) =>
  Array.from({ length: n }, () => random() % 50)
    .sort((x, y) => x - y);

test("findPair — chegaralar", () => {
  assert.equal(findPair([], 58), null);
  assert.equal(findPair([29], 58), null);
  assert.deepEqual(findPair([29, 29], 58), [29, 29]);
  assert.equal(findPair([5, 12, 18], 100), null);
});

test("findPair sodda yechim bilan bir xil", () => {
  for (let k = 0; k < 200; k++) {
    const list = sortedList(random() % 31);
    const target = random() % 100;
    const fast = findPair(list, target);
    assert.equal(fast === null, findPairSlow(list, target) === null);
    if (fast) assert.equal(fast[0] + fast[1], target);
  }
});

test("dedupeSorted — Set bilan bir xil", () => {
  for (let k = 0; k < 100; k++) {
    const ids = sortedList(random() % 31);
    const expected = [...new Set(ids)];
    const count = dedupeSorted(ids);
    assert.deepEqual(ids.slice(0, count), expected);
  }
});

test("mergeSorted — saralash bilan bir xil", () => {
  for (let k = 0; k < 100; k++) {
    const a = sortedList(random() % 20);
    const b = sortedList(random() % 7);
    const expected = [...a, ...b].sort((x, y) => x - y);
    assert.deepEqual(mergeSorted(a, b), expected);
  }
});

✔ findPair — chegaralar (1.33ms)
✔ findPair sodda yechim bilan bir xil (2.5196ms)
✔ dedupeSorted — Set bilan bir xil (1.5519ms)
✔ mergeSorted — saralash bilan bir xil (0.9211ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 121.0627

4-mashq: Amaliy tajriba — naqshlar ustuni

kurs/mashqlar/14/MURAKKABLIK.md ga "Naqsh" ustunini qo'shing va bugungi to'rt yechimni yozing. Ilgarigi qatorlarga ham naqsh nomini qo'ying (masalan, "hamma juftlar", "ikkiga bo'lish"). Bu ustun keyingi darslarda tez-tez to'ldiriladi — naqshni tanish masala yechishning yarmi.

| Masala | Naqsh | Vaqt | Xotira |
|---|---|---|---|
| Aniq summaga juft (saralangan) | qarama-qarshi ko'rsatkichlar | O(n) | O(1) |
| Takrorlarni o'chirish (saralangan) | o'qish/yozish ko'rsatkichlari | O(n) | O(1) |
| Bekor qilinganlarni o'chirish | o'qish/yozish ko'rsatkichlari | O(n) | O(1) |
| Ikki tartibli ro'yxatni birlashtirish | ikki massiv, ikki ko'rsatkich | O(a + b) | O(a + b) |
| Zanjirda aylana | tez/sekin ko'rsatkich | O(n) | O(1) |

git add 14/MURAKKABLIK.md 14/07-ikki-korsatkich
git commit -m "14/07: ikki ko'rsatkich, sodda yechim bilan testlar"

10. Real ishda

• Ma'lumotlar bazasi. Ikki jadvalni bog'lashda (JOIN) bazalar ko'pincha ikkala tomonni saralab, ikki ko'rsatkich bilan yuradi — "merge join". SQL va bazalarni keyingi qismlarda o'rganamiz.
• Git va diff. Ikki fayl versiyasini solishtirish, ikki tartibli ro'yxatni (masalan, oldingi va yangi buyurtmalar) taqqoslash — ikki ko'rsatkich bilan bir o'tishda.
• Satrlar. Palindrom tekshirish va matnni joyida tozalash — Matn algoritmlari darsida xuddi shu ko'rsatkichlar bilan.
• Intervyu. LeetCode'dagi "Two Sum II", "Remove Duplicates from Sorted Array", "Merge Sorted Array", "Squares of a Sorted Array", "Linked List Cycle" va "3Sum" — hammasi shu darsning naqshlari. "3Sum" da bitta tashqi sikl va ichida ikki ko'rsatkich: O(n³) o'rniga O(n²).

Xulosa

• Ikki ko'rsatkich — ikki indeksni bir vaqtda, faqat oldinga yuritish. Har qadamda kamida bittasi yursa — jami O(n).
• Qarama-qarshi ko'rsatkichlar saralangan massivda har qadamda bitta "imkonsiz" elementni tashlaydi. 16 000 narxda hamma juftlar 99 ms, ikki ko'rsatkich 0,1 ms oldi.
• O'qish/yozish ko'rsatkichlari takrorlarni yoki keraksiz elementlarni joyida, O(1) xotira bilan o'chiradi — siklda splice o'rniga.
• Ikki tartibli ro'yxat O(a + b) da birlashadi; tez/sekin ko'rsatkich aylanani xotirasiz topadi.
• Chegaralar: bo'sh, bitta element, takrorlar, manfiy sonlar; saralanmagan kirish — jim xato.

Keyingi dars: Sliding window (suriluvchi oyna) — ikki ko'rsatkich orasidagi oraliqni "oyna" deb qarab, ketma-ket soatlar tushumi va eng uzun takrorsiz qism kabi masalalarni O(n) da yechish.

Manbalar

• Robert Sedgewick, Kevin Wayne, "Algorithms", 4-nashr, Addison-Wesley, 2011 — "Mergesort" bobi (birlashtirish)
• Donald Knuth, "The Art of Computer Programming", 2-jild — tasodifiy sonlar bobi, aylanani topish (Floyd usuli)
• LeetCode masalalari: 167, 26, 88, 977, 141, 15 — leetcode.com (shartlar bu yerda o'zgartirib berilgan)