Array &
String

2.1 Array internals — bên trong array là gì?

Khi nói "array", lập trình viên C/C++ hiểu khác lập trình viên JS. Hãy phân biệt rõ vì điều này ảnh hưởng đến cách bạn nói về Big-O trong phỏng vấn.

Array trong C/C++ — cố định, contiguous

• Kích thước cố định khi khai báo
• Phần tử nằm liên tiếp trong RAM (contiguous memory)
• Truy cập arr[i] = base_address + i × sizeof(type) → O(1) thật sự
• Tất cả phần tử cùng kiểu (homogeneous)

Array trong JS — dynamic, heterogeneous

• Kích thước thay đổi được (push, pop, splice...)
• Có thể chứa nhiều kiểu khác nhau: [1, "hello", true, {a: 1}]
• Bên trong, V8 tối ưu hai kiểu lưu trữ:
  • Packed/Holey Smi: array chỉ chứa số nguyên nhỏ → lưu liên tiếp như C array
  • Dictionary mode: khi array thưa hoặc có lỗ → chuyển sang lưu giống object

// Packed elements (nhanh nhất)
const a = [1, 2, 3, 4, 5];

// Holey array (V8 deopt - chậm hơn)
const b = [1, 2, 3];
b[100] = 100;  // tạo "lỗ" → array trở thành holey

// Mixed types (chậm nhất)
const c = [1, "two", true, {}];

2.2 Big-O của các thao tác Array

Bảng này (đã xuất hiện ở Chương 1, ôn lại):

// ❌ SAI — chạy O(n²)
while (queue.length) {
  const item = queue.shift();
  process(item);
}

// ✅ ĐÚNG — dùng index thủ công, O(n)
let head = 0;
while (head < queue.length) {
  process(queue[head]);
  head++;
}

2.3 Pattern: Two Pointers — vũ khí số 1

Ý tưởng: dùng 2 con trỏ (index) di chuyển trên array để giảm O(n²) xuống O(n). Hai biến thể chính:

1. Opposite direction (đối nghịch): một con trỏ ở đầu, một ở cuối, di chuyển vào giữa.
2. Same direction (cùng hướng): cả hai cùng đi từ trái sang phải, một nhanh một chậm.

2.3.1 Opposite direction — Two Sum trên mảng đã sort

Bài toán: Cho mảng đã sort tăng dần và target. Tìm 2 số có tổng = target.

// Brute force — O(n²)
function twoSumBrute(arr, target) {
  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];
    }
  }
  return null;
}

// Two pointers — O(n) khi mảng đã sort
function twoSumPtr(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo < hi) {
    const sum = arr[lo] + arr[hi];
    if (sum === target) return [lo, hi];
    if (sum < target) lo++;   // cần tổng lớn hơn → đẩy lo phải
    else                hi--;  // cần tổng nhỏ hơn → kéo hi trái
  }
  return null;
}

Tại sao đúng?

• Nếu arr[lo] + arr[hi] < target: arr[hi] là phần tử lớn nhất còn lại, nên arr[lo] không thể là đáp án (ghép với bất kỳ phần tử nào khác đều < target). Bỏ lo.
• Tương tự khi tổng > target: bỏ hi.

Visualizer: Two Pointers

Tìm tổng = 13 trong [1, 3, 5, 7, 9, 11]:

1 + 11 = 12 < 13 → lo++

3 + 11 = 14 > 13 → hi--

3 + 9 = 12 < 13 → lo++

5 + 9 = 14 > 13 → hi--

5 + 7 = 12... à không phải 13. Trong ví dụ này không có cặp tổng 13. Nhưng cách di chuyển bạn đã thấy.

2.3.2 Same direction — Remove duplicates in-place

Bài toán: Mảng đã sort, xoá phần tử trùng tại chỗ, trả về độ dài mới.

// Two pointers cùng hướng — O(n)
function removeDuplicates(arr) {
  if (arr.length === 0) return 0;
  let slow = 0;  // vị trí ghi
  for (let fast = 1; fast < arr.length; fast++) {
    if (arr[fast] !== arr[slow]) {
      slow++;
      arr[slow] = arr[fast];
    }
  }
  return slow + 1;  // độ dài mới
}

