Pattern Recognition & Edge Cases — Master Guide

// Binary Search Template - Find target in sorted array
public int BinarySearch(int[] arr, int target) {
    int left = 0, right = arr.Length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // Avoid overflow

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1; // Search right
        } else {
            right = mid - 1; // Search left
        }
    }

    return -1; // Not found
}

// Variant: Find insertion position (leftmost)
public int SearchInsert(int[] arr, int target) {
    int left = 0, right = arr.Length;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left; // Insert position
}

// BFS Template - Shortest path in unweighted graph
public int BFS(int[][] graph, int start, int end) {
    Queue<int> queue = new Queue<int>();
    HashSet<int> visited = new HashSet<int>();
    Dictionary<int, int> distance = new Dictionary<int, int>();

    queue.Enqueue(start);
    visited.Add(start);
    distance[start] = 0;

    while (queue.Count > 0) {
        int node = queue.Dequeue();

        if (node == end) {
            return distance[end];
        }

        foreach (int neighbor in graph[node]) {
            if (!visited.Contains(neighbor)) {
                visited.Add(neighbor);
                distance[neighbor] = distance[node] + 1;
                queue.Enqueue(neighbor);
            }
        }
    }

    return -1; // No path found
}

// DFS Template - Recursive traversal
HashSet<int> visited = new HashSet<int>();

public void DFS(int node, int[][] graph) {
    if (visited.Contains(node)) {
        return;
    }

    visited.Add(node);
    // Process current node

    foreach (int neighbor in graph[node]) {
        if (!visited.Contains(neighbor)) {
            DFS(neighbor, graph);
        }
    }
}

// Iterative DFS using stack
public void DFSIterative(int start, int[][] graph) {
    Stack<int> stack = new Stack<int>();
    stack.Push(start);
    visited.Add(start);

    while (stack.Count > 0) {
        int node = stack.Pop();
        // Process node

        foreach (int neighbor in graph[node]) {
            if (!visited.Contains(neighbor)) {
                visited.Add(neighbor);
                stack.Push(neighbor);
            }
        }
    }
}

// Sliding Window Template - Fixed/variable window
// Problem: Find longest substring with at most k distinct chars
public int MaxWindowLength(string s, int k) {
    Dictionary<char, int> charCount = new Dictionary<char, int>();
    int left = 0, maxLen = 0;

    for (int right = 0; right < s.Length; right++) {
        // Expand window: add s[right]
        if (!charCount.ContainsKey(s[right])) {
            charCount[s[right]] = 0;
        }
        charCount[s[right]]++;

        // Shrink window: remove from left while invalid
        while (charCount.Count > k) {
            charCount[s[left]]--;
            if (charCount[s[left]] == 0) {
                charCount.Remove(s[left]);
            }
            left++;
        }

        // Update answer
        maxLen = Math.Max(maxLen, right - left + 1);
    }

    return maxLen;
}

// Two Pointers Template - Find pair with target sum
public int[] TwoSum(int[] sorted, int target) {
    int left = 0, right = sorted.Length - 1;

    while (left < right) {
        int sum = sorted[left] + sorted[right];

        if (sum == target) {
            return new int[] { left, right };
        } else if (sum < target) {
            left++; // Need larger sum
        } else {
            right--; // Need smaller sum
        }
    }

    return new int[] { -1, -1 };
}

// Variant: Partition array (e.g., sort colors 0,1,2)
public void Partition(int[] arr, int k) {
    int left = 0, right = arr.Length - 1;

    while (left < right) {
        while (left < right && arr[left] < k) left++;
        while (left < right && arr[right] >= k) right--;

        // Swap
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
}

// Union-Find with path compression and union by rank
public class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];

        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    // Find root with path compression
    public int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]); // Path compression
        }
        return parent[x];
    }

    // Union by rank
    public bool Union(int x, int y) {
        int rootX = Find(x);
        int rootY = Find(y);

        if (rootX == rootY) return false; // Already connected

        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }

        return true; // Successfully merged
    }
}

// Prefix Sum Template - O(1) range queries
public class RangeSumQuery {
    private long[] prefix;

    public RangeSumQuery(int[] nums) {
        prefix = new long[nums.Length + 1];

        // Build prefix sum: prefix[i] = sum of nums[0..i-1]
        for (int i = 0; i < nums.Length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }

    // Query sum of nums[left..right] in O(1)
    public long RangeSum(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

// For 2D matrix: prefix[i][j] = sum of rect from (0,0) to (i-1,j-1)
public long RangeSum2D(long[][] prefix, int r1, int c1, int r2, int c2) {
    return prefix[r2+1][c2+1]
        - prefix[r1][c2+1]
        - prefix[r2+1][c1]
        + prefix[r1][c1];
}

// Monotonic Stack - Find next greater element
public int[] NextGreaterElement(int[] nums) {
    Stack<int> stack = new Stack<int>();
    Dictionary<int, int> result = new Dictionary<int, int>();

    // Process in reverse to build monotonic decreasing stack
    for (int i = nums.Length - 1; i >= 0; i--) {
        // Pop smaller elements
        while (stack.Count > 0 && stack.Peek() < nums[i]) {
            stack.Pop();
        }

        // Top of stack is next greater (or -1 if empty)
        result[nums[i]] = stack.Count > 0 ? stack.Peek() : -1;

        // Push current element
        stack.Push(nums[i]);
    }

    int[] answer = new int[nums.Length];
    for (int i = 0; i < nums.Length; i++) {
        answer[i] = result[nums[i]];
    }

    return answer;
}

// Trie Template - Efficient prefix matching
public class TrieNode {
    public Dictionary<char, TrieNode> Children { get; set; }
    public bool IsEndOfWord { get; set; }

    public TrieNode() {
        Children = new Dictionary<char, TrieNode>();
        IsEndOfWord = false;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Insert word - O(m) where m = word length
    public void Insert(string word) {
        TrieNode node = root;

        foreach (char ch in word) {
            if (!node.Children.ContainsKey(ch)) {
                node.Children[ch] = new TrieNode();
            }
            node = node.Children[ch];
        }

        node.IsEndOfWord = true;
    }

    // Search for exact word
    public bool Search(string word) {
        TrieNode node = FindNode(word);
        return node != null && node.IsEndOfWord;
    }

    // Search with prefix (no exact match needed)
    public bool StartsWith(string prefix) {
        return FindNode(prefix) != null;
    }

    private TrieNode FindNode(string word) {
        TrieNode node = root;

        foreach (char ch in word) {
            if (!node.Children.ContainsKey(ch)) {
                return null;
            }
            node = node.Children[ch];
        }

        return node;
    }
}

// Dijkstra - Shortest path in weighted graph
public long[] Dijkstra(int n, List<(int neighbor, long weight)>[] graph, int start) {
    long[] dist = new long[n];
    for (int i = 0; i < n; i++) dist[i] = long.MaxValue;
    dist[start] = 0;

    PriorityQueue<(long dist, int node)> pq = new();
    pq.Enqueue((0, start), 0);

    while (pq.Count > 0) {
        (long d, int u) = pq.Dequeue();

        if (d > dist[u]) continue; // Skip outdated entry

        foreach ((int v, long w) in graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.Enqueue((dist[v], v), (int)dist[v]);
            }
        }
    }

    return dist;
}