Buổi 01 — Complexity Analysis & Array

Navigation

← Roadmap-FAANG | → 02-Linked-List-Dummy-Node Giai đoạn: Big Tech Foundation | Độ khó: ⭐⭐

1. Analogy & Context

Ví dụ thực tế

Tìm tên trong danh bạ điện thoại.

$O (N)$ — Linear Search: Lật từng trang một từ đầu đến cuối. 1000 trang = 1000 bước.

$O (lo g N)$ — Binary Search: Mở giữa sách. Tên cần tìm ở phần trước hay sau? Loại đi một nửa. 1000 trang = chỉ 10 bước.

$O (1)$ — Hash lookup: Có index ở cuối sách “N = trang 743”. Trực tiếp đến trang đó.

Insight: Cùng một bài toán, thuật toán khác nhau tạo ra sự khác biệt giữa “instant” và “server timeout”.

Array là gì dưới góc nhìn hardware? Array là vùng nhớ liên tiếp (contiguous memory). Phần tử thứ $i$ nằm ở địa chỉ base_address + i * element_size. Đây chính là lý do random access $O (1)$ — CPU tính thẳng địa chỉ, không cần traverse.

2. The FAANG Standard

Tại sao Senior Engineer phải master Complexity?

Ở FAANG, mọi code review đều có câu hỏi: “What’s the time and space complexity?” Không trả lời được → fail code review, dù code chạy đúng.

Array là foundation của mọi data structure. Heap, Hash Table, Segment Tree đều build trên array. Nếu không hiểu sâu array, mọi DS nâng cao đều sẽ bị “học vẹt”.

Điểm phân biệt Senior vs Junior:

Junior: “It works” ✓
Senior: “It works, time $O (N)$ , space $O (1)$ , và đây là tại sao không thể tốt hơn” ✓✓✓

3. Visual Thinking

3.1 Big O Hierarchy

graph LR
    A["O(1)<br/>Constant"] -->|faster| B["O(log N)<br/>Logarithmic"]
    B --> C["O(N)<br/>Linear"]
    C --> D["O(N log N)<br/>Linearithmic"]
    D --> E["O(N²)<br/>Quadratic"]
    E --> F["O(2ᴺ)<br/>Exponential"]
    F --> G["O(N!)<br/>Factorial"]

    style A fill:#22c55e,color:#fff
    style B fill:#86efac,color:#000
    style C fill:#fde047,color:#000
    style D fill:#fb923c,color:#fff
    style E fill:#f87171,color:#fff
    style F fill:#dc2626,color:#fff
    style G fill:#7f1d1d,color:#fff

3.2 Array Memory Layout

Index:   [0]   [1]   [2]   [3]   [4]
Value:   [10]  [20]  [30]  [40]  [50]
Addr:   0x100 0x104 0x108 0x10C 0x110
         ↑                         ↑
      base_addr              base + 4*4

3.3 Two-Pass Array Pattern

flowchart LR
    subgraph Pass1["Pass 1: Build prefix/state"]
        A[arr[0]] --> B[arr[1]] --> C[arr[2]] --> D[arr[n-1]]
    end
    subgraph Pass2["Pass 2: Answer queries"]
        E[arr[n-1]] --> F[arr[n-2]] --> G["..."] --> H[arr[0]]
    end
    Pass1 --> Pass2

4. TypeScript Template

4.1 Basic Array Operations

/**
 * Demonstrates O(1) vs O(N) array operations.
 * Understanding these fundamentals prevents common interview mistakes.
 */
 
// ✅ O(1) — Random Access
function getElement<T>(arr: T[], index: number): T | undefined {
  return arr[index]; // Direct memory address calculation
}
 
// ✅ O(N) — Linear Search (unsorted array)
function linearSearch<T>(arr: T[], target: T): number {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}
 
// ✅ O(N) — Prefix Sum (classic array pattern)
/**
 * Build prefix sum array để answer range sum queries in O(1).
 * @example prefixSum([1,2,3,4]) → [0,1,3,6,10]
 * Query sum(l, r) = prefix[r+1] - prefix[l]
 */
function buildPrefixSum(nums: number[]): number[] {
  const prefix = new Array(nums.length + 1).fill(0);
  for (let i = 0; i < nums.length; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
  }
  return prefix;
}
 
function rangeSum(prefix: number[], left: number, right: number): number {
  return prefix[right + 1] - prefix[left];
}

4.2 Kadane’s Algorithm — Maximum Subarray

