Array, String & Hash Map

Kenapa ini penting

Kalau kamu hanya punya waktu untuk menguasai satu pola, kuasai hash map. Di daftar soal populer seperti NeetCode 150 (yang menurut halaman resminya adalah Blind 75 ditambah 75 soal lagi, dikelompokkan dalam 18 kategori), kategori pertama adalah Arrays & Hashing. Alasannya sederhana: banyak soal brute force O(n²) bisa diturunkan menjadi O(n) hanya dengan bertanya "apa yang perlu aku ingat dari elemen-elemen sebelumnya, dan bisakah aku mencarinya dalam O(1)?"

Analogi: kamu penjaga parkir. Cara lambat, setiap kali pemilik datang, kamu berkeliling memeriksa semua mobil. Cara cepat, kamu mencatat "plat nomor → nomor slot" di buku. Buku itulah hash map: kamu menukar sedikit memori (buku catatan) dengan waktu yang jauh lebih cepat.

Konsep inti

Map, Set, atau objek biasa?

Tiga pola hash map yang wajib

1. Complement lookup ("pernah lihat pasanganku?"): Two Sum. Simpan nilai yang sudah lewat; untuk setiap elemen, cek apakah target - x sudah ada.
2. Frequency counter: hitung kemunculan, lalu bandingkan atau cari yang unik. Anagram, first unique character, majority element.
3. Grouping by key: kelompokkan elemen yang punya "tanda tangan" sama. Group anagrams memakai huruf yang diurutkan sebagai kunci.

Bonus: prefix sum + hash map untuk soal "berapa subarray yang jumlahnya k". Simpan berapa kali tiap jumlah prefix muncul; subarray (i, j] berjumlah k kalau prefix[j] - prefix[i] = k.

String di JavaScript

String di JS immutable: s[0] = 'x' diam-diam tidak berpengaruh. Untuk mengubah, ubah dulu jadi array ([...s]), olah, lalu join(''). [...s] juga memisah per code point, sehingga emoji tidak terbelah dua seperti pada s.split(''). Tanyakan ke interviewer: "Can I assume the input is ASCII lowercase letters only?" Jawabannya menentukan apakah array 26 elemen cukup.

Contoh percakapan interview: Two Sum

Begini kira-kira alur yang baik untuk soal Two Sum di phone screen. Perhatikan bahwa kandidat belum menulis satu baris kode pun sampai pendekatannya disepakati.

Interviewer: "Given an array of integers and a target, return the indices of the two numbers that add up to the target."

Candidate: "Just to clarify: is there always exactly one solution? Can I use the same element twice? And can the numbers be negative?"

Interviewer: "Exactly one solution, you can't reuse the same element, and yes, negatives are possible."

Candidate: "Okay. The brute-force approach is to check every pair with two nested loops. That's O(n²) time and O(1) space. Since for each number I'm really asking 'have I already seen the number that completes it?', I can store each value and its index in a hash map. Then for every element I look up target minus the element in constant time. That gives O(n) time and O(n) space. Does that sound good?"

Interviewer: "Sounds good, go ahead."

Candidate: "One detail: I'll check the map before inserting the current number, so I never pair a number with itself."

Kalimat terakhir itu kecil tapi kuat: ia menunjukkan kamu sudah memikirkan edge case sebelum menulis kode. Setelah selesai, kandidat yang baik akan menelusuri [3, 3] dengan target 6 secara lisan untuk membuktikan detail tersebut.

Contoh kode

// Two Sum: kembalikan indeks dua angka yang jumlahnya = target
function twoSumBrute(nums, target) {            // O(n^2) waktu, O(1) ruang
  for (let i = 0; i < nums.length; i++)
    for (let j = i + 1; j < nums.length; j++)
      if (nums[i] + nums[j] === target) return [i, j];
  return [];
}
function twoSum(nums, target) {                 // O(n) waktu, O(n) ruang
  const seen = new Map();                        // nilai -> indeks
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);                        // simpan SETELAH cek, agar tidak memakai elemen yang sama dua kali
  }
  return [];
}
console.log(twoSum([2, 7, 11, 15], 9));   // → [ 0, 1 ]
console.log(twoSum([3, 2, 4], 6));        // → [ 1, 2 ]
console.log(twoSum([3, 3], 6));           // → [ 0, 1 ]
console.log(twoSum([1, 2], 10));          // → []
console.log(twoSumBrute([3, 2, 4], 6));   // → [ 1, 2 ]

// Valid Anagram: frequency counter
function isAnagram(s, t) {
  if (s.length !== t.length) return false;
  const count = new Map();
  for (const ch of s) count.set(ch, (count.get(ch) ?? 0) + 1);
  for (const ch of t) {
    if (!count.get(ch)) return false;   // undefined atau 0
    count.set(ch, count.get(ch) - 1);
  }
  return true;
}
console.log(isAnagram('anagram', 'nagaram'), isAnagram('rat', 'car'), isAnagram('', ''), isAnagram('aacc', 'ccac'));
// → true false true false

