Massiv va string algoritmlari — two pointers, sliding window (3.2-bob)

3-QISM — Algoritm va ma'lumotlar tuzilmasi · 2-mavzu

1. Kirish va motivatsiya

Big-O 3.1-bob o'lchovini bildik; endi uni amalda qo'llaymiz. Massiv 2.7-bob va string 2.6-bob — dasturlashda eng ko'p uchraydigan ma'lumot. Ular ustidagi klassik algoritm naqshlari (ikki ko'rsatkich, sliding window, prefiks yig'indi) — intervyularning va kundalik ishning asosi.

Bu naqshlar — alohida masalalar emas, balki fikrlash shablonlari 0.6-bob. Bittasini o'zlashtirsangiz, yuzlab masalani yechasiz: "ikki ko'rsatkich" — palindrom, juftliklar, saralangan massivni birlashtirish; "sliding window" — eng katta ketma-ketlik, substring masalalari.

O'xshatish: bu naqshlar — duradgorning asosiy harakatlari (arralash, randalash, biriktirish). Har bir mebel boshqacha, lekin asosiy harakatlar bir xil. Algoritm naqshlarini bilsangiz — yangi masala "tanish" ko'rinadi.

Nega muhim?

• Massiv/string — har bir dasturda (ro'yxat, matn, ma'lumot qayta ishlash).
• Bu naqshlar O(n²) yechimni ko'pincha O(n) ga tushiradi 3.1-bob.
• LeetCode/intervyu masalalarining katta qismi shu naqshlarga tayanadi 3.13-bob.

2. Nazariya — chuqur tushuntirish

2.1. Massiv — xotirada qanday yashaydi (0.1)

Massiv — xotirada ketma-ket joylashgan elementlar (0.1: RAM kataklari). Shuning uchun indeks bo'yicha murojaat O(1) — manzil = boshlanish + indeks × element_hajmi (to'g'ridan-to'g'ri hisoblanadi):

  Indeks:   0    1    2    3    4
          ┌────┬────┬────┬────┬────┐
  Massiv: │ 10 │ 20 │ 30 │ 40 │ 50 │   ← ketma-ket xotirada 0.1-bob
          └────┴────┴────┴────┴────┘
  arr[3] → boshlanish + 3 × hajm → DARROV (O(1))

Lekin o'rtaga qo'shish/o'chirish O(n) — qolgan elementlarni surish kerak (3.1 jadvali).

2.2. Ikki ko'rsatkich (two pointers) naqshi

Ikki ko'rsatkich — massiv/stringda ikkita indeks bilan ishlash; ko'pincha O(n²) ni O(n) ga tushiradi:

• Qarama-qarshi (ends): biri boshdan, biri oxiridan — markazga qarab (palindrom, juftlik).
• Bir yo'nalishli (fast/slow): ikkalasi boshdan, har xil tezlikda (dublikat o'chirish).

  Palindrom tekshirish (qarama-qarshi):
  "k a n o k"
   ↑       ↑     chap va o'ng taqqoslanadi, markazga yaqinlashadi
   chap    o'ng

function palindromMi(s) {
  let chap = 0, ong = s.length - 1;
  while (chap < ong) {
    if (s[chap] !== s[ong]) return false;   // mos kelmasa — palindrom emas
    chap++; ong--;                           // markazga
  }
  return true;
}
// O(n) vaqt, O(1) xotira (3.1)

2.3. Sliding window (suriluvchi oyna) naqshi

Sliding window — uzluksiz ketma-ketlik (subarray/substring) ustida ishlash; "oyna"ni surib, qayta hisoblamasdan yangilash:

  Eng katta 3 ta uzluksiz son yig'indisi:
  [2, 1, 5, 1, 3, 2]
   └─────┘             oyna=8 (2+1+5)
      └─────┘          oyna surildi: -2 +1 = 7
         └─────┘       -1 +3 = 9 ← eng katta

function engKattaOyna(arr, k) {
  let oyna = 0;
  for (let i = 0; i < k; i++) oyna += arr[i];   // birinchi oyna
  let max = oyna;
  for (let i = k; i < arr.length; i++) {
    oyna += arr[i] - arr[i - k];   // yangi element qo'shiladi, eski ayriladi (qayta hisoblamasdan!)
    max = Math.max(max, oyna);
  }
  return max;
}
// O(n) — har element bir marta (ichma-ich tsiklsiz — 3.1)

Nega kuchli: har oynani noldan hisoblasak — O(n×k). Surib yangilash — O(n). Bu — qayta hisoblashdan qochish 3.1-bob.

