Day 1 — Arrays, Hashing & Time Complexity

Learning Objectives

• Nắm vững cách đo lường hiệu suất thuật toán qua Big O Notation.
• Phân biệt Static Array và Dynamic Array (Vector) trong bộ nhớ.
• Sử dụng HashSet để tối ưu hóa tìm kiếm từ O(n^2) xuống O(n).

Key Concepts & Glossary

Các thuật ngữ quan trọng:

• Static Array: Mảng có kích thước cố định, nằm trên Stack.
• Dynamic Array (Vec): Mảng có thể co giãn, dữ liệu nằm trên Heap, quản lý bởi một pointer trên Stack.
• Amortized Time Complexity: Độ phức tạp "trung bình tích lũy". Ví dụ: push vào Vector thường là O(1), nhưng khi đầy sẽ tốn O(n) để cấp phát lại, trung bình vẫn coi là O(1).
• Hashing Function: Hàm biến một giá trị đầu vào thành một chỉ số duy nhất trong bộ nhớ.

Example Implementation

Cargo.toml

[package]
name = "algo01_arrays_hashing"
version = "0.1.0"
edition = "2024"

[dependencies]
# No external crates needed for basic exercises

src/main.rs

use std::collections::HashSet;

fn main() {
    let nums = vec![1, 2, 3, 1];
    
    // Task: Check for duplicates (LeetCode 217)
    let has_duplicate = contains_duplicate(&nums);
    println!("Has duplicate: {has_duplicate}");

    // Task: Valid Anagram (LeetCode 242)
    let s = String::from("anagram");
    let t = String::from("nagaram");
    println!("Is anagram: {}", is_anagram(s, t));
}

/// O(n) approach using a HashSet
fn contains_duplicate(nums: &[i32]) -> bool {
    let mut seen = HashSet::with_capacity(nums.len());
    for &num in nums {
        // insert returns false if the value was already present
        if !seen.insert(num) {
            return true;
        }
    }
    false
}

/// O(n) approach using a Frequency Table (Array of 26 integers)
fn is_anagram(s: String, t: String) -> bool {
    if s.len() != t.len() { 
        return false; 
    }
    
    let mut counts = [0i32; 26];
    
    // Use zip to iterate through both strings simultaneously in O(n)
    for (sb, tb) in s.bytes().zip(t.bytes()) {
        counts[(sb - b'a') as usize] += 1;
        counts[(tb - b'a') as usize] -= 1;
    }
    
    // Ensure all frequencies are zero
    counts.iter().all(|&x| x == 0)
}

Hands-on Exercises

1. two_sum(nums: Vec, target: i32) -> Vec Tìm chỉ số của hai số có tổng bằng target. Sử dụng HashMap để đạt O(n). Ví dụ: [2, 7, 11, 15], target = 9 -> [0, 1].
2. is_alphanumeric_palindrome(s: &str) -> bool Kiểm tra chuỗi đối xứng, bỏ qua ký tự đặc biệt và hoa thường. Sử dụng kỹ thuật Two Pointers. Ví dụ: "A man, a plan, a canal: Panama" -> true.
3. replace_elements(arr: Vec) -> Vec Thay thế mỗi phần tử bằng phần tử lớn nhất bên phải nó. Phần tử cuối cùng thay bằng -1. Ví dụ: [17, 18, 5, 4, 6, 1] -> [18, 6, 6, 6, 1, -1].

Common Pitfalls & Debugging Tips

Q&A — Common Questions

Q1. Tại sao HashSet trong Rust đôi khi chạy chậm hơn C++?

• Mặc định Rust dùng SipHash để chống tấn công HashDoS. Nếu bạn cần tốc độ tối đa cho các bài tập thuật toán (nơi không lo bị tấn công), bạn có thể dùng FxHash từ crate rustc-hash.

Q2. Khi nào nên dùng Sorting thay vì HashMap?

• Khi bộ nhớ (Space) bị giới hạn cực kỳ khắt khe. Sorting thường tốn O(1) hoặc O(log n) bộ nhớ phụ trợ, trong khi HashMap tốn O(n) để lưu các keys.

Wisdom Note