Problem Solving

// Restated: best profit from one buy then one later sell; 0 if prices only fall.
// Input: int[] prices (may be empty). Output: int >= 0.
Console.WriteLine(MaxProfit([7, 1, 5, 3, 6, 4])); // normal: buy at 1, sell at 6
Console.WriteLine(MaxProfit([7, 6, 4, 3, 1]));    // prices only fall
Console.WriteLine(MaxProfit([]));                 // empty
Console.WriteLine(MaxProfit([5]));                // one day

static int MaxProfit(int[] prices)
{
    int lowest = int.MaxValue, best = 0;
    foreach (int price in prices)
    {
        lowest = Math.Min(lowest, price);      // cheapest buy so far
        best = Math.Max(best, price - lowest); // what if I sell today?
    }
    return best;
}

int passed = 0, failed = 0;

Check("", true);                          // empty
Check("a", true);                         // one character
Check("ab", false);                       // smallest false case
Check("Aba", true);                       // mixed case
Check("A man, a plan, a canal: Panama", true);
Check("race a car", false);
Check(".,", true);                        // only punctuation
Console.WriteLine($"{passed} passed, {failed} failed");

void Check(string input, bool expected)
{
    bool got = IsPalindrome(input);
    if (got == expected) passed++;
    else
    {
        failed++;
        Console.WriteLine($"FAIL '{input}': expected {expected}, got {got}");
    }
}

static bool IsPalindrome(string s)
{
    int i = 0, j = s.Length - 1;
    while (i < j)
    {
        char a = s[i], b = s[j];
        if (!char.IsLetterOrDigit(a)) { i++; continue; }
        if (!char.IsLetterOrDigit(b)) { j--; continue; }
        if (char.ToLowerInvariant(a) != char.ToLowerInvariant(b)) return false;
        i++;
        j--;
    }
    return true;
}

foreach (int n in new[] { 1_000, 10_000 })
{
    int[] a = Enumerable.Range(0, n).ToArray(); // no duplicates: the worst case
    Console.WriteLine($"n={n}  nested={NestedOps(a)}  set={SetOps(a)}");
}

// O(n^2): compare every pair
static long NestedOps(int[] a)
{
    long ops = 0;
    for (int i = 0; i < a.Length; i++)
        for (int j = i + 1; j < a.Length; j++)
        {
            ops++;
            if (a[i] == a[j]) return ops;
        }
    return ops;
}

// O(n): remember what we have seen
static long SetOps(int[] a)
{
    long ops = 0;
    var seen = new HashSet<int>();
    foreach (int x in a)
    {
        ops++;
        if (!seen.Add(x)) return ops; // Add returns false for a duplicate
    }
    return ops;
}

int[] a = [1, 3, 4, 6, 8, 11];
Console.WriteLine(PairSum(a, 10));
Console.WriteLine(PairSum(a, 2));

// sorted input: indices of two numbers that add up to target, or (-1, -1)
static (int, int) PairSum(int[] a, int target)
{
    int i = 0, j = a.Length - 1;
    while (i < j)
    {
        int sum = a[i] + a[j];
        if (sum == target) return (i, j);
        if (sum < target) i++; // need bigger: move the left pointer up
        else j--;              // need smaller: move the right pointer down
    }
    return (-1, -1);
}

Console.WriteLine($"{LongestUnique("abcabcbb")} {LongestUnique("bbbb")} {LongestUnique("pwwkew")}");
Console.WriteLine(MaxSumK([2, 1, 5, 1, 3, 2], 3));

// length of the longest substring with no repeated character
static int LongestUnique(string s)
{
    var lastSeen = new Dictionary<char, int>();
    int best = 0, left = 0;
    for (int right = 0; right < s.Length; right++)
    {
        char c = s[right];
        if (lastSeen.TryGetValue(c, out int prev) && prev >= left)
            left = prev + 1; // jump the left edge past the repeat
        lastSeen[c] = right;
        best = Math.Max(best, right - left + 1);
    }
    return best;
}

// fixed-size window: biggest sum of any k consecutive numbers
static int MaxSumK(int[] a, int k)
{
    int sum = 0;
    for (int i = 0; i < k; i++) sum += a[i];
    int best = sum;
    for (int i = k; i < a.Length; i++)
    {
        sum += a[i] - a[i - k]; // slide: add the new, drop the old
        best = Math.Max(best, sum);
    }
    return best;
}