Kadane algoritmi — eng katta yig'indili uzluksiz subarray (oyna kengligi qat'iy emas, o'zgaruvchan). Har bir indeksda savol: "shu elementni oldingi yig'indiga qo'shamizmi yoki undan yangi boshlaymizmi?" Manfiy sonlar bo'lganda ham ishlaydi:

  [-2, 1, -3, 4, -1, 2, 1, -5, 4]
                └──────────┘        eng katta yig'indi = 6 (4-1+2+1)

function engKattaYigindi(arr) {
  let joriy = arr[0], max = arr[0];   // bo'sh massivni alohida tekshirish (0.6)
  for (let i = 1; i < arr.length; i++) {
    joriy = Math.max(arr[i], joriy + arr[i]);   // yangi boshlash yoki davom ettirish
    max = Math.max(max, joriy);                 // eng katta yig'indini yangilab borish
  }
  return max;
}
engKattaYigindi([-2, 1, -3, 4, -1, 2, 1, -5, 4]);   // 6 — O(n), O(1) xotira

G'oya: agar oldingi yig'indi manfiy bo'lsa — uni tashlab, shu elementdan yangi boshlash foydaliroq. Bu — DP ning 3.12-bob eng sodda namunalaridan biri.

2.4. Prefiks yig'indi (prefix sum) naqshi

Oldindan yig'indilarni hisoblab saqlash — keyin istalgan oraliq yig'indisini O(1) da olish:

function prefiksYigindi(arr) {
  const prefiks = [0];
  for (let i = 0; i < arr.length; i++)
    prefiks[i + 1] = prefiks[i] + arr[i];   // har joygacha yig'indi
  return prefiks;
}
// [3,1,4,1,5] → prefiks [0,3,4,8,9,14]
// oraliq [i..j] yig'indisi = prefiks[j+1] - prefiks[i]  → O(1)!

2.5. Hash map bilan tezlashtirish (2.9)

Ko'p massiv masalasi Map/Set bilan O(n²) dan O(n) ga tushadi (3.1, 2.9):

// "Two Sum" — yig'indisi target bo'lgan ikki son indeksi
function twoSum(arr, target) {
  const korilgan = new Map();   // qiymat → indeks
  for (let i = 0; i < arr.length; i++) {
    const kerakli = target - arr[i];
    if (korilgan.has(kerakli))           // juftini ko'rganmizmi? O(1) (2.9)
      return [korilgan.get(kerakli), i];
    korilgan.set(arr[i], i);
  }
  return null;
}
// O(n) — Map bilan (ichma-ich tsikl O(n²) o'rniga — 3.1)

2.6. Asosiy massiv amallari (in-place vs yangi)

• In-place — asl massivni o'zgartirish (O(1) qo'shimcha xotira), lekin mutatsiya 2.7-bob.
• Yangi massiv — immutable (2.7, 2.15), lekin O(n) xotira.

// In-place ag'darish (ikki ko'rsatkich — 2.2)
function agdar(arr) {
  let l = 0, r = arr.length - 1;
  while (l < r) { [arr[l], arr[r]] = [arr[r], arr[l]]; l++; r--; }  // swap (2.8)
  return arr;
}
// Immutable: [...arr].reverse() yoki arr.map(...) (2.7)

2.7. String algoritmlari (2.6)

String — o'zgarmas 2.6-bob, shuning uchun ko'p amal uchun massivga aylantirib ishlanadi:

const harflar = [...s];           // yoki s.split("") (2.6)
const tartiblangan = [...s].sort().join("");   // string saralash (2.6, 2.7)