/**
 * Maximum Subarray Sum — LeetCode #53 (Classic FAANG problem)
 *
 * Key insight: Tại mỗi vị trí i, ta có 2 lựa chọn:
 *   1. Extend subarray hiện tại: currentSum + nums[i]
 *   2. Start fresh từ nums[i]
 * → Chọn cái nào lớn hơn.
 *
 * Time: O(N) | Space: O(1)
 */
function maxSubArray(nums: number[]): number {
  let maxSum = nums[0];
  let currentSum = nums[0];
 
  for (let i = 1; i < nums.length; i++) {
    // Extend or start fresh — core of Kadane's
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
 
  return maxSum;
}

4.3 Product Except Self — No Division Trick

/**
 * Product of Array Except Self — LeetCode #238
 *
 * Approach: Two-pass prefix & suffix product.
 * Pass 1 (left→right): result[i] = product of all elements to the LEFT of i
 * Pass 2 (right→left): multiply result[i] by product of all elements to the RIGHT
 *
 * Time: O(N) | Space: O(1) (output array không tính)
 */
function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const result = new Array(n).fill(1);
 
  // Pass 1: prefix products
  let leftProduct = 1;
  for (let i = 0; i < n; i++) {
    result[i] = leftProduct;
    leftProduct *= nums[i];
  }
 
  // Pass 2: multiply by suffix products
  let rightProduct = 1;
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= rightProduct;
    rightProduct *= nums[i];
  }
 
  return result;
}

5. Complexity Deep-Dive

5.1 Time Complexity Comparison

Operation	Array	Linked List	Hash Table
Access by index	$O (1)$	$O (N)$	N/A
Search (unsorted)	$O (N)$	$O (N)$	$O (1)$ avg
Search (sorted)	$O (lo g N)$	$O (N)$	N/A
Insert at end	$O (1)$ amortized	$O (1)$	$O (1)$ avg
Insert at beginning	$O (N)$	$O (1)$	N/A
Delete	$O (N)$	$O (N)$ to find	$O (1)$ avg

5.2 Phân tích Prefix Sum

Brute force range sum:
  For each query (l, r): iterate l → r → O(N) per query
  Q queries: O(Q * N) total

Với Prefix Sum:
  Build: O(N) một lần
  Each query: O(1)
  Q queries: O(N + Q) total → khi Q >> 1, lợi thế là rõ rệt

Khi nào dùng Prefix Sum?

Nhiều range sum/average queries trên static array

“Sum of subarray” hoặc “range query” trong đề

Có thể extend sang 2D prefix sum cho matrix problems

5.3 Amortized Analysis — Dynamic Array

Tại sao Array.push() là $O (1)$ amortized?

Dynamic array double size khi full. Với $N$ push operations:

$N$ operations: $O (1)$ each

Resize events: 1 + 2 + 4 + … + $N /2$ = $O (N)$ total copy work

Amortized per operation: $O (N) / N = O (1)$

6. Edge Cases & Pitfalls

Các bẫy thường gặp — Senior vẫn mắc

1. Off-by-one error (phổ biến nhất)

// ❌ Sai — miss phần tử cuối
for (let i = 0; i < arr.length - 1; i++) { ... }
 
// ✅ Đúng
for (let i = 0; i < arr.length; i++) { ... }

2. Empty array — không check

// ❌ Crash khi arr = []
function maxElement(arr: number[]): number {
  let max = arr[0]; // undefined nếu arr rỗng!
  ...
}
 
// ✅ Guard clause
function maxElement(arr: number[]): number {
  if (arr.length === 0) throw new Error("Empty array");
  let max = arr[0];
  ...
}

3. Integer overflow trong prefix sum

// ❌ Có thể overflow với large inputs (TypeScript dùng float64 nên hiếm hơn)
// Nhưng trong Java/C++: int có thể overflow khi N = 10^5, value = 10^4
// → Dùng long/BigInt
 
// ✅ TypeScript: number là float64, safe up to 2^53 ≈ 9 * 10^15
// Với FAANG problems, thường đủ — nhưng luôn comment lý do

4. Mutating input array mà không nói

// ❌ Silently modifies input — interviewer sẽ hỏi
function process(arr: number[]): void {
  arr.sort(); // MUTATES INPUT!
}
 
// ✅ Explicit về mutation, hoặc tạo copy
function process(arr: readonly number[]): number[] {
  return [...arr].sort((a, b) => a - b); // Clone trước
}