Console.WriteLine(TwoSum([3, 8, 2, 11, 7], 9));
foreach (var group in GroupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
    Console.WriteLine(string.Join(", ", group));

// unsorted input: indices of two numbers adding to target (the classic "Two Sum")
static (int, int) TwoSum(int[] nums, int target)
{
    var indexOf = new Dictionary<int, int>();
    for (int i = 0; i < nums.Length; i++)
    {
        if (indexOf.TryGetValue(target - nums[i], out int j)) return (j, i);
        indexOf[nums[i]] = i;
    }
    return (-1, -1);
}

// group words that are anagrams of each other
static IEnumerable<List<string>> GroupAnagrams(string[] words)
{
    var groups = new SortedDictionary<string, List<string>>(StringComparer.Ordinal);
    foreach (string w in words)
    {
        string key = string.Concat(w.Order()); // "tea" -> "aet"
        if (!groups.TryGetValue(key, out var list)) groups[key] = list = [];
        list.Add(w);
    }
    return groups.Values;
}

int[] temps = [73, 74, 75, 71, 69, 72, 76, 73];
Console.WriteLine(string.Join(", ", DaysUntilWarmer(temps)));
Console.WriteLine($"{Rpn("3 4 + 2 *")} {Rpn("10 3 -")}");

// for each day, how many days until a warmer temperature (0 if never)
static int[] DaysUntilWarmer(int[] temps)
{
    var answer = new int[temps.Length];
    var waiting = new Stack<int>(); // indices still waiting; coolest on top
    for (int i = 0; i < temps.Length; i++)
    {
        while (waiting.Count > 0 && temps[i] > temps[waiting.Peek()])
        {
            int day = waiting.Pop();
            answer[day] = i - day;
        }
        waiting.Push(i);
    }
    return answer;
}

// reverse Polish notation: "3 4 + 2 *" means (3 + 4) * 2
static int Rpn(string expr)
{
    var st = new Stack<int>();
    foreach (string tok in expr.Split(" "))
    {
        switch (tok)
        {
            case "+": st.Push(st.Pop() + st.Pop()); break;
            case "*": st.Push(st.Pop() * st.Pop()); break;
            case "-": { int b = st.Pop(), a = st.Pop(); st.Push(a - b); break; }
            default: st.Push(int.Parse(tok)); break;
        }
    }
    return st.Pop();
}

var subsets = new List<List<int>>();
Subsets([1, 2, 3], 0, [], subsets);
Console.WriteLine(string.Join(" ", subsets.Select(s => "[" + string.Join(",", s) + "]")));

var perms = new List<string>();
Permute("", "abc", perms);
Console.WriteLine(string.Join(" ", perms));

static void Subsets(int[] nums, int start, List<int> current, List<List<int>> output)
{
    output.Add([.. current]);                 // copy: current keeps changing
    for (int i = start; i < nums.Length; i++)
    {
        current.Add(nums[i]);                 // choose
        Subsets(nums, i + 1, current, output); // explore
        current.RemoveAt(current.Count - 1);  // un-choose
    }
}

static void Permute(string prefix, string rest, List<string> output)
{
    if (rest.Length == 0) { output.Add(prefix); return; }
    for (int i = 0; i < rest.Length; i++)
        Permute(prefix + rest[i], rest.Remove(i, 1), output);
}

List<(int Start, int End)> meetings = [(8, 10), (1, 3), (2, 6), (15, 18), (17, 20)];
Console.WriteLine(string.Join(" ", Merge(meetings)));

static List<(int Start, int End)> Merge(List<(int Start, int End)> intervals)
{
    var merged = new List<(int Start, int End)>();
    foreach (var iv in intervals.OrderBy(iv => iv.Start))
    {
        if (merged.Count > 0 && iv.Start <= merged[^1].End)
            merged[^1] = (merged[^1].Start, Math.Max(merged[^1].End, iv.End)); // overlap: extend
        else
            merged.Add(iv); // gap: start a new interval
    }
    return merged;
}

(int Dr, int Dc)[] dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)];

char[][] map =
[
    "##..#".ToCharArray(),
    "#...#".ToCharArray(),
    "..#..".ToCharArray(),
    "....#".ToCharArray(),
];
Console.WriteLine($"islands: {CountIslands(map)}");
Console.WriteLine($"steps: {ShortestPath(["..#.", ".#..", "....", "#.#."])}");

int CountIslands(char[][] g)
{
    int count = 0;
    for (int r = 0; r < g.Length; r++)
        for (int c = 0; c < g[0].Length; c++)
            if (g[r][c] == '#') { count++; Sink(g, r, c); }
    return count;
}

void Sink(char[][] g, int r, int c) // DFS: turn a whole island into water
{
    if (r < 0 || c < 0 || r >= g.Length || c >= g[0].Length || g[r][c] != '#') return;
    g[r][c] = '.';
    foreach (var (dr, dc) in dirs) Sink(g, r + dr, c + dc);
}

int ShortestPath(string[] maze) // BFS from top-left to bottom-right, -1 if unreachable
{
    int rows = maze.Length, cols = maze[0].Length;
    var dist = new int[rows, cols];
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++) dist[r, c] = -1;
    var queue = new Queue<(int R, int C)>();
    dist[0, 0] = 0;
    queue.Enqueue((0, 0));
    while (queue.Count > 0)
    {
        var (r, c) = queue.Dequeue();
        foreach (var (dr, dc) in dirs)
        {
            int nr = r + dr, nc = c + dc;
            if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && maze[nr][nc] == '.' && dist[nr, nc] == -1)
            {
                dist[nr, nc] = dist[r, c] + 1;
                queue.Enqueue((nr, nc));
            }
        }
    }
    return dist[rows - 1, cols - 1];
}

Console.WriteLine($"paths 3x3 = {UniquePaths(3, 3)}, 3x7 = {UniquePaths(3, 7)}");
Console.WriteLine($"rob = {Rob([2, 7, 9, 3, 1])}");
Console.WriteLine($"max subarray = {MaxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])}");

// a robot moves only right or down: how many routes from top-left to bottom-right?
static long UniquePaths(int rows, int cols)
{
    var row = new long[cols];
    Array.Fill(row, 1L);            // top row: exactly one way to reach each cell
    for (int r = 1; r < rows; r++)
        for (int c = 1; c < cols; c++)
            row[c] += row[c - 1];   // from above (old row[c]) + from the left
    return row[cols - 1];
}

// most money from houses in a row without robbing two neighbours
static int Rob(int[] houses)
{
    int skip = 0, take = 0;         // best so far without / with the previous house
    foreach (int money in houses)
    {
        int newTake = skip + money;
        skip = Math.Max(skip, take);
        take = newTake;
    }
    return Math.Max(skip, take);
}

// largest sum of a contiguous subarray (Kadane)
static int MaxSubarray(int[] a)
{
    int best = a[0], endingHere = a[0];
    for (int i = 1; i < a.Length; i++)
    {
        endingHere = Math.Max(a[i], endingHere + a[i]); // extend, or start fresh here
        best = Math.Max(best, endingHere);
    }
    return best;
}