Problem Solving

// Restated: best profit from one buy then one later sell; 0 if prices only fall.
// Input: a slice of prices (may be empty). Output: u32, never negative.
fn max_profit(prices: &[u32]) -> u32 {
    let mut lowest = u32::MAX;
    let mut best = 0;
    for &price in prices {
        lowest = lowest.min(price);             // cheapest buy so far
        best = best.max(price - lowest);        // sell today? (price >= lowest, so no underflow)
    }
    best
}

fn main() {
    println!("{}", max_profit(&[7, 1, 5, 3, 6, 4])); // normal: buy 1, sell 6
    println!("{}", max_profit(&[7, 6, 4, 3, 1]));    // only falls
    println!("{}", max_profit(&[]));                 // empty
    println!("{}", max_profit(&[5]));                // one day
}

fn is_palindrome(s: &str) -> bool {
    let cleaned: Vec<char> = s
        .chars()
        .filter(|c| c.is_alphanumeric())
        .map(|c| c.to_ascii_lowercase())
        .collect();
    cleaned.iter().eq(cleaned.iter().rev())
}

fn main() {
    // (input, expected): the small cases, written down before the code
    let cases = [
        ("", true),                              // empty
        ("a", true),                             // one char
        ("ab", false),                           // smallest false case
        ("Aba", true),                           // case
        ("A man, a plan, a canal: Panama", true),
        ("race a car", false),
        (".,", true),                            // only punctuation
    ];
    let mut failed = 0;
    for (input, expected) in cases {
        let got = is_palindrome(input);
        if got != expected {
            failed += 1;
            println!("FAIL {:?}: expected {}, got {}", input, expected, got);
        }
    }
    println!("{} passed, {} failed", cases.len() - failed, failed);
}

use std::collections::HashSet;

fn has_duplicate_nested(a: &[u32], ops: &mut u64) -> bool {   // O(n^2)
    for i in 0..a.len() {
        for j in i + 1..a.len() {
            *ops += 1;
            if a[i] == a[j] {
                return true;
            }
        }
    }
    false
}

fn has_duplicate_set(a: &[u32], ops: &mut u64) -> bool {      // O(n)
    let mut seen = HashSet::new();
    for &x in a {
        *ops += 1;
        if !seen.insert(x) {       // insert returns false if x was already there
            return true;
        }
    }
    false
}

fn main() {
    for n in [1_000u32, 10_000] {
        let a: Vec<u32> = (0..n).collect();          // no duplicates: worst case
        let (mut nested, mut set) = (0, 0);
        has_duplicate_nested(&a, &mut nested);
        has_duplicate_set(&a, &mut set);
        println!("n={}  nested={}  set={}", n, nested, set);
    }
}

// Sorted input: positions of two numbers that add up to target.
fn pair_sum(a: &[i32], target: i32) -> Option<(usize, usize)> {
    if a.is_empty() {
        return None;
    }
    let (mut i, mut j) = (0, a.len() - 1);
    while i < j {
        let sum = a[i] + a[j];
        if sum == target {
            return Some((i, j));
        } else if sum < target {
            i += 1;               // need bigger: move the left pointer up
        } else {
            j -= 1;               // need smaller: move the right pointer down
        }
    }
    None
}

fn main() {
    let a = [1, 3, 4, 6, 8, 11];
    println!("{:?}", pair_sum(&a, 10));
    println!("{:?}", pair_sum(&a, 2));
    println!("{:?}", pair_sum(&[], 5));
}

// Fixed window: biggest sum of k consecutive values.
fn max_window_sum(a: &[i64], k: usize) -> Option<i64> {
    if k == 0 || k > a.len() {
        return None;
    }
    let mut sum: i64 = a[..k].iter().sum();
    let mut best = sum;
    for i in k..a.len() {
        sum += a[i] - a[i - k];          // slide: add the new right, drop the old left
        best = best.max(sum);
    }
    Some(best)
}

// Variable window: length of the longest run of bytes with no repeat.
fn longest_unique(s: &str) -> usize {
    let bytes = s.as_bytes();
    let mut last_seen = [None::<usize>; 256];  // byte -> last index it appeared at
    let (mut left, mut best) = (0, 0);
    for (right, &b) in bytes.iter().enumerate() {
        if let Some(prev) = last_seen[b as usize] {
            if prev >= left {
                left = prev + 1;                // shrink past the earlier copy
            }
        }
        last_seen[b as usize] = Some(right);
        best = best.max(right - left + 1);
    }
    best
}