5. Confusing i với arr[i] khi đặt tên

// ❌ Confusing
for (let i = 0; i < arr.length; i++) {
  if (arr[i] > arr[i+1]) { ... } // i là index hay value?
}
 
// ✅ Clear naming
for (let idx = 0; idx < arr.length; idx++) {
  const current = arr[idx];
  const next = arr[idx + 1];
  if (current > next) { ... }
}

7. Pattern Recognition

Signal Words → Array Patterns

Signal trong đề	Pattern	Template
”subarray sum equals K”	Prefix Sum + HashMap	`prefixSum`, `count[sum]++`
”maximum subarray”	Kadane’s Algorithm	`currentSum = max(nums[i], currentSum + nums[i])`
”rotate array k steps”	Reverse trick hoặc Extra array	3 reverses in-place
”find duplicate in [1,N]“	Index as Hash / Floyd’s cycle	`arr[arr[i]] = visited marker`
”merge sorted arrays”	Two Pointers	`i`, `j` trên 2 arrays
”product except self”	Prefix + Suffix pass	Two-pass, O(1) space

8. Top LeetCode Problems

Curated List — Bắt buộc giải trước khi qua buổi tiếp theo

#	Problem	Difficulty	Pattern	Ghi chú
53	Maximum Subarray	Medium	Kadane’s	Bài kinh điển, phải giải được trong 5 phút
238	Product of Array Except Self	Medium	Prefix + Suffix	Không dùng division — test Two-pass thinking
560	Subarray Sum Equals K	Medium	Prefix Sum + HashMap	Kết hợp 2 kỹ thuật
152	Maximum Product Subarray	Medium	Kadane’s variant	Track cả min và max (negative số)
41	First Missing Positive	Hard	Array as Hash	Dùng index làm marker — $O (N)$ , $O (1)$ space

Giải trình bài #41 (Hard) — Why it’s important

/**
 * First Missing Positive — LeetCode #41
 *
 * Key insight: Missing positive trong array độ dài N phải nằm trong [1, N+1].
 * Dùng chính array làm hash table: đặt nums[i] ở đúng vị trí index nums[i]-1.
 *
 * Time: O(N) | Space: O(1) — đây là điểm phân biệt Senior
 */
function firstMissingPositive(nums: number[]): number {
  const n = nums.length;
 
  // Phase 1: Place each number at its correct index
  // nums[i] should be at index nums[i] - 1
  for (let i = 0; i < n; i++) {
    while (
      nums[i] > 0 &&
      nums[i] <= n &&
      nums[nums[i] - 1] !== nums[i]  // Avoid infinite loop on duplicates
    ) {
      // Swap nums[i] to its correct position
      const correctIdx = nums[i] - 1;
      [nums[i], nums[correctIdx]] = [nums[correctIdx], nums[i]];
    }
  }
 
  // Phase 2: Find first position where nums[i] !== i + 1
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) return i + 1;
  }
 
  return n + 1; // All 1..N are present
}

9. Self-Assessment Checklist

Trước khi chuyển sang buổi tiếp theo, hãy confirm bản thân có thể:

Giải thích được sự khác biệt giữa $O (N)$ và $O (N^{2})$ bằng ngôn ngữ người thường
Phân tích Amortized complexity của dynamic array
Code Prefix Sum từ scratch trong 3 phút
Implement Kadane’s algorithm không cần nhìn
Giải LeetCode #238 với $O (1)$ space
Identify được 5 edge cases trước khi code bất kỳ bài array nào

→ Tiếp theo: 02-Linked-List-Dummy-Node — Dummy Node pattern & why it’s elegant

lthieu's notes

Explorer

01-Complexity-and-Array

Buổi 01 — Complexity Analysis & Array

1. Analogy & Context

2. The FAANG Standard

3. Visual Thinking

3.1 Big O Hierarchy

3.2 Array Memory Layout

3.3 Two-Pass Array Pattern

4. TypeScript Template

4.1 Basic Array Operations

4.2 Kadane’s Algorithm — Maximum Subarray

4.3 Product Except Self — No Division Trick

5. Complexity Deep-Dive

5.1 Time Complexity Comparison

5.2 Phân tích Prefix Sum

5.3 Amortized Analysis — Dynamic Array

6. Edge Cases & Pitfalls

7. Pattern Recognition

8. Top LeetCode Problems

Giải trình bài #41 (Hard) — Why it’s important

9. Self-Assessment Checklist

Graph View

Table of Contents

Backlinks