Klassik string masalalari: palindrom 2.2-bob, anagram (harf sanog'i), substring qidirish, belgi chastotasi (Map — 2.9).

// Anagram tekshirish — harf chastotasi (Map — 2.9)
function anagramMi(a, b) {
  if (a.length !== b.length) return false;   // chegaraviy holat (0.6)
  const sanoq = {};
  for (const ch of a) sanoq[ch] = (sanoq[ch] || 0) + 1;
  for (const ch of b) {
    if (!sanoq[ch]) return false;
    sanoq[ch]--;
  }
  return true;
}
// O(n) — chastotani Map'da sanash (saralash O(n log n) o'rniga)

2.8. Senior Architect: Boyer-Moore Majority Vote va Dutch National Flag (3-Way Partition)

Intervyularda va yuqori samaradorlikka ega ma'lumotlarni qayta ishlashda "Hash Map bilan $O(n)$ xotira" yechimidan ko'ra, $O(1)$ xotirali nafis matematik algoritmlar yuqori baholanadi.

1. Boyer-Moore Majority Vote Algoritmi (O(n) vaqt, O(1) xotira)

Masala: $n$ ta elementli massivda elementlarning yarmidan ko'pini ($> \lfloor n/2 \rfloor$) tashkil qiluvchi "ko'pchilik elementi"ni topish (LeetCode 169).

• Oddiy yechim: Hash Map bilan chastota sanash — $O(n)$ vaqt, lekin $O(n)$ qo'shimcha xotira oladi.
• Boyer-Moore yechimi: $O(n)$ vaqt, atigi $O(1)$ xotira!

G'oya: Ovoz berish jarayoni. Ko'pchilik elementi qolgan barcha turdagi elementlar yig'indisidan ko'p. Shuning uchun turli elementlar bir-birini "bekor" qilganda ham, baribir ko'pchilik elementi tirik qoladi:

function majorityElement(nums) {
  let candidate = null;
  let count = 0;

  for (const num of nums) {
    if (count === 0) {
      candidate = num; // Yangi nomzod
    }
    count += (num === candidate) ? 1 : -1;
  }

  return candidate;
}

console.log(majorityElement([2, 2, 1, 1, 1, 2, 2])); // 2 (O(n) vaqt, O(1) qo'shimcha xotira!)

2. Gollandiya Milliy Bayrog'i (Dutch National Flag — Dijkstra 3-Way Partition)

Edsger Dijkstra tomonidan taklif qilingan klassik algoritm. Masala: Faqat 3 xil qiymatdan iborat massivni (masalan 0, 1, 2 — LeetCode 75: Sort Colors) bir martalik o'tishda ($O(n)$ vaqt) va hech qanday qo'shimcha xotirasiz ($O(1)$ in-place) saralash.

Uch ko'rsatkich ishlatiladi:

• low — $0$ lar tugaydigan chegara.
• mid — hozir tekshirilayotgan element.
• high — $2$ lar boshlanadigan chegara.

function sortColors(nums) {
  let low = 0, mid = 0, high = nums.length - 1;

  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++; // 1 o'z joyida, faqat olg'a
    } else {
      // nums[mid] === 2
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--; // mid oshmaydi, chunki almashtirilgan yangi element hali tekshirilmagan!
    }
  }
  return nums;
}

const arr = [2, 0, 2, 1, 1, 0];
sortColors(arr);
console.log(arr); // [0, 0, 1, 1, 2, 2] — Sof O(n) vaqt, O(1) in-place!

Bu algoritm QuickSort'da ko'p takrorlanuvchi elementlar bo'lganda algoritmning $O(n^2)$ ga degradatsiya bo'lishining oldini oluvchi 3-Way Partitioning asosidir.

3. Asosiy naqshlar — tez ma'lumotnoma

IKKI KO'RSATKICH   — palindrom, juftlik, saralangan birlashtirish (O(n))
SLIDING WINDOW     — uzluksiz subarray/substring (O(n))
KADANE             — eng katta yig'indili uzluksiz subarray (O(n))
PREFIX SUM         — oraliq yig'indilari (hisob O(n), so'rov O(1))
HASH MAP/SET       — qidiruv/dublikat/chastota O(n) ga tushirish 2.9-bob
IN-PLACE SWAP      — ag'darish/tartiblash O(1) xotira

4. Batafsil kod namunalari

Misol 1 — Ikki ko'rsatkich: saralangan massivda juftlik (2.2)

// Saralangan massivda yig'indisi target bo'lgan juftlik
function juftlikTopib(arr, target) {
  let l = 0, r = arr.length - 1;       // qarama-qarshi (2.2)
  while (l < r) {
    const yigindi = arr[l] + arr[r];
    if (yigindi === target) return [arr[l], arr[r]];
    yigindi < target ? l++ : r--;      // kichik bo'lsa chapni surib, katta bo'lsa o'ngni
  }
  return null;
}
juftlikTopib([1, 3, 5, 7, 9], 12);   // [3, 9] — O(n), O(1) xotira

Misol 2 — Sliding window: takrorsiz eng uzun substring (2.3)

function engUzunTakrorsiz(s) {
  const korilgan = new Set();   // oynadagi belgilar (2.9)
  let chap = 0, max = 0;
  for (let ong = 0; ong < s.length; ong++) {
    while (korilgan.has(s[ong])) {     // takror bo'lsa — chapni surib toraytirish
      korilgan.delete(s[chap]); chap++;
    }
    korilgan.add(s[ong]);
    max = Math.max(max, ong - chap + 1);   // oyna kengligi
  }
  return max;
}
engUzunTakrorsiz("abcabcbb");   // 3 ("abc") — O(n)

Misol 3 — Hash map: chastota va eng ko'p uchragan (2.5, 2.9)