fn main() {
    println!("{:?}", max_window_sum(&[2, 1, 5, 1, 3, 2], 3));
    println!("{:?}", max_window_sum(&[4, 2], 3));
    for s in ["abcabcbb", "bbbbb", "pwwkew", ""] {
        println!("{:?} -> {}", s, longest_unique(s));
    }
}

use std::collections::{BTreeMap, HashMap};

// Unsorted input: positions of two numbers that add up to target.
fn two_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    let mut seen: HashMap<i32, usize> = HashMap::new();   // value -> index
    for (i, &x) in nums.iter().enumerate() {
        if let Some(&j) = seen.get(&(target - x)) {
            return Some((j, i));
        }
        seen.insert(x, i);
    }
    None
}

// Group words that are anagrams of each other.
fn group_anagrams<'a>(words: &[&'a str]) -> Vec<Vec<&'a str>> {
    let mut groups: BTreeMap<Vec<char>, Vec<&'a str>> = BTreeMap::new();
    for &w in words {
        let mut key: Vec<char> = w.chars().collect();
        key.sort_unstable();                                  // "eat" and "tea" -> ['a','e','t']
        groups.entry(key).or_default().push(w);
    }
    groups.into_values().collect()
}

fn main() {
    println!("{:?}", two_sum(&[2, 7, 11, 15], 9));
    println!("{:?}", two_sum(&[3, 2, 4], 6));
    println!("{:?}", two_sum(&[1, 2], 7));
    println!("{:?}", group_anagrams(&["eat", "tea", "tan", "ate", "nat", "bat"]));
}

fn balanced(s: &str) -> bool {
    let mut stack = Vec::new();
    for c in s.chars() {
        match c {
            '(' => stack.push(')'),          // push the closer we now expect
            '[' => stack.push(']'),
            '{' => stack.push('}'),
            ')' | ']' | '}' => {
                if stack.pop() != Some(c) {
                    return false;            // wrong closer, or nothing open
                }
            }
            _ => {}                          // ignore everything else
        }
    }
    stack.is_empty()                         // anything left open?
}

// For each day, how many days until a warmer one (0 if never).
fn days_until_warmer(temps: &[i32]) -> Vec<usize> {
    let mut answer = vec![0; temps.len()];
    let mut waiting: Vec<usize> = Vec::new();         // indices, temps decreasing
    for (i, &t) in temps.iter().enumerate() {
        while let Some(&j) = waiting.last() {
            if temps[j] >= t {
                break;
            }
            waiting.pop();
            answer[j] = i - j;                          // day i is j's warmer day
        }
        waiting.push(i);
    }
    answer
}

fn main() {
    for s in ["([]{})", "([)]", "((", "fn f() { v[0] }"] {
        println!("{:<16} {}", s, balanced(s));
    }
    println!("{:?}", days_until_warmer(&[73, 74, 75, 71, 69, 72, 76, 73]));
}

// Every combination of candidates (each used at most once) that sums to target.
fn combination_sum(candidates: &[u32], target: u32) -> Vec<Vec<u32>> {
    fn go(c: &[u32], start: usize, remaining: u32, path: &mut Vec<u32>, out: &mut Vec<Vec<u32>>) {
        if remaining == 0 {
            out.push(path.clone());                  // found one: record a copy
            return;
        }
        for i in start..c.len() {
            if c[i] > remaining {
                break;                               // sorted, so nothing later fits either
            }
            path.push(c[i]);                         // choose
            go(c, i + 1, remaining - c[i], path, out); // explore
            path.pop();                              // un-choose
        }
    }
    let mut sorted = candidates.to_vec();
    sorted.sort_unstable();
    let mut out = Vec::new();
    go(&sorted, 0, target, &mut Vec::new(), &mut out);
    out
}

fn main() {
    println!("{:?}", combination_sum(&[5, 2, 3, 7, 1], 8));
    println!("{:?}", combination_sum(&[4, 6], 5));
}

// Merge overlapping [start, end] intervals.
fn merge(mut intervals: Vec<(u32, u32)>) -> Vec<(u32, u32)> {
    intervals.sort_unstable_by_key(|&(start, _)| start);
    let mut merged: Vec<(u32, u32)> = Vec::new();
    for (start, end) in intervals {
        match merged.last_mut() {
            Some(last) if start <= last.1 => last.1 = last.1.max(end), // overlaps: extend
            _ => merged.push((start, end)),                            // gap: new interval
        }
    }
    merged
}

