Algoritmy - two pointers

Když je v úloze potřeba procházet polem popř. spojovým seznamem, můžu se zamyslet, jestli by nešlo použít technikou two pointers.

Typické úlohy pro využití této techniky jsou např.:

• hledání dvojice prvků daných vlastností
• odstranění duplicit
• spojení dvou seřazených polí
• hledání části pole splňující určitou podmínku
• hledání podřetězců v řetězci
• posouvání prvků (rotování o několik pozic)

Takové úlohy je možné řešit hrubou silou, ale při použití dvou ukazatelů se velmi sníží časová složitost.

Ukazatele se mohou pohybovat různými způsoby:

1. Směrem k sobě (např. při hledání dvojice prvků dávající určitý součet)
2. Stejným směrem, ale různě rychle (např. při hledání cyklů ve spojových seznamech)
3. Ukazatele se pohybují různě podle podmínek v algoritmu (hledání podřetězce daných vlastností)

Příklady

1. Ukazatele se pohybují směrem k sobě:

Problém: v setříděném poli najdi dvojici prvků, jejichž součet se rovná danému číslu.

Hrubou silou můžu zkoušet všechny kombinace dvojic prvků v poli, dokud nenajdu řešení. Časová složitost bude O(n^2): (pozn. ve všech ukázkách předpokládám, že vstup je validní)

Hrubá síla:

const findTwoNumbers_BruteForce = (array, target) => {
  for (let i = 0; i < array.length - 1; i++) {
    for (let j = i + 1; j < array.length; j++) {
      if (array[i] + array[j] === target) {
        return [i, j];
      }
    }
  }
  return [-1, -1];
};

Dva ukazatele:

Při použití dvou ukazatelů mi stačí projít pole pouze jednou a časová složitost bude O(n):

const findTwoNumbers_TwoPointers = (array, target) => {
  let left = 0; // levy ukazatel
  let right = array.length - 1; // pravy ukazatel
  while (left < right) { // dokud se ukazatele nepotkaji, opakuj nasledujici
    const sum = array[left] + array[right];
    if (sum === target) {
      return [left, right]; // mame reseni
    } else if (sum < target) {
      left++; // soucet je prilis maly - posuneme levy ukazatel doprava
    } else {
      right--; // soucet je prilis velky - posuneme pravy ukazatel doleva
    }
  }
  return [-1, -1]; // pokud jsme nenasli reseni
};

Popis řešení: Na začátku určím oba ukazatele - první a poslední pozice v poli. V každém kroku ověřuju, jestli součet prvků pole na daných pozicích je roven číslu na vstupu (target).

Pokud je roven, našel jsem řešení. Pokud je součet menší, musím posunout levý index doprava (potřebuju do součtu vyšší číslo, než mám teď a vím, že pole je setříděné). Pokud je součet větší, posunu pravý index doleva. Opakuji, dokud se indexy p1 a p2 nepotkají.

V případě, že jsem nenašel řešení, vrátím [-1, -1].

2. Ukazatele se pohybují stejným směrem, ale různě rychle

Problém: ze setříděného pole odstraň všechny duplicitní prvky. Prostorová složitost by měla být O(1) - tzn. s prvky budeme pracovat jen uvnitř pole. Hrubou silou můžu vytvořit něco, co vypadá to ošklivě a má to kvadratickou časovou náročnost:

Hrubá síla

const removeDuplicates_bruteForce = (array) => {
  for (let i = 0; i < array.length - 1; i++) {
    for (let j = i + 1; j < array.length; j++) {
      if (array[i] === array[j]) {
        for (let k = j; k < array.length - 1; k++) {
          array[k] = array[k + 1];
        }
        array.pop();
        i--;
      }
    }
  }
  return array;
};

S použitím dvou ukazatelů:

const removeDuplicates_twoPointers = (array) => {
  if (array.length === 0) return [];
  let lastUnique = 0;

  for (let i = 0; i < array.length - 1; i++) {
    if (array[i] !== array[i + 1]) { // je nasledujici prvek unikatni?
      if (lastUnique + 1 !== i + 1) { // je nasledujici unikatni prvek na spravnem miste?
        array[lastUnique + 1] = array[i + 1];
      }
      lastUnique++;
    }
  }
  array.length = lastUnique + 1; // oriznu pole
  return array;
};

Popis řešení: První ukazatel i prochází polem, zatímco druhý ukazatel lastUnique určuje pozici, na kterou přijde další unikátní prvek pole.

Postupně procházím polem přes index i, a zjišťuju, jestli následující hodnota v poli je shodná s aktuální. (Jsem v setříděném poli, takže mi stačí kontrolovat vždy následující prvek.) Pokud je shodná, pokračuju dál (lastUnique zůstává stejné).

Pokud se následují prvek liší od aktuálního, ověřím, jestli už není na správném místě (např. pro pole [1, 2, 2, 3] je druhý prvek různý od prvního, ale je na správném místě, takže krok array[lastUnique + 1] = array[i + 1] neprovedu. Naopak v případě třetího a čtvrtého prvku tento krok provedu - index i už se posunul na třetí prvek, zatímco lastUnique zůstal na pozici druhého prvku). Při každém dalším unikátním prvku ještě zvýšim ukazatel lastUnique.

Nakonec oříznu pole podle počtu nalezených unikátních prvků.

3. Ukazatele se pohybují různě podle podmínek v algoritmu

Problém: sloučení dvou setříděných polí do jednoho setříděného pole.

Hrubá síla

const mergeSortedArrays_BruteForce = (array1, array2) => {
  let merged = array1.concat(array2);
  merged.sort((a, b) => a - b);
  return merged;
};

Dva ukazatele

const mergeSortedArrays_TwoPointers = (array1, array2) => {
  let p1 = 0;
  let p2 = 0;
  result = [];

  while (p1 < array1.length && p2 < array2.length) {
    if (array1[p1] < array2[p2]) {
      result.push(array1[p1]);
      p1++;
    } else {
      result.push(array2[p2]);
      p2++;
    }
  }
  if (p1 === array1.length) {
    result = result.concat(array2.slice(p2));
  } else {
    result = result.concat(array1.slice(p1));
  }
  return result;
};

Popis řešení: pro každé vstupní pole si nastavím vlastní ukazatel na začátek pole. Ještě si vytvořím pole pro ukládání výsledku.

Porovnávám prvky na aktuálních pozicích obou ukazatelů - když je na ukazateli v prvním poli menší hodnota, než v na ukazateli v druhém poli, vložím do výsledného pole hodnotu z prvního pole a index prvního pole posunu o jedna do prava. V opačném případě vložím do výsledného pole hodnotu z druhého pole a index druhého pole posunu o jedna do prava. Toto celé opakuju, dokud nedojdu na konec jednoho z polí.

Nakonec připojím zbytek pole, ukterého index nedošel až do konce.