function engKopUchragan(arr) {
  const sanoq = new Map();
  for (const x of arr)
    sanoq.set(x, (sanoq.get(x) || 0) + 1);   // chastota (2.9)

  let max = null, maxSon = 0;
  for (const [qiymat, son] of sanoq)          // eng ko'p uchraganini topish
    if (son > maxSon) { max = qiymat; maxSon = son; }
  return max;
}
engKopUchragan([1, 3, 1, 3, 1]);   // 1 — O(n)

Misol 4 — In-place: noldan keyin surish (2.6)

// Barcha 0 larni oxiriga surish (in-place, tartibni saqlab)
function nollarniSur(arr) {
  let yoz = 0;                          // nol bo'lmaganlarni yozish indeksi
  for (let i = 0; i < arr.length; i++)
    if (arr[i] !== 0) arr[yoz++] = arr[i];   // nol bo'lmaganni oldinga
  while (yoz < arr.length) arr[yoz++] = 0;   // qolganini nol bilan to'ldirish
  return arr;
}
nollarniSur([0, 1, 0, 3, 12]);   // [1, 3, 12, 0, 0] — O(n), O(1) xotira

5. To'g'ri va noto'g'ri holatlar

1) Ichma-ich tsikl (naqsh o'rniga)

// ❌ O(n²) — har juftlikni tekshirish (3.1)
for (let i = 0; i < arr.length; i++)
  for (let j = i + 1; j < arr.length; j++)
    if (arr[i] + arr[j] === target) return [i, j];

// ✅ O(n) — hash map (2.5)
const m = new Map();
for (let i = 0; i < arr.length; i++) {
  if (m.has(target - arr[i])) return [m.get(target - arr[i]), i];
  m.set(arr[i], i);
}

2) Stringni tsiklda += bilan qurish (katta hajmda)

// ❌ string o'zgarmas — har += yangi string (sekin — 2.6)
let r = "";
for (const ch of s) r += ch.toUpperCase();

// ✅ massivga yig'ib, join (2.7)
const r = [...s].map(ch => ch.toUpperCase()).join("");

3) Sliding window'ni har safar noldan hisoblash

// ❌ O(n×k) — har oynani qayta yig'ish
// ✅ surib yangilash: +yangi -eski (O(n) — 2.3)
oyna += arr[i] - arr[i - k];

4) Chegaraviy holatlarni unutish (0.6)

// ❌ bo'sh massiv, bitta element, uzunlik teng emas — tekshirilmagan
// ✅ boshida tekshiring
if (arr.length === 0) return null;
if (a.length !== b.length) return false;   // anagram (2.7)

6. Keng tarqalgan xatolar va yechimlari

Xato 1 — Off-by-one (chegara xatosi)

Sababi: < vs <=, indeks chegarasi (0.6, 2.2). Yechimi: qo'lda kichik misolda tekshiring; ikki ko'rsatkichda while (l < r) (teng bo'lganda to'xtaydi).

Xato 2 — undefined element (chegaradan tashqari)

Sababi: arr[i] mavjud bo'lmagan indeks 2.7-bob. Yechimi: indeks arr.length ichida ekanini tekshiring; sliding window'da i - k >= 0.

Xato 3 — String'ni massiv kabi o'zgartirish

s[0] = "X";   // ❌ ishlamaydi — string o'zgarmas (2.6)

Sababi: string immutable 2.6-bob. Yechimi: [...s] (massivga), o'zgartiring, join 2.7-bob.

Xato 4 — Katta nda O(n²) muzlash

Sababi: ichma-ich tsikl 3.1-bob. Yechimi: ikki ko'rsatkich/sliding window/hash map naqshi (3-bo'lim).

Xato 5 — Mutatsiya kutilmagan natija

Sababi: in-place algoritm asl massivni o'zgartirdi 2.7-bob. Yechimi: nusxa kerak bo'lsa [...arr]; ataylab in-place bo'lsa hujjatlang.

7. Integratsiya — bu mavzu stack'ning qayerida uchraydi

• Big-O 3.1-bob: bu naqshlar O(n²) ni O(n) ga tushiradi.
• Array/String/Map/Set (2.6, 2.7, 2.9): asosiy vositalar.
• Saralash/qidiruv (3.9, 3.10): ko'p naqsh saralangan massivga tayanadi.
• Masala yechish 3.13-bob: LeetCode masalalarining asosi shu naqshlar.
• Backend ma'lumot qayta ishlash (5, 6): DB natijalarini filtrlash/tahlil.
• DP 3.12-bob: prefiks yig'indi DP ning kirishi.

8. Eng yaxshi amaliyotlar (best practices)

