1. Two Sum

Given array of integers, return indices of two numbers that add to target.

Approach: hashmap of value to index, single pass, complement lookup.

#![allow(unused)]
fn main() {
// time O(n), space O(n)
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut num_to_idx: HashMap<i32, i32> = HashMap::new();
    for (i, &num) in nums.iter().enumerate() {
        let guess = target - num;
        if let Some(&x) = num_to_idx.get(&guess) {
            return vec![x, i as i32];
        }
        num_to_idx.insert(num, i as i32);
    }

    vec![]
}

}

14. Longest Common Prefix

Find the longest common prefix string amongst an array of strings.

Vertical scan approach:

#![allow(unused)]
fn main() {
pub fn longest_common_prefix(strs: Vec<String>) -> String {
    let first = strs[0].as_bytes();
    for i in 0..first.len() {
        for j in 1..strs.len() {
            let sb = strs[j].as_bytes();
            if i == sb.len() || first[i] != sb[i] {
                return strs[0][..i].to_string();
            }
        }
    }

    strs[0].clone()
}
}

Sort approach (only first/last need comparing after sorting):

#![allow(unused)]
fn main() {
pub fn longest_common_prefix_sorted(strs: Vec<String>) -> String {
    if strs.len() == 1 {
        return strs[0].clone();
    }

    let mut strs = strs;
    strs.sort();

    let first = strs[0].as_bytes();
    let last = strs[strs.len() - 1].as_bytes();
    for i in 0..first.len() {
        if first[i] != last[i] {
            return strs[0][..i].to_string();
        }
    }

    strs[0].clone()
}
}

27. Remove Element

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums. Return k.

Example 1:

Input: nums = [3,2,2,3], val = 3

Output: k = 2, nums = [2,2,_,_]

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2

Output: k = 5, nums = [0,1,3,0,4,_,_,_]

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

Swap-with-last approach:

i scans forward from the start, n tracks the current logical end of the array. When nums[i] == val, shrink n by one and overwrite nums[i] with whatever sits at the new last index nums[n], then re-check the same i (the swapped-in value hasn’t been checked yet). When nums[i] != val, it’s already in the “keep” region, so just advance i. Elements equal to val end up pushed past index n, and the loop only ever touches each index once as either the scanning pointer or the source of a swap, giving O(k) time (k = nums.len()) and O(1) extra space.

#![allow(unused)]
fn main() {
pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
    let mut i = 0;
    let mut n = nums.len();
    while i < n {
        if nums[i] == val {
            n -= 1;
            nums[i] = nums[n];
        } else {
            i += 1;
        }
    }

    n as i32
}
}

49. Group Anagrams

Group strings that are anagrams of each other.

HashMap with count-vector key:

#![allow(unused)]
fn main() {
// time O(n * k), space O(n * k)
pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
    let mut map: HashMap<Vec<u8>, Vec<String>> = HashMap::with_capacity(strs.len());

    for s in strs {
        let mut vec: Vec<u8> = vec![0; 26];
        for c in s.chars() {
            vec[(c as u8 - b'a') as usize] += 1;
        }
        map.entry(vec).or_default().push(s);
    }

    map.into_values().collect()
}
}

75. Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

Dutch National Flag (three-way partition):

#![allow(unused)]
fn main() {
// Dutch National Flag algorithm
// time O(n), space O(1)
pub fn sort_colors(nums: &mut Vec<i32>) {
    let mut i: usize = 0;
    let mut l: usize = 0;
    let mut r: usize = nums.len();
    while i < r {
        if nums[i] == 0 {
            nums.swap(l, i);
            l += 1;
            i += 1;
        } else if nums[i] == 2 {
            r -= 1;
            nums.swap(i, r);
        } else {
            i += 1;
        }
    }
}
}

Counting sort (bucket):