// Demo:
// arr = [1, 1, 2, 2, 3]
// slow=0 fast=1: arr[1]=1 == arr[0]=1 → bỏ qua
// slow=0 fast=2: arr[2]=2 != arr[0]=1 → slow=1, arr[1]=2
// slow=1 fast=3: arr[3]=2 == arr[1]=2 → bỏ qua
// slow=1 fast=4: arr[4]=3 != arr[1]=2 → slow=2, arr[2]=3
// Kết quả: arr = [1, 2, 3, ...], length = 3

Khi nào dùng Two Pointers?

• Mảng đã sort + tìm cặp/bộ ba có tổng/hiệu nhất định
• Đảo ngược mảng/chuỗi tại chỗ
• Loại bỏ phần tử / lấy phần tử duy nhất tại chỗ
• Kiểm tra palindrome
• Container with most water, trapping rain water

2.4 Pattern: Sliding Window — cửa sổ trượt

Ý tưởng: duy trì 1 "cửa sổ" liên tiếp (subarray) trên mảng, trượt cửa sổ để tìm subarray tốt nhất theo điều kiện. Hai biến thể:

1. Fixed-size window: kích thước cửa sổ cố định k.
2. Variable-size window: kích thước thay đổi theo điều kiện.

2.4.1 Fixed window — Tổng max của subarray có k phần tử

// Brute force — O(n × k)
function maxSumK(arr, k) {
  let max = -Infinity;
  for (let i = 0; i <= arr.length - k; i++) {
    let sum = 0;
    for (let j = i; j < i + k; j++) sum += arr[j];
    max = Math.max(max, sum);
  }
  return max;
}

// Sliding window — O(n)
function maxSumKWindow(arr, k) {
  let sum = 0;
  // Tính tổng cửa sổ đầu tiên
  for (let i = 0; i < k; i++) sum += arr[i];
  let max = sum;
  // Trượt cửa sổ: thêm phần tử mới, bỏ phần tử cũ
  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k];
    max = Math.max(max, sum);
  }
  return max;
}

2.4.2 Variable window — Longest Substring Without Repeating

Bài toán kinh điển: tìm substring dài nhất không có ký tự lặp.

// Sliding window + hash set — O(n)
function lengthOfLongestSubstring(s) {
  const seen = new Set();
  let left = 0, max = 0;
  for (let right = 0; right < s.length; right++) {
    // Thu nhỏ cửa sổ từ trái cho đến khi không còn ký tự lặp
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);
    max = Math.max(max, right - left + 1);
  }
  return max;
}

// Demo: s = "abcabcbb"
// right=0 'a': seen={a}, max=1
// right=1 'b': seen={a,b}, max=2
// right=2 'c': seen={a,b,c}, max=3
// right=3 'a': 'a' đã có → xoá s[left=0]='a', seen={b,c}; thêm 'a' → seen={b,c,a}, window [1,3]
// ...

Template Sliding Window biến đổi

function slidingWindow(arr, isValid) {
  let left = 0;
  let result = 0;  // hoặc khởi tạo phù hợp
  for (let right = 0; right < arr.length; right++) {
    // Mở rộng cửa sổ: thêm arr[right] vào state
    addToWindow(arr[right]);

    // Thu nhỏ cửa sổ nếu vi phạm điều kiện
    while (!isValid()) {
      removeFromWindow(arr[left]);
      left++;
    }

    // Cập nhật kết quả
    result = Math.max(result, right - left + 1);
  }
  return result;
}

Khi nào dùng Sliding Window?

• Bài toán tìm subarray/substring "dài nhất" / "ngắn nhất" / "chứa đúng k phần tử khác nhau"
• Tổng/tích/đếm trong cửa sổ
• Substring chứa các ký tự nhất định
• Bất kỳ bài nào cần "khoảng liên tiếp"

2.5 Prefix Sum — tính tổng đoạn trong O(1)