fn main() {
    println!("{:?}", merge(vec![(8, 10), (1, 3), (2, 6), (15, 18)]));
    println!("{:?}", merge(vec![(1, 4), (4, 5)]));
    println!("{:?}", merge(vec![(1, 10), (2, 3), (4, 5)]));
    println!("{:?}", merge(vec![]));
}

use std::collections::VecDeque;

const DIRS: [(isize, isize); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];

// The in-bounds neighbours of (r, c).
fn neighbours(grid: &[Vec<u8>], r: usize, c: usize) -> impl Iterator<Item = (usize, usize)> + '_ {
    DIRS.iter().filter_map(move |&(dr, dc)| {
        let nr = r.checked_add_signed(dr)?;          // None if it would go below 0
        let nc = c.checked_add_signed(dc)?;
        (nr < grid.len() && nc < grid[0].len()).then_some((nr, nc))
    })
}

// DFS: count islands of '#' (land connected up/down/left/right).
fn count_islands(grid: &[Vec<u8>]) -> usize {
    let mut seen = vec![vec![false; grid[0].len()]; grid.len()];
    let mut islands = 0;
    for r in 0..grid.len() {
        for c in 0..grid[0].len() {
            if grid[r][c] != b'#' || seen[r][c] {
                continue;
            }
            islands += 1;
            let mut stack = vec![(r, c)];            // explicit stack: no deep recursion
            seen[r][c] = true;
            while let Some((cr, cc)) = stack.pop() {
                for (nr, nc) in neighbours(grid, cr, cc) {
                    if grid[nr][nc] == b'#' && !seen[nr][nc] {
                        seen[nr][nc] = true;
                        stack.push((nr, nc));
                    }
                }
            }
        }
    }
    islands
}

// BFS: fewest steps from top-left to bottom-right through '.' cells.
fn shortest_path(grid: &[Vec<u8>]) -> Option<usize> {
    let (rows, cols) = (grid.len(), grid[0].len());
    let mut dist = vec![vec![None; cols]; rows];
    let mut queue = VecDeque::from([(0, 0)]);
    dist[0][0] = Some(0);
    while let Some((r, c)) = queue.pop_front() {
        let d = dist[r][c]?;
        if (r, c) == (rows - 1, cols - 1) {
            return Some(d);                          // BFS reaches it first by the shortest route
        }
        for (nr, nc) in neighbours(grid, r, c) {
            if grid[nr][nc] == b'.' && dist[nr][nc].is_none() {
                dist[nr][nc] = Some(d + 1);
                queue.push_back((nr, nc));
            }
        }
    }
    None
}

fn parse(rows: &[&str]) -> Vec<Vec<u8>> {
    rows.iter().map(|r| r.bytes().collect()).collect()
}

fn main() {
    let map = parse(&["##..#", "#...#", "..#..", "....#"]);
    println!("islands: {}", count_islands(&map));
    let maze = parse(&["..#.", "#...", "..#.", ".#.."]);
    println!("shortest: {:?}", shortest_path(&maze));
    let blocked = parse(&[".#", "#."]);
    println!("blocked: {:?}", shortest_path(&blocked));
}

// House robber: best total without taking two neighbours.
fn rob(houses: &[u32]) -> u32 {
    let (mut skip, mut take) = (0, 0);         // best so far if the last house was skipped / taken
    for &h in houses {
        (skip, take) = (skip.max(take), skip + h);
    }
    skip.max(take)
}

// Kadane: biggest sum of a non-empty contiguous run.
fn max_subarray(a: &[i32]) -> Option<i32> {
    let (&first, rest) = a.split_first()?;
    let (mut ending_here, mut best) = (first, first);
    for &x in rest {
        ending_here = x.max(ending_here + x);   // extend the run, or start again at x
        best = best.max(ending_here);
    }
    Some(best)
}

fn main() {
    println!("rob {:?} = {}", [2, 7, 9, 3, 1], rob(&[2, 7, 9, 3, 1]));
    println!("rob {:?} = {}", [2, 1, 1, 2], rob(&[2, 1, 1, 2]));
    println!("max_subarray = {:?}", max_subarray(&[-2, 1, -3, 4, -1, 2, 1, -5, 4]));
    println!("max_subarray = {:?}", max_subarray(&[-3, -1, -2]));
    println!("max_subarray = {:?}", max_subarray(&[]));
}