#![allow(unused)]
fn main() {
// time O(n), space O(1)
pub fn sort_colors_bucket(nums: &mut Vec<i32>) {
    let mut cnt = [0; 3];
    for &num in nums.iter() {
        cnt[num as usize] += 1;
    }

    let mut idx: usize = 0;
    for i in 0..3 {
        while cnt[i] > 0 {
            cnt[i] -= 1;
            nums[idx] = i as i32;
            idx += 1;
        }
    }
}
}

1929. Concatenation of Array

Given array nums, return array ans of length 2n where ans[i] == nums[i] and ans[i + n] == nums[i] for 0 <= i < n.

Approach: allocate result of double size upfront, fill by indexing source with modulo.

#![allow(unused)]
fn main() {
// time O(2n), space O(2n)
pub fn get_concatenation(nums: Vec<i32>) -> Vec<i32> {
    let original_size = nums.len();
    let size = original_size * 2;
    let mut ans: Vec<i32> = Vec::with_capacity(size);
    for i in 0..size {
        ans.push(nums[i % original_size]);
    }

    ans
}
}

242. Valid Anagram

Check if t is an anagram of s.

HashMap approach:

#![allow(unused)]
fn main() {
// time O(n), space O(n)
pub fn is_anagram(s: String, t: String) -> bool {
    let mut letter_counts: HashMap<char, i32> = HashMap::with_capacity(s.len());
    for s_c in s.chars() {
        letter_counts
            .entry(s_c)
            .and_modify(|v| *v += 1)
            .or_insert(1);
    }

    for t_c in t.chars() {
        letter_counts
            .entry(t_c)
            .and_modify(|v| *v -= 1)
            .or_insert(-1);
    }

    letter_counts.values().all(|&v| v == 0)
}
}

Fixed array approach (ASCII lowercase only, faster, O(1) space):

#![allow(unused)]
fn main() {
pub fn is_anagram_array(s: String, t: String) -> bool {
    let mut letter_counts = [0; 26];
    for s_c in s.chars() {
        letter_counts[(s_c as u8 - b'a') as usize] += 1;
    }

    for t_c in t.chars() {
        letter_counts[(t_c as u8 - b'a') as usize] -= 1;
    }

    letter_counts.iter().all(|&v| v == 0)
}
}

347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. The answer may be returned in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Bucket by frequency:

#![allow(unused)]
fn main() {
// time O(n), space O(n)
pub fn top_k_frequent(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let k = k as usize;
    let mut count = HashMap::new();
    let mut freq = vec![vec![]; nums.len() + 1];
    for &num in &nums {
        *count.entry(num).or_insert(0usize) += 1;
    }

    for (&num, &cnt) in &count {
        freq[cnt].push(num);
    }

    let mut res = Vec::new();
    for i in (1..freq.len()).rev() {
        for &num in &freq[i] {
            res.push(num);
            if res.len() == k {
                return res;
            }
        }
    }

    res
}
}

Min-heap of size k:

#![allow(unused)]
fn main() {
// time O(n log k), space O(n)
pub fn top_k_frequent_heap(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let k = k as usize;
    let mut count = HashMap::new();
    for &num in &nums {
        *count.entry(num).or_insert(0i32) += 1;
    }

    let mut heap = BinaryHeap::new();
    for (&num, &freq) in &count {
        heap.push(Reverse((freq, num)));
        if heap.len() > k {
            heap.pop();
        }
    }

    heap.into_iter().map(|Reverse((_, num))| num).collect()
}
}

217. Contains Duplicate

Check if any value appears at least twice in nums.

HashSet approach:

#![allow(unused)]
fn main() {
pub fn contains_duplicate(nums: Vec<i32>) -> bool {
    let mut unique: HashSet<i32> = HashSet::with_capacity(nums.len());
    for num in nums {
        if !unique.insert(num) {
            return true;
        }
    }

    false
}
}

169. Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

HashMap counting:

#![allow(unused)]
fn main() {
// time O(n), space O(n)
pub fn majority_element(nums: Vec<i32>) -> i32 {
    let mut cnt: HashMap<i32, i32> = HashMap::new();
    let mut res = 0;
    let mut max = 0;
    for num in nums {
        let v = cnt.entry(num).or_insert(0);
        *v += 1;
        if *v > max {
            res = num;
            max = *v;
        }
    }

    res
}
}

Sort and take the middle:

#![allow(unused)]
fn main() {
pub fn majority_element_sort(nums: Vec<i32>) -> i32 {
    let mut nums = nums;
    nums.sort();

    nums[nums.len() / 2]
}
}

Boyer-Moore voting:

#![allow(unused)]
fn main() {
// time O(n), space O(1)
pub fn majority_element_boyer_moore(nums: Vec<i32>) -> i32 {
    let mut res = 0;
    let mut cnt = 0;
    for num in nums {
        if cnt == 0 {
            res = num;
        }
        cnt += if num == res { 1 } else { -1 };
    }

    res
}
}

Randomization:

#![allow(unused)]
fn main() {
// time O(n) expected, space O(1)
pub fn majority_element_random(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    loop {
        let guess = nums[rand::rng().random_range(0..n)]; // let guess = nums[rand::random::<usize>() % n]; for leetcode
        let cnt = nums.iter().filter(|&&x| x == guess).count();
        if cnt > n / 2 {
            return guess;
        }
    }
}
}

705. Design HashSet

Design a HashSet without using any built-in hash table libraries.

Implement MyHashSet class:

• void add(key) Inserts the value key into the HashSet.
• bool contains(key) Returns whether the value key exists in the HashSet or not.
• void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.

Example 1:

Input
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
Output
[null, null, null, true, false, null, true, null, false]

Bucket of BTreeSets:

#![allow(unused)]
fn main() {
#[allow(dead_code)]
struct MyHashSet {
    buckets: Vec<BTreeSet<i32>>,
    size: usize,
}

#[allow(dead_code)]
impl MyHashSet {
    // time O(1), space O(n)
    pub fn new() -> Self {
        Self {
            buckets: (0..10_000).map(|_| BTreeSet::new()).collect(),
            size: 10_000,
        }
    }

    fn hash(&self, key: i32) -> usize {
        key as usize % self.size
    }

    // time O(log k), space O(1)
    pub fn add(&mut self, key: i32) {
        let idx = self.hash(key);
        self.buckets[idx].insert(key);
    }

    // time O(log k), space O(1)
    pub fn remove(&mut self, key: i32) {
        let idx = self.hash(key);
        self.buckets[idx].remove(&key);
    }

    // time O(log k), space O(1)
    pub fn contains(&self, key: i32) -> bool {
        let idx = self.hash(key);
        self.buckets[idx].contains(&key)
}

Bucket of Vecs (naive linear scan):

#![allow(unused)]
fn main() {
 */

#[allow(dead_code)]
struct MyHashSetLinkedList {
    buckets: Vec<Vec<i32>>,
}

#[allow(dead_code)]
impl MyHashSetLinkedList {
    // time O(1), space O(n)
    pub fn new() -> Self {
        Self {
            buckets: vec![Vec::new(); 10_000],
        }
    }

    fn hash(key: i32) -> usize {
        key as usize % 10_000
    }

    // time O(k), space O(1)
    pub fn add(&mut self, key: i32) {
        let idx = Self::hash(key);
        if !self.buckets[idx].contains(&key) {
            self.buckets[idx].push(key);
        }
    }

    // time O(k), space O(1)
    pub fn remove(&mut self, key: i32) {
        let idx = Self::hash(key);
        if let Some(i) = self.buckets[idx].iter().position(|&x| x == key) {
            self.buckets[idx].remove(i);
        }
    }

    // time O(k), space O(1)
    pub fn contains(&self, key: i32) -> bool {
        let idx = Self::hash(key);
}

Bitset (not viable for arbitrary i32 — assumes non-negative keys within a fixed upper bound):

#![allow(unused)]
fn main() {
        self.buckets[idx].contains(&key)
    }
}

#[allow(dead_code)]
struct MyHashSetBitset {
    set: Vec<u32>,
}

#[allow(dead_code)]
impl MyHashSetBitset {
    // time O(1), space O(n)
    pub fn new() -> Self {
        Self {
            set: vec![0; 31251],
        }
    }

    fn get_mask(key: i32) -> u32 {
        1 << (key % 32)
    }

    // time O(1), space O(1)
    pub fn add(&mut self, key: i32) {
        self.set[key as usize / 32] |= Self::get_mask(key);
    }

    // time O(1), space O(1)
    pub fn remove(&mut self, key: i32) {
        if self.contains(key) {
            self.set[key as usize / 32] ^= Self::get_mask(key);
        }
    }
}

706. Design HashMap

Design a HashMap without using any built-in hash table libraries.

Implement MyHashMap class:

• MyHashMap() initializes the object with an empty map.
• void put(key, value) inserts a (key, value) pair into the HashMap. If the key already exists, update the corresponding value.
• int get(key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
• void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Example 1:

Input
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]

Bucket of Vecs (linear scan for the key):

#![allow(unused)]
fn main() {
#[allow(dead_code)]
struct MyHashMap {
    buckets: Vec<Vec<(i32, i32)>>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
#[allow(dead_code)]
impl MyHashMap {
    // time O(1), space O(n)
    pub fn new() -> Self {
        Self {
            buckets: vec![Vec::new(); 1000],
        }
    }

    fn hash(key: i32) -> usize {
        key as usize % 1000
    }

    // time O(k), space O(1)
    pub fn put(&mut self, key: i32, value: i32) {
        let idx = Self::hash(key);
        for pair in self.buckets[idx].iter_mut() {
            if pair.0 == key {
                pair.1 = value;
                return;
            }
        }
        self.buckets[idx].push((key, value));
    }

    // time O(k), space O(1)
    pub fn get(&self, key: i32) -> i32 {
        let idx = Self::hash(key);
        for pair in &self.buckets[idx] {
            if pair.0 == key {
                return pair.1;
            }
        }
        -1
    }

    // time O(k), space O(1)
    pub fn remove(&mut self, key: i32) {
        let idx = Self::hash(key);
        if let Some(pos) = self.buckets[idx].iter().position(|p| p.0 == key) {
            self.buckets[idx].remove(pos);
        }
    }
}
}

912. Sort an Array

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Merge sort (ping-pong buffer):

#![allow(unused)]
fn main() {
// time O(n log n), space O(n)
pub fn sort_array(mut nums: Vec<i32>) -> Vec<i32> {
    let mut scratch = nums.clone();
    merge_sort(&mut nums, &mut scratch);
    nums
}

fn merge_sort(dst: &mut [i32], scratch: &mut [i32]) {
    if dst.len() <= 1 {
        return;
    }

    let mid = dst.len() / 2;
    let (dst_left, dst_right) = dst.split_at_mut(mid);
    let (buf_left, buf_right) = scratch.split_at_mut(mid);

    merge_sort(buf_left, dst_left);
    merge_sort(buf_right, dst_right);

    merge(buf_left, buf_right, dst);
}

fn merge(left: &[i32], right: &[i32], out: &mut [i32]) {
    let (mut i, mut j, mut k) = (0, 0, 0);
    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            out[k] = left[i];
            i += 1;
        } else {
            out[k] = right[j];
            j += 1;
        }
        k += 1;
    }

    out[k..].copy_from_slice(if i < left.len() {
        &left[i..]
    } else {
        &right[j..]
    });
}
}

Counting sort:

#![allow(unused)]
fn main() {
// time O(n + range), space O(range)
pub fn sort_array_counting(mut nums: Vec<i32>) -> Vec<i32> {
    let Some((min, max)) = min_max(&nums) else {
        return nums;
    };

    let span = (max as i64 - min as i64 + 1) as usize;
    let mut cnt = vec![0u32; span];

    for &x in &nums {
        cnt[(x - min) as usize] += 1;
    }

    let mut k = 0;
    for (offset, &count) in cnt.iter().enumerate() {
        let count = count as usize;
        nums[k..k + count].fill(min + offset as i32);
        k += count;
    }

    nums
}

fn min_max(v: &[i32]) -> Option<(i32, i32)> {
    let mut it = v.iter().copied();
    let first = it.next()?;
    Some(it.fold((first, first), |(lo, hi), x| (lo.min(x), hi.max(x))))
}
}

Quicksort (randomized pivot, three-way partition):

#![allow(unused)]
fn main() {
// time O(n log n) expected, space O(log n) expected
pub fn sort_array_quicksort(mut nums: Vec<i32>) -> Vec<i32> {
    let mut rng = Rng::new();
    quicksort(&mut nums, &mut rng);
    nums
}

fn quicksort(v: &mut [i32], rng: &mut Rng) {
    if v.len() <= 1 {
        return;
    }

    let pivot = v[rng.below(v.len())];
    let (lt, gt) = partition(v, pivot);

    let (less, rest) = v.split_at_mut(lt);
    let (_equal, greater) = rest.split_at_mut(gt - lt);

    quicksort(less, rng);
    quicksort(greater, rng);
}

fn partition(v: &mut [i32], pivot: i32) -> (usize, usize) {
    let (mut lt, mut i, mut gt) = (0, 0, v.len());
    while i < gt {
        if v[i] < pivot {
            v.swap(lt, i);
            lt += 1;
            i += 1;
        } else if v[i] > pivot {
            gt -= 1;
            v.swap(i, gt);
        } else {
            i += 1;
        }
    }

    (lt, gt)
}

struct Rng(u64);

impl Rng {
    fn new() -> Self {
        Rng(RandomState::new().build_hasher().finish() | 1)
    }

    fn next_u64(&mut self) -> u64 {
        let mut x = self.0;
        x ^= x >> 12;
        x ^= x << 25;
        x ^= x >> 27;
        self.0 = x;
        x.wrapping_mul(0x2545_F491_4F6C_DD1D)
    }

    fn below(&mut self, n: usize) -> usize {
        ((self.next_u64() as u128 * n as u128) >> 64) as usize
    }
}
}

724. Find Pivot Index

Given array nums, return the leftmost pivot index where sum of elements to the left equals sum of elements to the right. Return -1 if none exists.

Approach: compute total sum upfront, then walk left to right tracking running left sum; right sum derived as total - left_sum - nums[i].

#![allow(unused)]
fn main() {
// time O(n), space O(1)
pub fn pivot_index(nums: Vec<i32>) -> i32 {
    let total: i32 = nums.iter().sum();
    let mut left_sum = 0;
    for i in 0..nums.len() {
        let right_sum = total - left_sum - nums[i];
        if left_sum == right_sum {
            return i as i32;
        }
        left_sum += nums[i];
    }

    -1
}
}

1991. Find the Middle Index in Array

Given array nums, return the leftmost middle index where sum of elements to the left equals sum of elements to the right. Return -1 if none exists.

Approach: compute total sum upfront, then walk left to right tracking running left sum; right sum derived as sum - left_sum - nums[i].

#![allow(unused)]
fn main() {
// time O(n), space O(1)
pub fn find_middle_index(nums: Vec<i32>) -> i32 {
    let sum: i32 = nums.iter().sum();
    let mut left_sum: i32 = 0;
    for i in 0..nums.len() {
        let right_sum = sum - left_sum - nums[i];
        if left_sum == right_sum {
            return i as i32;
        }
        left_sum += nums[i];
    }

    -1
}
}