Ý tưởng: tiền xử lý mảng trong O(n) để sau đó trả lời tổng từ index i đến j trong O(1) cho mọi truy vấn.

// Khởi tạo prefix sum
function buildPrefix(arr) {
  const prefix = [0];  // prefix[0] = 0 (sentinel)
  for (let i = 0; i < arr.length; i++) {
    prefix.push(prefix[i] + arr[i]);
  }
  return prefix;
}

// arr   = [3, 1, 4, 1, 5, 9, 2, 6]
// prefix= [0, 3, 4, 8, 9, 14, 23, 25, 31]
//          ^idx 0 1 2 3 4  5   6   7   8

// Tổng từ index i đến j (inclusive) = prefix[j+1] - prefix[i]
function sumRange(prefix, i, j) {
  return prefix[j + 1] - prefix[i];
}

// Vd: tổng từ index 2 đến 5 = 4+1+5+9 = 19
//   = prefix[6] - prefix[2] = 23 - 4 = 19 ✓

Bài toán: Subarray Sum Equals K

Đếm số subarray có tổng = k. Đây là bài cực kinh điển, hỏi rất nhiều.

// Brute force — O(n²)
function subarraySumBrute(arr, k) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    let sum = 0;
    for (let j = i; j < arr.length; j++) {
      sum += arr[j];
      if (sum === k) count++;
    }
  }
  return count;
}

// Prefix sum + Hash Map — O(n)
// Ý tưởng: nếu prefix[j+1] - prefix[i] = k → prefix[i] = prefix[j+1] - k
// Đếm xem prefix[i] đã xuất hiện bao nhiêu lần trong các prefix trước
function subarraySum(arr, k) {
  const map = new Map();
  map.set(0, 1);  // prefix sum 0 đã xuất hiện 1 lần (trước khi bắt đầu)
  let sum = 0, count = 0;
  for (const x of arr) {
    sum += x;
    if (map.has(sum - k)) count += map.get(sum - k);
    map.set(sum, (map.get(sum) || 0) + 1);
  }
  return count;
}

2D Prefix Sum

Áp dụng tương tự cho ma trận: tổng vùng chữ nhật trong O(1) sau O(m·n) preprocessing.

function build2DPrefix(matrix) {
  const m = matrix.length, n = matrix[0].length;
  const p = Array.from({length: m + 1}, () => Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + matrix[i-1][j-1];
    }
  }
  return p;
}

// Tổng vùng [r1..r2][c1..c2]
function sumRegion(p, r1, c1, r2, c2) {
  return p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1];
}

2.6 Difference Array — range update O(1)

Anh em song sinh của Prefix Sum. Difference array dùng để cập nhật một đoạn mảng trong O(1), sau đó dựng lại mảng cuối trong O(n).

// Bài toán: cho mảng arr, có Q truy vấn dạng "thêm v vào tất cả arr[l..r]"
// Sau Q truy vấn, in mảng cuối.

// Brute force — O(Q × n)
// Difference array — O(Q + n)

function rangeUpdate(arr, queries) {
  const n = arr.length;
  const diff = new Array(n + 1).fill(0);

  // Mỗi query (l, r, v):
  // diff[l] += v, diff[r+1] -= v
  for (const [l, r, v] of queries) {
    diff[l] += v;
    diff[r + 1] -= v;
  }

  // Dựng lại bằng prefix sum của diff
  let acc = 0;
  for (let i = 0; i < n; i++) {
    acc += diff[i];
    arr[i] += acc;
  }
  return arr;
}

// Demo:
// arr = [0, 0, 0, 0, 0], queries = [[1,3,5], [0,2,2]]
// Sau query 1: arr nên là [0, 5, 5, 5, 0]
// Sau query 2: arr nên là [2, 7, 7, 5, 0]
// Difference array: diff = [2, 5, 0, -5, 0, -2]
// Prefix: 2, 7, 7, 2, 2, 0 → arr cuối = [2, 7, 7, 2, 2] (≈ ý tưởng)

