C# DSA Cheat Sheet

Dictionary (Hash Map)

var freq = new Dictionary<int, int>();
foreach (var x in nums)
    freq[x] = freq.GetValueOrDefault(x) + 1;

// Check and get
if (freq.TryGetValue(key, out int val)) { /* use val */ }

// Iterate
foreach (var (k, v) in freq) { }

O(1) average lookup/insert. Use for frequency counting, complement lookup (Two Sum), and caching seen values.

HashSet

var seen = new HashSet<int>();
seen.Add(x);
bool exists = seen.Contains(x);
seen.Remove(x);

// Intersection / union
var inter = new HashSet<int>(a);
inter.IntersectWith(b);

O(1) membership. Use to track visited nodes, detect duplicates, and set operations.

Stack

var stack = new Stack<int>();
stack.Push(x);
int top = stack.Peek();   // look without removing
int val = stack.Pop();    // remove and return
bool empty = stack.Count == 0;

LIFO. Use for balanced parentheses, monotonic stack, DFS iterative, undo operations.

Queue

var q = new Queue<int>();
q.Enqueue(x);
int front = q.Peek();
int val = q.Dequeue();
bool empty = q.Count == 0;

FIFO. Use for BFS, level-order tree traversal, sliding window with constraints.

Priority Queue (Min-Heap)

// Min-heap (.NET 6+)
var pq = new PriorityQueue<int, int>();
pq.Enqueue(value, priority);     // lower priority = dequeued first
int top = pq.Peek().Element;     // not available — use Dequeue
(int elem, int pri) = pq.Dequeue();
int size = pq.Count;

// Max-heap: negate the priority
pq.Enqueue(value, -value);

O(log n) push/pop. Use for top-K, Dijkstra, merge K sorted lists, median stream (two heaps).

SortedSet / SortedDictionary

var ss = new SortedSet<int>();
ss.Add(x);
int min = ss.Min;
int max = ss.Max;
int floor  = ss.GetViewBetween(int.MinValue, x).Max;  // largest ≤ x
int ceiling = ss.GetViewBetween(x, int.MaxValue).Min; // smallest ≥ x
ss.Remove(x);

O(log n) all ops. Use when you need both fast lookup and order queries (floor/ceiling/successor).

Linked List (as Deque)

var dq = new LinkedList<int>();
dq.AddFirst(x);   // push front
dq.AddLast(x);    // push back
int front = dq.First!.Value;
int back  = dq.Last!.Value;
dq.RemoveFirst();
dq.RemoveLast();

O(1) front/back ops. Use for sliding window max/min (monotonic deque) and LRU cache.

Opposite ends (sorted array)

int left = 0, right = nums.Length - 1;
while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == target) return new[] { left, right };
    if (sum < target) left++;
    else right--;
}

Fast / Slow pointer (cycle detection)

var slow = head;
var fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true; // cycle
}
return false;

Remove duplicates in-place

int k = 1;
for (int i = 1; i < nums.Length; i++)
    if (nums[i] != nums[i - 1])
        nums[k++] = nums[i];
return k;

Fixed size window

int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += nums[i];
int maxSum = windowSum;
for (int i = k; i < nums.Length; i++) {
    windowSum += nums[i] - nums[i - k];
    maxSum = Math.Max(maxSum, windowSum);
}

Variable size — at most K distinct characters

var freq = new Dictionary<char, int>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.Length; right++) {
    freq[s[right]] = freq.GetValueOrDefault(s[right]) + 1;
    while (freq.Count > k) {                      // shrink
        freq[s[left]]--;
        if (freq[s[left]] == 0) freq.Remove(s[left]);
        left++;
    }
    maxLen = Math.Max(maxLen, right - left + 1);
}

Grid BFS

int[][] dirs = { new[]{0,1}, new[]{0,-1}, new[]{1,0}, new[]{-1,0} };
var q = new Queue<(int r, int c)>();
q.Enqueue((startR, startC));
var visited = new bool[rows, cols];
visited[startR, startC] = true;
int steps = 0;

while (q.Count > 0) {
    int size = q.Count;
    for (int i = 0; i < size; i++) {
        var (r, c) = q.Dequeue();
        if (r == endR && c == endC) return steps;
        foreach (var d in dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                && !visited[nr, nc] && grid[nr][nc] != '#') {
                visited[nr, nc] = true;
                q.Enqueue((nr, nc));
            }
        }
    }
    steps++;
}

Tree Level Order

var result = new List<IList<int>>();
if (root == null) return result;
var q = new Queue<TreeNode>();
q.Enqueue(root);
while (q.Count > 0) {
    int size = q.Count;
    var level = new List<int>();
    for (int i = 0; i < size; i++) {
        var node = q.Dequeue();
        level.Add(node.val);
        if (node.left != null)  q.Enqueue(node.left);
        if (node.right != null) q.Enqueue(node.right);
    }
    result.Add(level);
}

Recursive DFS on graph

var visited = new HashSet<int>();
void Dfs(int node) {
    visited.Add(node);
    foreach (var neighbour in graph[node])
        if (!visited.Contains(neighbour))
            Dfs(neighbour);
}

Backtracking template (subsets / permutations)

var result = new List<IList<int>>();
void Backtrack(int start, List<int> current) {
    result.Add(new List<int>(current)); // snapshot
    for (int i = start; i < nums.Length; i++) {
        current.Add(nums[i]);       // choose
        Backtrack(i + 1, current);  // explore
        current.RemoveAt(current.Count - 1); // un-choose
    }
}
Backtrack(0, new List<int>());

1D DP — Climbing Stairs / House Robber pattern

// dp[i] = best answer considering first i elements
int[] dp = new int[n + 1];
dp[0] = base0;
dp[1] = base1;
for (int i = 2; i <= n; i++)
    dp[i] = Math.Max(dp[i - 1], dp[i - 2] + nums[i - 1]);
return dp[n];

// Space-optimised (rolling variables)
int prev2 = base0, prev1 = base1;
for (int i = 2; i <= n; i++) {
    int cur = Math.Max(prev1, prev2 + nums[i - 1]);
    prev2 = prev1; prev1 = cur;
}
return prev1;

2D DP — Longest Common Subsequence pattern

int m = text1.Length, n = text2.Length;
int[,] dp = new int[m + 1, n + 1];
for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
        dp[i, j] = text1[i-1] == text2[j-1]
            ? dp[i-1, j-1] + 1
            : Math.Max(dp[i-1, j], dp[i, j-1]);
return dp[m, n];

Memoization with tuple key

var memo = new Dictionary<(int, int), int>();
int Solve(int i, int j) {
    if (/* base case */) return 0;
    if (memo.TryGetValue((i, j), out int cached)) return cached;
    int result = /* recurrence */;
    return memo[(i, j)] = result;
}