• Naqshni taning: uzluksiz oraliq → sliding window; saralangan/juftlik → ikki ko'rsatkich; qidiruv/dublikat → hash map.
• Avval Big-O ni o'ylang 3.1-bob — ichma-ich tsikldan qoching.
• Chegaraviy holatlarni boshida tekshiring 0.6-bob: bo'sh, bitta, teng emas.
• String uchun massivga aylantiring ([...s]), tsiklda += qilmang 2.6-bob.
• In-place vs immutable ni ongli tanlang 2.7-bob.
• Qo'lda kichik misolda yuring 0.6-bob — off-by-one'ni topadi.
• Hash map — eng kuchli qurol ko'p massiv masalasida 2.9-bob.

9. Amaliy loyiha: "Algoritm Naqshlari To'plami"

Massiv/string naqshlarini amalda mustahkamlovchi masalalar to'plami.

Maqsad

Ikki ko'rsatkich, sliding window, prefiks yig'indi va hash map naqshlarini qo'llab, har masala uchun Big-O ni aniqlash 3.1-bob.

Talablar (requirements)

Har masala uchun: pseudokod 0.6-bob, yechim, Big-O tahlili, chegaraviy holatlar:

1. Palindrom (ikki ko'rsatkich — 2.2): bo'sh/bitta belgi, bo'shliq/registr.
2. Two Sum (hash map — 2.5): juftlik yo'q holat.
3. Eng uzun takrorsiz substring (sliding window — Misol 2).
4. Anagram (chastota — 2.7): uzunlik teng emas.
5. Eng katta k-uzunlikdagi yig'indi (sliding window — 2.3).
6. Eng katta yig'indili subarray (Kadane — 2.3): manfiy sonli holat.
7. Oraliq yig'indisi (prefiks sum — 2.4): bir nechta so'rov.
8. Nollarni surish (in-place — Misol 4).
9. Eng ko'p uchragan element (Map — Misol 3).
10. Har yechim uchun O(n²) "sodda" versiya bilan solishtiring (qaysi tezroq va nega).

Maslahatlar (hint)

• Avval pseudokod, keyin kod 0.6-bob.
• Ikki ko'rsatkich: while (l < r); sliding window: Set/yig'indi yangilash.
• Two Sum/anagram: Map/object chastota 2.9-bob.
• Chegaraviy holatlarni boshida 0.6-bob.
• Har masala uchun "n 10x → vaqt necha barobar?" 3.1-bob.

"Tayyor" mezonlari (acceptance criteria)

• 9 masala ishlaydi, har biri pseudokod bilan.
• To'g'ri naqsh ishlatilgan (ikki ko'rsatkich/window/hash map).
• Har yechim O(n) yoki O(n log n) (sodda O(n²) emas).
• Chegaraviy holatlar tekshirilgan.
• Big-O tahlili har masala uchun yozilgan.
• In-place masala asl massivni to'g'ri o'zgartiradi.

Yechim kodi ataylab berilmagan — bu loyihani o'zingiz yozib ko'ring.

10. Xulosa va keyingi bobga ko'prik

Bu bobda massiv va string ustidagi klassik algoritm naqshlarini o'rgandik:

• Massiv — xotirada ketma-ket 0.1-bob; indeks O(1), o'rta qo'shish/o'chirish O(n).
• Ikki ko'rsatkich — qarama-qarshi yoki fast/slow; palindrom, juftlik (O(n), O(1) xotira).
• Sliding window — uzluksiz oraliq; surib yangilash (qayta hisoblamasdan, O(n)).
• Kadane — eng katta yig'indili subarray; manfiy sonli holatda ham O(n).
• Prefiks yig'indi — oraliq so'rovlari O(1).
• Hash map/set 2.9-bob — qidiruv/dublikat/chastotani O(n) ga tushiradi.
• Best: naqshni taning, Big-O ni o'ylang, chegaraviy holatlarni tekshiring.

Keyingi bob — 3.3-bob: Linked List. Massiv — ketma-ket xotira (indeks tez, o'rta o'zgartirish sekin). Linked List — boshqa yondashuv: elementlar xotirada tarqoq, lekin "ko'rsatkich" bilan bog'langan; bosh/o'rtaga qo'shish/o'chirish O(1). Bu — birinchi "ko'rsatkichli" ma'lumotlar tuzilmasi.

Foydalanilgan rasmiy/ishonchli manbalar

• bigocheatsheet.com — massiv operatsiyalari murakkabligi
• MDN Web Docs — Array, String metodlari (2.6, 2.7)
• Universal CS — two pointers, sliding window, prefix sum naqshlari