Pengenalan Knowing What to Track

State yang disimpan sebuah algoritma menentukan apa yang bisa dia jawab dengan efisien. Saya sering butuh jumlah kemunculan tiap value atau catatan value yang udah pernah muncul. Catatan-catatan ini bisa menggantikan pencarian berulang di input.

Hitung dulu, lalu pakai hasil hitungannya

Frequency counting punya dua fase. Pertama, saya men-scan input dan mencatat seberapa sering tiap value muncul. Lalu saya pakai catatan itu untuk menjawab pertanyaan yang sebenarnya, misalnya mencari duplikat atau membandingkan dua input.

Menurut saya teknik ini berguna untuk mencari value yang paling sering atau paling jarang muncul, mengecek jumlah kemunculan yang pasti, membandingkan dataset, dan mendeteksi duplikat. Tanda umumnya adalah sebuah value jadi penting karena berapa kali dia muncul. Contoh-contoh di bawah memakai pengecekan duplikat dan pengecekan permutasi.

Contoh dan pilihan penyimpanan

Saya pakai frequency counting untuk mencari tahu apakah sebuah array punya duplikat:

function hasDuplicate(nums) {
  const counts = {};

  // Counting phase
  for (let num of nums) {
    counts[num] = (counts[num] || 0) + 1;
  }

  // Utilization phase
  for (let num in counts) {
    if (counts[num] > 1) {
      return true; // Found a duplicate!
    }
  }
  return false;
}

Saya juga memakainya untuk mengecek apakah dua string merupakan permutasi satu sama lain:

function arePermutations(str1, str2) {
  if (str1.length !== str2.length) return false;

  const counts = {};

  // Count characters in first string
  for (let char of str1) {
    counts[char] = (counts[char] || 0) + 1;
  }

  // Decrement for second string
  for (let char of str2) {
    if (!counts[char]) return false;
    counts[char]--;
  }

  // All should be zero if they're permutations
  return Object.values(counts).every((count) => count === 0);
}

Hash map adalah pilihan yang umum. Saya pakai tiap elemen sebagai key dan frekuensinya sebagai value:

const frequency = {};
for (let item of data) {
  frequency[item] = (frequency[item] || 0) + 1;
}

Kalau value-nya integer kecil, sebuah array bisa memakai value itu sebagai index:

const frequency = new Array(26).fill(0); // For lowercase letters
for (let char of str) {
  frequency[char.charCodeAt(0) - "a".charCodeAt(0)]++;
}

Kompleksitas dan checklist

Pass untuk menghitung itu O(n), diikuti dengan scan atas value yang berbeda. Hash map memakai space O(k) untuk k value yang berbeda, sementara array berukuran tetap memakai space yang terikat pada range yang dipilih. Menentukan state yang dibutuhkan sebelum menulis kode bikin sisa solusinya tetap lugas.

Pertama, tentukan value yang nanti harus diambil lagi oleh algoritmanya. Lalu cek apakah sebuah count, membership flag, atau index bisa merepresentasikannya. Pertanyaan itu biasanya mengungkap state terkecil yang berguna.