2.7 String trong JavaScript

Tính chất quan trọng

• Immutable: không thể thay đổi tại chỗ. s[0] = 'A' không có hiệu lực.
• UTF-16 encoding: mỗi ký tự thường là 1 code unit (16 bit), nhưng emoji có thể chiếm 2.
• Concatenation tốn kém: s + t tạo string mới → tránh trong vòng lặp lớn.

// ❌ SAI — tạo n string mới, O(n²) tổng cộng
function joinSlow(words) {
  let s = '';
  for (const w of words) s += w;
  return s;
}

// ✅ ĐÚNG — dùng Array + join, O(n)
function joinFast(words) {
  return words.join('');
}

// ✅ ĐÚNG — dùng template literal hoặc Array.push + join
const parts = [];
for (const w of words) parts.push(w);
const s = parts.join('');

Các phương thức quan trọng

Convert string ↔ array

// String → Array để dùng các method array
const arr = "hello".split("");        // ["h","e","l","l","o"]
const arr2 = [..."hello"];            // tương tự
const arr3 = Array.from("hello");     // tương tự

// Array → String
const s = ["h","e","l","l","o"].join("");  // "hello"

// Đảo ngược string (vì string immutable, phải qua array)
const reversed = "hello".split("").reverse().join("");  // "olleh"

const s = "👋hello";
s.length;              // 7 (emoji chiếm 2 code unit!)
s[0];                  // '\uD83D' — half emoji, hỏng
[...s][0];             // '👋' — đúng, vì spread chia theo Unicode
s.charAt(0);           // '\uD83D' — vẫn hỏng
[...s].length;         // 6 — đúng số ký tự "thấy được"

2.8 String Matching — tìm pattern trong text

Naive (Brute Force) — O(n·m)

function naiveSearch(text, pattern) {
  const n = text.length, m = pattern.length;
  for (let i = 0; i <= n - m; i++) {
    let j = 0;
    while (j < m && text[i + j] === pattern[j]) j++;
    if (j === m) return i;
  }
  return -1;
}

KMP (Knuth-Morris-Pratt) — O(n+m)

Dùng "failure function" để khi mismatch, không phải bắt đầu lại từ đầu pattern. Chi tiết KMP sẽ học sâu ở chương String advanced nâng cao (tham khảo).

function buildLPS(pattern) {
  const lps = new Array(pattern.length).fill(0);
  let len = 0, i = 1;
  while (i < pattern.length) {
    if (pattern[i] === pattern[len]) {
      lps[i++] = ++len;
    } else if (len > 0) {
      len = lps[len - 1];
    } else {
      lps[i++] = 0;
    }
  }
  return lps;
}

function kmpSearch(text, pattern) {
  const lps = buildLPS(pattern);
  let i = 0, j = 0;
  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i++; j++;
      if (j === pattern.length) return i - j;
    } else if (j > 0) {
      j = lps[j - 1];
    } else {
      i++;
    }
  }
  return -1;
}

Bài tập

// Input:  [1, 2, 3, 4, 5]
// Output: [5, 4, 3, 2, 1]

"A man, a plan, a canal: Panama" → true
"race a car"                      → false

arr = [2, 1, 5, 1, 3, 2], k = 3 → 9 (5+1+3)

s = "ADOBECODEBANC", t = "ABC" → "BANC"

[1,2,3,4] → [24,12,8,6]

Tổng kết chương 2

• ✅ Array trong JS có thể chậm bất ngờ với shift/unshift/splice — nhớ Big-O từng method
• ✅ Two Pointers: giảm O(n²) → O(n) cho bài cặp/bộ ba trên mảng sort
• ✅ Sliding Window: tốt cho bài "subarray/substring liên tiếp" với điều kiện
• ✅ Prefix Sum: range query O(1) sau O(n) preprocessing
• ✅ Difference Array: range update O(1)
• ✅ String trong JS immutable — không concat trong vòng lặp lớn, dùng arr.join('')
• ✅ Cẩn thận với Unicode/emoji — dùng [...str] thay str[i]