// Group Anagrams: kunci = huruf yang diurutkan
function groupAnagrams(words) {
  const groups = new Map();
  for (const w of words) {
    const key = [...w].sort().join('');
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(w);
  }
  return [...groups.values()];
}
console.log(groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']));
// → [ [ 'eat', 'tea', 'ate' ], [ 'tan', 'nat' ], [ 'bat' ] ]
console.log(groupAnagrams(['']), groupAnagrams(['a']));
// → [ [ '' ] ] [ [ 'a' ] ]

// First unique character
function firstUniqChar(s) {
  const freq = {};
  for (const ch of s) freq[ch] = (freq[ch] || 0) + 1;
  for (let i = 0; i < s.length; i++) if (freq[s[i]] === 1) return i;
  return -1;
}
console.log(firstUniqChar('leetcode'), firstUniqChar('loveleetcode'), firstUniqChar('aabb'));
// → 0 2 -1

// Longest consecutive sequence O(n) dengan Set
function longestConsecutive(nums) {
  const set = new Set(nums); let best = 0;
  for (const n of set) {
    if (set.has(n - 1)) continue;     // hanya mulai dari awal deret
    let len = 1; while (set.has(n + len)) len++;
    best = Math.max(best, len);
  }
  return best;
}
console.log(longestConsecutive([100, 4, 200, 1, 3, 2]), longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]), longestConsecutive([]));
// → 4 9 0

Kompleksitas: twoSum O(n)/O(n); isAnagram O(n)/O(k) dengan k jumlah karakter berbeda; groupAnagrams O(n · L log L) dengan L panjang kata (karena sort per kata); longestConsecutive O(n) karena setiap angka hanya "dijalani" sekali dari awal deretnya. Bagian terakhir ini sering ditanya: "Isn't the while loop inside a for loop O(n²)?" Jawabannya: tidak, karena while hanya berjalan dari angka yang merupakan awal deret, jadi total iterasi while di seluruh run paling banyak n.

Kesalahan umum

1. Menyimpan ke map sebelum mengecek di Two Sum. Untuk [3] dengan target 6, kamu akan memakai angka 3 dua kali. Cara benar: cek complement dulu, baru simpan.
2. if (map.get(x)) saat nilainya bisa 0. Indeks 0 dianggap falsy. Cara benar: pakai map.has(x).
3. Memakai objek dengan kunci angka lalu kaget kuncinya string. Object.keys({1: 'a'}) menghasilkan ['1']. Cara benar: pakai Map untuk kunci non-string.
4. Menganggap urutan output tidak penting tanpa bertanya. Cara benar: "Does the order of the groups matter?"
5. Lupa kasus kosong dan duplikat. Selalu uji [], satu elemen, dan elemen kembar.

Latihan

1. Mudah, containsDuplicate(nums): kembalikan true kalau ada angka yang muncul lebih dari sekali. Target O(n).
2. Sedang, majorityElement(nums): kembalikan elemen yang muncul lebih dari n/2 kali (dijamin ada).
3. Menantang, subarraySum(nums, k): hitung jumlah subarray kontigu yang totalnya k. Angka bisa negatif. Target O(n).

// 1. Set: berhenti segera saat ketemu duplikat
const containsDuplicate = nums => { const s = new Set(); for (const n of nums) { if (s.has(n)) return true; s.add(n); } return false; };
console.log(containsDuplicate([1, 2, 3, 1]), containsDuplicate([1, 2, 3, 4]), containsDuplicate([]));
// → true false false

// 2. Frequency counter, kembalikan begitu melewati n/2
function majorityElement(nums) {
  const c = new Map();
  for (const n of nums) { const v = (c.get(n) ?? 0) + 1; c.set(n, v); if (v > nums.length / 2) return n; }
}
console.log(majorityElement([3, 2, 3]), majorityElement([2, 2, 1, 1, 1, 2, 2]), majorityElement([7]));
// → 3 2 7
// Follow-up yang sering ditanya: Boyer-Moore voting memberi O(1) ruang.

// 3. Prefix sum + hash map. Sliding window TIDAK bisa karena ada angka negatif.
function subarraySum(nums, k) {
  const prefixCount = new Map([[0, 1]]);  // prefix 0 muncul sekali (subarray dari awal)
  let sum = 0, count = 0;
  for (const n of nums) {
    sum += n;
    count += prefixCount.get(sum - k) ?? 0;
    prefixCount.set(sum, (prefixCount.get(sum) ?? 0) + 1);
  }
  return count;
}
console.log(subarraySum([1, 1, 1], 2), subarraySum([1, 2, 3], 3), subarraySum([1, -1, 0], 0), subarraySum([], 0));
// → 2 2 3 0

Ringkasan

• Hash map menukar memori O(n) dengan lookup O(1), sering mengubah O(n²) menjadi O(n).
• Tiga pola utama: complement lookup, frequency counter, grouping by key; plus prefix sum + map.
• Pakai Map untuk kunci non-string dan has() untuk mengecek keberadaan.
• String JS immutable; ubah ke array untuk dimodifikasi, [...s] aman untuk emoji.
• Selalu uji input kosong, satu elemen, duplikat, dan angka negatif.