The collections that matter in a coding interview, what each operation costs, and the traps that turn a good C# answer into a slow or wrong one. Written for someone who knows basic C#.
Interviewers do not test C# trivia. But they do notice list.RemoveAt(0) inside a loop, and they note that your O(n) idea just became O(n²). This page is the small set of facts that stops that from happening.
// O(1) or // O(n log n). Average means a bad run of hash collisions could make that one call O(n). On interview inputs, treat it as constant. Amortised means the cost holds across many calls, even though one call now and then costs more.The pattern pages use modern C#, up to C# 14. Five pieces of syntax cover most of it. If any look new, read this section first.
public static class Basics
{
/// <summary>Names the sign of a number with a switch expression.</summary>
/// <param name="n">Any integer.</param>
/// <returns>"negative", "zero" or "positive".</returns>
/// <example>Basics.Sign(-4) returns "negative".</example>
public static string Sign(int n) => n switch
{
< 0 => "negative", // 0 is the line between the two signs
0 => "zero",
_ => "positive", // _ is the catch-all arm
};
/// <summary>Swaps two values with tuple deconstruction.</summary>
/// <param name="a">The first value.</param>
/// <param name="b">The second value.</param>
/// <returns>The pair in swapped order.</returns>
/// <example>Basics.Swap(1, 2) returns (2, 1).</example>
public static (int First, int Second) Swap(int a, int b)
{
(a, b) = (b, a); // the right side is built first, so no temp is needed
return (a, b);
}
/// <summary>Builds a list from an array plus one more item.</summary>
/// <returns>The new list.</returns>
/// <example>Basics.Spread() returns [1, 2, 3, 4].</example>
public static List<int> Spread()
{
int[] start = [1, 2, 3]; // sample data
List<int> more = [.. start, 4]; // .. copies every item in, then 4 goes on the end
return more;
}
}
[1, 2, 3] is a collection expression. The same brackets build an array, a List<T>, a HashSet<T> or a span, based on the target type. .. inside one is the spread operator.
Every DFS and backtracking solution on this site defines a helper inside the main method. In C# that is a local function. It can read and change the outer method’s locals. There is no nonlocal keyword to remember.
public static class LocalFunctions
{
/// <summary>Adds up the items with a local function that changes an outer local.</summary>
/// <param name="items">The numbers to add.</param>
/// <returns>The total of all items.</returns>
/// <example>LocalFunctions.AddUp([1, 2, 3]) returns 6.</example>
public static int AddUp(int[] items)
{
int total = 0; // 0 is the sum of no items
// The local function captures `total`, so += changes the outer variable.
void Add(int value) => total += value;
// Each pass adds one item. Invariant: total = sum of the items seen so far.
foreach (int item in items)
{
Add(item);
}
return total;
}
}
static local function cannot capture anything, which is a useful way to prove a helper is pure. A lambda captures the same way, but a lambda that captures allocates a closure object each time it is created.is null/// <summary>A binary tree node. A class, so variables hold a reference to it.</summary>
public class TreeNode(int val, TreeNode? left = null, TreeNode? right = null)
{
public int Val { get; set; } = val;
public TreeNode? Left { get; set; } = left;
public TreeNode? Right { get; set; } = right;
}
/// <summary>A grid cell. A record struct gets value equality and a hash code for free.</summary>
public readonly record struct Cell(int Row, int Col);
public static class TreeDepth
{
/// <summary>Returns the height of a tree, counting nodes on the longest path.</summary>
/// <param name="root">The root, or null for an empty tree.</param>
/// <returns>0 for null, else 1 plus the taller child.</returns>
/// <example>TreeDepth.Of(new TreeNode(1, new TreeNode(2))) returns 2.</example>
public static int Of(TreeNode? root)
{
// `is null` cannot be fooled by an overloaded == operator.
if (root is null)
{
return 0; // an empty tree has no levels
}
return 1 + Math.Max(Of(root.Left), Of(root.Right)); // 1 counts this node
}
}
The parentheses after class TreeNode are a primary constructor. TreeNode? means the value may be null. Nullable reference types are on in every sample, so the compiler warns when you forget a null check.
T[] and doubles it when full. Indexing is instant. Adding at the end is instant on average. Adding or removing at the front shifts every other element, so it is slow.If you know Java, this is ArrayList. C++: std::vector. Python: list.
public static class ListDemo
{
/// <summary>Runs the everyday List operations and returns the result.</summary>
/// <returns>The list after the edits below.</returns>
/// <example>ListDemo.Run() returns [0, 1, 2, 3].</example>
public static List<int> Run()
{
List<int> items = [3, 1, 2]; // sample data
items.Add(4); // O(1) amortised [3, 1, 2, 4]
int first = items[0]; // O(1) index 0 is the first slot, so 3
items.RemoveAt(items.Count - 1); // O(1) - 1 because the last index is Count - 1
bool hasTwo = items.Contains(2); // O(n) a linear scan. Use a HashSet if hot.
items.Sort(); // O(n log n) in place, NOT stable [1, 2, 3]
// The two slow ones. Both shift every later element.
items.Insert(0, 0); // O(n) index 0 is the front [0, 1, 2, 3]
items.RemoveAt(0); // O(n) removes the front again
items.Insert(0, 0); // O(n) put it back for the return value
return items;
}
}
List.Sort and Array.Sort are not stable. Equal keys may come out in any order. When ties must keep their input order, use LINQ OrderBy, which is stable, or add a tie-break to the comparer.Equals and GetHashCode. Numbers, strings, enums, value tuples and records all work. Arrays and most classes compare by reference, which is a trap covered below.If you know Java, this is HashMap. C++: std::unordered_map. Python: dict.
public static class DictDemo
{
/// <summary>Runs the everyday Dictionary operations.</summary>
/// <returns>The age stored for "cat" plus the default read for "dan".</returns>
/// <example>DictDemo.Run() returns 40.</example>
public static int Run()
{
var ages = new Dictionary<string, int> { ["ann"] = 30, ["bob"] = 25 }; // sample data
ages["cat"] = 40; // O(1) avg insert, or overwrite if present
bool hasBob = ages.ContainsKey("bob"); // O(1) avg true
int dan = ages.GetValueOrDefault("dan"); // O(1) avg 0, the default for int
ages.Remove("bob"); // O(1) avg returns false if missing
bool added = ages.TryAdd("ann", 99); // O(1) avg false, "ann" is already there
return ages["cat"] + dan; // O(1) avg 40 + 0
}
/// <summary>Reads a missing key with the indexer.</summary>
/// <returns>Never returns. It throws KeyNotFoundException.</returns>
/// <example>DictDemo.ReadMissing() throws KeyNotFoundException.</example>
public static int ReadMissing()
{
var ages = new Dictionary<string, int>();
return ages["zed"]; // throws: reading the indexer never defaults
}
}
d[key] = v adds or overwrites, and never throws. Reading d[key] throws KeyNotFoundException when the key is missing. d.Add(key, v) throws ArgumentException when the key already exists. Use TryGetValue, GetValueOrDefault and TryAdd when a miss is normal.Order is not guaranteed. A Dictionary often iterates in insertion order, until you remove something. Never rely on it. If the output must be ordered, sort it, or use SortedDictionary.
C# has no Counter and no defaultdict. Two short idioms replace them.
using System.Runtime.InteropServices;
public static class Tally
{
/// <summary>Counts each character with GetValueOrDefault. Two lookups per character.</summary>
/// <param name="text">The text to count.</param>
/// <returns>A map from character to count.</returns>
/// <example>Tally.Simple("aab")['a'] returns 2.</example>
public static Dictionary<char, int> Simple(string text)
{
var counts = new Dictionary<char, int>();
// Each pass counts one character. Invariant: counts covers every char seen so far.
foreach (char ch in text)
{
counts[ch] = counts.GetValueOrDefault(ch) + 1; // a miss reads as 0, + 1 counts ch
}
return counts;
}
/// <summary>Counts each character with one hash lookup per character.</summary>
/// <param name="text">The text to count.</param>
/// <returns>A map from character to count.</returns>
/// <example>Tally.Fast("mississippi")['s'] returns 4.</example>
public static Dictionary<char, int> Fast(string text)
{
var counts = new Dictionary<char, int>();
foreach (char ch in text)
{
// Get a ref to the value slot. A missing key gets a new slot holding 0.
ref int slot = ref CollectionsMarshal.GetValueRefOrAddDefault(counts, ch, out _);
slot++; // + 1 for this sighting, written straight into the dictionary
}
return counts;
}
}
CollectionsMarshal.GetValueRefOrAddDefault lives in System.Runtime.InteropServices. It hashes once instead of twice. Do not add or remove keys while you still hold the ref, because a resize moves the slot. In an interview, the simple form is fine. Mention the fast one as a follow-up.public static class Grouping
{
/// <summary>Groups words that are anagrams of each other.</summary>
/// <param name="words">The words to group.</param>
/// <returns>The number of distinct groups.</returns>
/// <example>Grouping.AnagramGroups(["eat", "tea", "tan", "nat", "bat"]) returns 3.</example>
public static int AnagramGroups(string[] words)
{
var groups = new Dictionary<string, List<string>>();
foreach (string word in words)
{
// Every anagram has the same sorted letters, so they make the key.
char[] letters = word.ToCharArray();
Array.Sort(letters);
string key = new string(letters);
// Create the bucket on first touch. This is the defaultdict(list) idiom.
if (!groups.TryGetValue(key, out var bucket))
{
bucket = [];
groups[key] = bucket;
}
bucket.Add(word);
}
return groups.Count;
}
/// <summary>Builds an adjacency list for nodes 0..n-1 as an array of lists.</summary>
/// <param name="n">The number of nodes.</param>
/// <param name="edges">Undirected edges as [u, v] pairs.</param>
/// <returns>adj[u] lists every neighbour of u.</returns>
/// <example>Grouping.Adjacency(3, [[0, 1], [1, 2]])[1] returns [0, 2].</example>
public static List<int>[] Adjacency(int n, int[][] edges)
{
// Nodes are 0..n-1, so a plain array beats a Dictionary. Fill every slot first.
var adj = new List<int>[n];
for (int u = 0; u < n; u++) // u is a node id. 0 is the first one.
{
adj[u] = [];
}
foreach (int[] e in edges)
{
adj[e[0]].Add(e[1]); // [0] is one end, [1] is the other
adj[e[1]].Add(e[0]); // undirected, so add the reverse direction too
}
return adj;
}
}
Add, Remove and Contains. Its whole job is answering “have I seen this before?” fast. Add returns false when the value was already there, which saves a separate check.public static class Sets
{
/// <summary>Returns the first value seen twice, or null if all are distinct.</summary>
/// <param name="nums">The values to scan.</param>
/// <returns>The first repeat, or null.</returns>
/// <example>Sets.FirstRepeat([3, 1, 4, 1, 5]) returns 1.</example>
public static int? FirstRepeat(int[] nums)
{
var seen = new HashSet<int>();
foreach (int x in nums)
{
if (!seen.Add(x)) // O(1) avg. Add is false when x is already in the set.
{
return x;
}
}
return null;
}
/// <summary>Returns the values in both arrays, smallest first.</summary>
/// <param name="a">The first array.</param>
/// <param name="b">The second array.</param>
/// <returns>The common values, sorted.</returns>
/// <example>Sets.Common([1, 2, 3], [2, 3, 4]) returns [2, 3].</example>
public static List<int> Common(int[] a, int[] b)
{
var set = new HashSet<int>(a); // O(len a)
set.IntersectWith(b); // O(len b). Changes the set in place.
return [.. set.Order()]; // sorted, because set order is not defined
}
}
list.Contains(x) scans the whole list and is O(n). set.Contains(x) is O(1). Putting the wrong one inside a loop is the most common accidental slowdown in interviews.Enqueue and Dequeue are O(1). This is the queue for every BFS. Never use List.RemoveAt(0) as a queue.public static class Bfs
{
/// <summary>Finds the fewest edges from start to every node.</summary>
/// <param name="adj">adj[u] lists the neighbours of u.</param>
/// <param name="start">The source node.</param>
/// <returns>dist[v] = edges from start, or -1 if v cannot be reached.</returns>
/// <example>Bfs.Distances([[1], [0, 2], [1]], 0) returns [0, 1, 2].</example>
public static int[] Distances(int[][] adj, int start)
{
var dist = new int[adj.Length];
Array.Fill(dist, -1); // -1 marks "not reached yet"
dist[start] = 0; // 0 edges from start to itself
var queue = new Queue<int>();
queue.Enqueue(start); // O(1)
// Each pass settles one node. Invariant: the queue is ordered by distance.
while (queue.TryDequeue(out int u)) // O(1). False when the queue is empty.
{
foreach (int v in adj[u])
{
if (dist[v] == -1) // -1 means unseen, so mark it now, on push
{
dist[v] = dist[u] + 1; // + 1 for the edge from u to v
queue.Enqueue(v);
}
}
}
return dist;
}
}
Push, Pop and Peek are O(1). TryPop and TryPeek return false on an empty stack instead of throwing. A List<T> with Add and RemoveAt(Count - 1) works too.public static class Brackets
{
/// <summary>Checks that every bracket closes in the right order.</summary>
/// <param name="text">The text to check. Other characters are ignored.</param>
/// <returns>True when every bracket is matched.</returns>
/// <example>Brackets.Balanced("([]{})") returns true.</example>
public static bool Balanced(string text)
{
var open = new Stack<char>();
foreach (char ch in text)
{
if (ch is '(' or '[' or '{')
{
open.Push(ch); // O(1)
continue;
}
// Map each closer to its opener. '\0' stands for "not a bracket".
char want = ch switch { ')' => '(', ']' => '[', '}' => '{', _ => '\0' };
if (want == '\0')
{
continue;
}
// TryPop is false on an empty stack, which means a closer with no opener.
if (!open.TryPop(out char top) || top != want)
{
return false;
}
}
return open.Count == 0; // 0 left open means all matched
}
/// <summary>Shows that a Stack enumerates from the top down.</summary>
/// <returns>The stack's items in enumeration order.</returns>
/// <example>Brackets.EnumerationOrder() returns [3, 2, 1].</example>
public static List<int> EnumerationOrder()
{
var stack = new Stack<int>();
stack.Push(1); // sample data, pushed in the order 1, 2, 3
stack.Push(2);
stack.Push(3);
return [.. stack]; // top first, so 3, 2, 1
}
}
foreach, ToArray and ToList all give the newest item first. So new Stack<int>(list) followed by ToList() returns the list reversed. When a monotonic stack’s contents are the answer, check which order the problem wants.deque, Java has ArrayDeque, and C++ has std::deque. C# has nothing with O(1) push and pop at both ends on an array. You have two choices. LinkedList<T> is built in and O(1) at both ends, but every node is a separate heap object. A ring buffer is ten lines of code and much faster. Say which one you chose and why.public static class LinkedListDemo
{
/// <summary>Uses LinkedList as a deque and removes a node by its handle.</summary>
/// <returns>The values left, front to back.</returns>
/// <example>LinkedListDemo.Run() returns [0, 1, 3].</example>
public static List<int> Run()
{
var list = new LinkedList<int>([1, 2, 3]); // sample data
list.AddFirst(0); // O(1) [0, 1, 2, 3]
list.AddLast(4); // O(1) [0, 1, 2, 3, 4]
list.RemoveLast(); // O(1) [0, 1, 2, 3]
LinkedListNode<int> two = list.Find(2)!; // O(n) walks from the front
list.Remove(two); // O(1) given the node itself
return [.. list];
}
}
The node handle is the reason LinkedList<T> matters. Keep a Dictionary<TKey, LinkedListNode<T>> and you can unlink any node in O(1). That is the whole trick behind an LRU cache.
/// <summary>A double-ended queue of ints on a growable circular array.</summary>
public class RingDeque
{
private int[] _items = new int[4]; // 4 is a small start size. It doubles when full.
private int _head; // index of the front item
/// <summary>The number of items stored.</summary>
public int Count { get; private set; }
/// <summary>Adds a value at the front. O(1) amortised.</summary>
/// <param name="value">The value to add.</param>
/// <example>d.PushFront(5) makes 5 the front.</example>
public void PushFront(int value)
{
Grow();
// Step head back one slot. + Length keeps the index from going negative.
_head = (_head - 1 + _items.Length) % _items.Length;
_items[_head] = value;
Count++;
}
/// <summary>Adds a value at the back. O(1) amortised.</summary>
/// <param name="value">The value to add.</param>
/// <example>d.PushBack(5) makes 5 the back.</example>
public void PushBack(int value)
{
Grow();
_items[(_head + Count) % _items.Length] = value; // % wraps past the end
Count++;
}
/// <summary>Removes and returns the front value. O(1).</summary>
/// <returns>The front value.</returns>
/// <example>After PushBack(1) and PushBack(2), PopFront() returns 1.</example>
public int PopFront()
{
if (Count == 0) // 0 items means there is nothing to pop
{
throw new InvalidOperationException("The deque is empty.");
}
int value = _items[_head];
_head = (_head + 1) % _items.Length; // + 1 moves to the next slot, % wraps
Count--;
return value;
}
/// <summary>Removes and returns the back value. O(1).</summary>
/// <returns>The back value.</returns>
/// <example>After PushBack(1) and PushBack(2), PopBack() returns 2.</example>
public int PopBack()
{
if (Count == 0) // 0 items means there is nothing to pop
{
throw new InvalidOperationException("The deque is empty.");
}
Count--;
return _items[(_head + Count) % _items.Length]; // after Count--, the last slot
}
/// <summary>Doubles the array when it is full, copying items in queue order.</summary>
private void Grow()
{
if (Count < _items.Length)
{
return; // still room
}
var bigger = new int[_items.Length * 2]; // * 2 keeps pushes O(1) amortised
for (int i = 0; i < Count; i++) // i is a queue position. 0 = front.
{
bigger[i] = _items[(_head + i) % _items.Length];
}
_items = bigger;
_head = 0; // the front now sits at index 0
}
}
Dequeue returns the element with the smallest priority. Enqueue and Dequeue are O(log n). Peek is O(1). The items inside are not sorted, only heap-ordered.If you know Java, this is PriorityQueue. C++: std::priority_queue, which is a max-heap by default. Python: heapq, which is functions over a list.
public static class Heaps
{
/// <summary>Returns the k largest values, largest first, with a size-k min-heap.</summary>
/// <param name="nums">The values.</param>
/// <param name="k">How many to keep. Assumed to be 0 or more.</param>
/// <returns>The k largest values in descending order.</returns>
/// <example>Heaps.TopK([5, 1, 9, 3, 7], 2) returns [9, 7].</example>
public static List<int> TopK(int[] nums, int k)
{
// Element and priority are the same int. The root is the smallest value kept.
var heap = new PriorityQueue<int, int>();
foreach (int x in nums)
{
heap.Enqueue(x, x); // O(log k)
if (heap.Count > k)
{
heap.Dequeue(); // O(log k) evict the smallest
}
}
// Dequeue gives the smallest first, so reverse at the end for largest first.
var result = new List<int>(heap.Count);
while (heap.TryDequeue(out int value, out _))
{
result.Add(value);
}
result.Reverse();
return result;
}
/// <summary>Drains values largest first, using a reversed comparer.</summary>
/// <param name="values">The values.</param>
/// <returns>The values in descending order.</returns>
/// <example>Heaps.MaxFirst([3, 7, 5]) returns [7, 5, 3].</example>
public static List<int> MaxFirst(int[] values)
{
// b.CompareTo(a) flips the order. Safer than negating, which overflows at MinValue.
var descending = Comparer<int>.Create((a, b) => b.CompareTo(a));
var heap = new PriorityQueue<int, int>(descending);
foreach (int v in values)
{
heap.Enqueue(v, v); // O(log n)
}
var order = new List<int>();
while (heap.Count > 0) // 0 left means the heap is drained
{
order.Add(heap.Dequeue()); // O(log n)
}
return order;
}
/// <summary>Builds a heap from pairs in one O(n) step instead of n pushes.</summary>
/// <param name="names">The elements.</param>
/// <param name="priorities">The priority of each element, by position.</param>
/// <returns>The element with the lowest priority.</returns>
/// <example>Heaps.Heapify(["b", "a", "c"], [2, 1, 3]) returns "a".</example>
public static string Heapify(string[] names, int[] priorities)
{
var pairs = names.Zip(priorities); // (element, priority) tuples
var heap = new PriorityQueue<string, int>(pairs); // O(n) heapify
return heap.Peek(); // O(1)
}
}
-int.MinValue overflows back to int.MinValue.(cost, seq). Value tuples compare element by element.UnorderedItems is exactly what it says. Only Dequeue gives sorted order.var tasks = new PriorityQueue<string, (int Cost, int Seq)>();
tasks.Enqueue("write", (2, 0)); // Seq is an arrival counter. It breaks cost ties.
tasks.Enqueue("read", (1, 1));
string next = tasks.Dequeue(); // "read", the lowest cost
SortedSet<T> holds unique values. SortedDictionary<TKey, TValue> maps sorted keys to values.If you know Java, these are TreeSet and TreeMap. C++: std::set and std::map.
public static class Ordered
{
/// <summary>Finds the smallest value in the set that is at least x.</summary>
/// <param name="set">The sorted set.</param>
/// <param name="x">The lower bound.</param>
/// <returns>The ceiling of x, or null when every value is below x.</returns>
/// <example>Ordered.Ceiling(new SortedSet<int> { 1, 5, 9 }, 6) returns 9.</example>
public static int? Ceiling(SortedSet<int> set, int x)
{
// A live view of [x, int.MaxValue]. MaxValue is the largest possible upper end.
foreach (int value in set.GetViewBetween(x, int.MaxValue))
{
return value; // the view is sorted, so its first value is the ceiling
}
return null;
}
/// <summary>Finds the largest value in the set that is at most x.</summary>
/// <param name="set">The sorted set.</param>
/// <param name="x">The upper bound.</param>
/// <returns>The floor of x, or null when every value is above x.</returns>
/// <example>Ordered.Floor(new SortedSet<int> { 1, 5, 9 }, 6) returns 5.</example>
public static int? Floor(SortedSet<int> set, int x)
{
// int.MinValue is the smallest possible lower end. Reverse walks from the top.
foreach (int value in set.GetViewBetween(int.MinValue, x).Reverse())
{
return value;
}
return null;
}
/// <summary>Counts words and lists them in key order.</summary>
/// <param name="text">Words separated by spaces.</param>
/// <returns>"word=count" strings, sorted by word.</returns>
/// <example>Ordered.WordCounts("b a b") returns ["a=1", "b=2"].</example>
public static List<string> WordCounts(string text)
{
// StringComparer.Ordinal compares raw char codes, which is fast and predictable.
var counts = new SortedDictionary<string, int>(StringComparer.Ordinal);
foreach (string word in text.Split(' ', StringSplitOptions.RemoveEmptyEntries))
{
counts[word] = counts.GetValueOrDefault(word) + 1; // O(log n). + 1 for this word.
}
return [.. counts.Select(kv => $"{kv.Key}={kv.Value}")]; // already in key order
}
}
SortedSet holds no duplicates, so store (value, id) tuples to fake a multiset. SortedDictionary has no floor or ceiling method, so keep a SortedSet of keys beside it when you need one. And Min on an empty set returns default, which is 0 for ints, not an error. That is why the helpers above use a foreach.SortedList<TKey, TValue> is a third option. It is two sorted arrays, so lookups are O(log n) but inserts are O(n). It only wins when you build once and then read by index.
int[] is a fixed-size block of memory, zeroed when created. C# has two kinds of grid. A jagged array int[][] is an array of row arrays. A 2D array int[,] is one rectangular block, indexed as grid[r, c]. Interview code and every LeetCode signature use jagged arrays.public static class Grids
{
/// <summary>Builds a jagged grid. Every row must be created on its own.</summary>
/// <param name="rows">The number of rows.</param>
/// <param name="cols">The number of columns.</param>
/// <returns>A rows by cols grid of zeros.</returns>
/// <example>Grids.Jagged(2, 3)[1].Length returns 3.</example>
public static int[][] Jagged(int rows, int cols)
{
var grid = new int[rows][]; // rows slots, each one still null
for (int r = 0; r < rows; r++) // r is a row index. 0 is the top row.
{
grid[r] = new int[cols]; // a fresh zeroed row, never shared
}
return grid;
}
/// <summary>Sums a jagged grid. Rows may differ in length.</summary>
/// <param name="grid">The grid.</param>
/// <returns>The sum of every cell.</returns>
/// <example>Grids.SumJagged([[1, 2], [3]]) returns 6.</example>
public static int SumJagged(int[][] grid)
{
int total = 0; // 0 is the sum of no cells
foreach (int[] row in grid)
{
foreach (int cell in row)
{
total += cell;
}
}
return total;
}
/// <summary>Sums a rectangular 2D array, using GetLength for each dimension.</summary>
/// <param name="grid">The grid.</param>
/// <returns>The sum of every cell.</returns>
/// <example>Grids.Sum2D(new int[,] { { 1, 2 }, { 3, 4 } }) returns 10.</example>
public static int Sum2D(int[,] grid)
{
int total = 0; // 0 is the sum of no cells
// GetLength(0) counts rows and GetLength(1) counts columns. Length is rows * cols.
for (int r = 0; r < grid.GetLength(0); r++)
{
for (int c = 0; c < grid.GetLength(1); c++)
{
total += grid[r, c];
}
}
return total;
}
}
int[][]
grid.Length is the row count. grid[r].Length is that row’s width.new int[rows][] gives null rows. Create each row in a loop.int[,]
Length is the total cell count, not the row count. Use GetLength(0) and GetLength(1).foreach see it as one flat run of cells.Useful array helpers: Array.Fill(a, v) sets every slot, Array.Copy and a.Clone() copy, Array.Reverse reverses in place, and Array.IndexOf scans in O(n). Array.Sort and Array.BinarySearch are in the idioms.
await. Use it inside one method.public static class Spans
{
/// <summary>Checks two lowercase strings are anagrams with a stack counter.</summary>
/// <param name="a">The first word, letters a to z only.</param>
/// <param name="b">The second word, letters a to z only.</param>
/// <returns>True when both use the same letters the same number of times.</returns>
/// <example>Spans.IsAnagram("listen", "silent") returns true.</example>
public static bool IsAnagram(string a, string b)
{
if (a.Length != b.Length)
{
return false; // different lengths can never match
}
Span<int> counts = stackalloc int[26]; // 26 letters, on the stack, no allocation
for (int i = 0; i < a.Length; i++) // i walks both strings together
{
counts[a[i] - 'a']++; // - 'a' maps 'a'..'z' to 0..25
counts[b[i] - 'a']--;
}
foreach (int c in counts)
{
if (c != 0) // 0 means the letter balanced out
{
return false;
}
}
return true;
}
/// <summary>Sums all but the first and last items through an O(1) slice.</summary>
/// <param name="values">The values.</param>
/// <returns>The sum of the inner values, or 0 when there are fewer than 2.</returns>
/// <example>Spans.SumInner([10, 1, 2, 3, 10]) returns 6.</example>
public static int SumInner(int[] values)
{
if (values.Length < 2) // 2 = a first and a last to drop
{
return 0;
}
ReadOnlySpan<int> inner = values.AsSpan(1..^1); // 1 skips the first, ^1 the last
int total = 0; // 0 is the sum of nothing
foreach (int v in inner)
{
total += v;
}
return total;
}
}
System.Text. Append is O(1) amortised. ToString copies once at the end. Strings themselves are immutable, so every += builds a brand new string.public static class ConcatSlow
{
/// <summary>Joins 0..n-1. O(n^2).</summary>
/// <param name="n">How many digits.</param>
/// <returns>The digits as one string.</returns>
/// <example>ConcatSlow.Digits(4) returns "0123".</example>
public static string Digits(int n)
{
string s = "";
for (int i = 0; i < n; i++)
{
s += i; // copies ALL of s
}
return s;
}
}
using System.Text;
public static class ConcatFast
{
/// <summary>Joins 0..n-1. O(n).</summary>
/// <param name="n">How many digits.</param>
/// <returns>The digits as one string.</returns>
/// <example>ConcatFast.Digits(4) returns "0123".</example>
public static string Digits(int n)
{
var sb = new StringBuilder();
for (int i = 0; i < n; i++)
{
sb.Append(i); // O(1) amortised
}
return sb.ToString(); // one copy
}
}
When you already have the pieces, string.Join(",", parts) and string.Concat(parts) do the same job in one call. To build a string from characters, fill a char[] and call new string(chars).
a[start..end] takes the items from start up to but not including end. ^1 means “one from the end”, so a[^1] is the last item. Either side may be left out. Ranges work on arrays, strings, List<T> and spans.public static class Slices
{
/// <summary>Shows the range forms on an array. Each one returns a NEW array.</summary>
/// <returns>Each slice joined with commas.</returns>
/// <example>Slices.Demo() returns ["1,2,3", "0,1", "4,5", "1,2,3,4"].</example>
public static List<string> Demo()
{
int[] a = [0, 1, 2, 3, 4, 5]; // indices 0..5. ^1 is index 5.
return
[
string.Join(",", a[1..4]), // 1 is in, 4 is out: 1, 2, 3
string.Join(",", a[..2]), // from the start up to index 2
string.Join(",", a[^2..]), // ^2 = Length - 2, so the last two
string.Join(",", a[1..^1]), // drop the first and the last
];
}
/// <summary>Moves the first k items to the back. O(n) time and space.</summary>
/// <param name="items">The items.</param>
/// <param name="k">How far to rotate. Assumed to be 0 or more.</param>
/// <returns>A new rotated array.</returns>
/// <example>Slices.RotateLeft([1, 2, 3, 4, 5], 2) returns [3, 4, 5, 1, 2].</example>
public static int[] RotateLeft(int[] items, int k)
{
if (items.Length == 0)
{
return []; // 0 items: nothing to rotate, and % 0 throws
}
k %= items.Length; // % makes a k larger than the length harmless
return [.. items[k..], .. items[..k]]; // the tail, then the head
}
/// <summary>Checks a palindrome with two pointers. O(n) time, O(1) space.</summary>
/// <param name="text">The text to check.</param>
/// <returns>True when it reads the same both ways.</returns>
/// <example>Slices.IsPalindrome("racecar") returns true.</example>
public static bool IsPalindrome(string text)
{
// left starts at index 0, right at the last index (Length - 1). Both move inward.
for (int left = 0, right = text.Length - 1; left < right; left++, right--)
{
if (text[left] != text[right])
{
return false;
}
}
return true;
}
}
List<T> copies, so it costs O(k). A range on a span is a view and costs O(1). a.AsSpan(1..^1) and s.AsSpan(2) are the zero-copy forms.a[::2] or a[::-1]. Use a loop, Array.Reverse, or LINQ Reverse().a[2:99] quietly stops at the end. C#’s a[2..99] throws ArgumentOutOfRangeException. So does a start after the end.a[-1] throws. Write a[^1].source.AsSpan().CopyTo(dest.AsSpan(i)) or Array.Copy.a[i..j] has j - i items, and a[..k] plus a[k..] is the whole array for any valid k.public static class PrefixCountSlow
{
/// <summary>Counts where pat starts.</summary>
/// <param name="s">The text.</param>
/// <param name="pat">The pattern.</param>
/// <returns>The number of matches.</returns>
/// <example>PrefixCountSlow.Count("abab", "ab")
/// returns 2.</example>
public static int Count(string s, string pat)
{
int hits = 0; // 0 matches so far
for (int i = 0; i < s.Length; i++)
{
// s[i..] COPIES the tail
if (s[i..].StartsWith(pat,
StringComparison.Ordinal))
{
hits++;
}
}
return hits;
}
}
public static class PrefixCountFast
{
/// <summary>Counts where pat starts.</summary>
/// <param name="s">The text.</param>
/// <param name="pat">The pattern.</param>
/// <returns>The number of matches.</returns>
/// <example>PrefixCountFast.Count("abab", "ab")
/// returns 2.</example>
public static int Count(string s, string pat)
{
int hits = 0; // 0 matches so far
for (int i = 0; i < s.Length; i++)
{
// a view of the tail, no copy
if (s.AsSpan(i).StartsWith(
pat.AsSpan()))
{
hits++;
}
}
return hits;
}
}
The same trap appears in recursion. Solve(items[1..]) copies the array at every level and turns O(n) into O(n²). Pass the array plus a start index instead. That is why every template on this site threads indices, from backtracking to binary search.
AsSpan.”Know this list. Most accidental time-limit failures are one line of it.
a[i], list[i], s[i], .Count, .Length.list.Add(x) and list.RemoveAt(list.Count - 1), amortised.Queue.Enqueue, Queue.Dequeue, Stack.Push, Stack.Pop, Peek.LinkedList.AddFirst, AddLast, RemoveFirst, RemoveLast, and Remove(node).PriorityQueue.Peek. StringBuilder.Append, amortised. Slicing a span.Dictionary: indexer, TryGetValue, ContainsKey, Remove, TryAdd.HashSet: Add, Contains, Remove.PriorityQueue.Enqueue, Dequeue.SortedSet and SortedDictionary: add, remove, lookup, Min, Max.Array.BinarySearch and List.BinarySearch on sorted data.list.Insert(0, x), list.RemoveAt(0), list.Remove(x), list.Contains(x), IndexOf.Dictionary.ContainsValue. LinkedList.Find. PriorityQueue.Remove.Substring, ToArray, ToList.new PriorityQueue(pairs) heapify. string.Join, sb.ToString().Count(), Min(), Max(), Sum(), Contains() on a sequence.Array.Sort and List.Sort: introsort, in place, not stable.OrderBy, Order: stable, and it allocates a new sequence.s += x in a loop. list.RemoveAt(0) or list.Contains in a loop.s[i..] inside a loop or a recursion.list.Contains(x) inside a loop over the same list, and list.RemoveAt(0) as a queue. Both turn a linear algorithm into a quadratic one. Both look innocent, and a reviewer spots both at once.A struct is a value type. Reading one out of a list, an array element’s property, or a dictionary gives you a copy. Changing the copy changes nothing else.
Reading the figure. Blue boxes are what the list holds. Amber is your local variable p. Green is a heap object. On the left, the arrow is a copy of the data, so the two boxes change on their own. On the right, both arrows point at the same object, so an edit through either name is seen through both.
using System.Runtime.InteropServices;
/// <summary>A MUTABLE struct. This is the shape that causes the copy trap.</summary>
public struct MutablePoint
{
public int X;
public int Y;
}
public static class StructTrap
{
/// <summary>Edits a copy of points[0]. The list does not change.</summary>
/// <returns>The X still stored in the list.</returns>
/// <example>StructTrap.EditCopy() returns 0.</example>
public static int EditCopy()
{
List<MutablePoint> points = [new MutablePoint()]; // one point at (0, 0)
MutablePoint p = points[0]; // the indexer returns a COPY of the struct
p.X = 5; // 5 is sample data. This changes the copy only.
return points[0].X; // still 0
}
/// <summary>Writes the edited copy back: read, change, store.</summary>
/// <returns>The X stored in the list.</returns>
/// <example>StructTrap.WriteBack() returns 5.</example>
public static int WriteBack()
{
List<MutablePoint> points = [new MutablePoint()];
MutablePoint p = points[0];
p.X = 5; // 5 is sample data
points[0] = p; // store the edited copy back into slot 0
return points[0].X;
}
/// <summary>Edits in place through a span over the list's own array.</summary>
/// <returns>The X stored in the list.</returns>
/// <example>StructTrap.EditInPlace() returns 5.</example>
public static int EditInPlace()
{
List<MutablePoint> points = [new MutablePoint()];
// AsSpan exposes the backing array. Do not Add or Remove while you hold it.
CollectionsMarshal.AsSpan(points)[0].X = 5; // slot 0, sample value 5
return points[0].X;
}
}
The compiler catches the most direct form. These lines do not build:
points[0].X = 5; // error CS1612: cannot modify the return value
foreach (var p in points) p.X = 1; // error CS1654: p is a read-only copy
readonly record struct and replace them with with: points[0] = points[0] with { X = 5 };. For a list of things you edit in place, use a class.public static class RemoveEvens
{
/// <summary>Removes inside foreach. This throws InvalidOperationException.</summary>
/// <param name="items">The list to edit.</param>
/// <returns>Never returns normally.</returns>
/// <example>RemoveEvens.InsideForeach([1, 2, 3]) throws.</example>
public static List<int> InsideForeach(List<int> items)
{
foreach (int x in items)
{
if (x % 2 == 0) // % 2 == 0 means even
{
items.Remove(x); // the next MoveNext sees the change and throws
}
}
return items;
}
/// <summary>Walks backwards, so a removal never shifts an item not yet visited.</summary>
/// <param name="items">The list to edit.</param>
/// <returns>The same list, evens removed.</returns>
/// <example>RemoveEvens.Backwards([1, 2, 3, 4]) returns [1, 3].</example>
public static List<int> Backwards(List<int> items)
{
// i starts at the last index (Count - 1) and ends at 0. Items after i are done.
for (int i = items.Count - 1; i >= 0; i--)
{
if (items[i] % 2 == 0) // % 2 == 0 means even
{
items.RemoveAt(i);
}
}
return items;
}
/// <summary>The idiomatic form. One O(n) pass with no repeated shifting.</summary>
/// <param name="items">The list to edit.</param>
/// <returns>The same list, evens removed.</returns>
/// <example>RemoveEvens.WithRemoveAll([1, 2, 3, 4]) returns [1, 3].</example>
public static List<int> WithRemoveAll(List<int> items)
{
items.RemoveAll(x => x % 2 == 0); // % 2 == 0 means even
return items;
}
}
RemoveAt shifts the tail. RemoveAll compacts in one pass. One odd exception: since .NET Core 3.0, Dictionary.Remove during a foreach over the same dictionary is allowed. Adding a new key still throws.An int is 32 bits. Arithmetic is unchecked by default, so it wraps around silently. No exception, just a wrong answer.
public static class Overflow
{
/// <summary>Adds 1 to int.MaxValue. It wraps silently to int.MinValue.</summary>
/// <returns>The wrapped value.</returns>
/// <example>Overflow.Wraps() returns -2147483648.</example>
public static int Wraps()
{
int big = int.MaxValue; // 2^31 - 1, the largest int
big++; // + 1 past the top wraps to the bottom, no error
return big;
}
/// <summary>The same add inside checked. It throws OverflowException.</summary>
/// <returns>Never returns normally.</returns>
/// <example>Overflow.Checked() throws OverflowException.</example>
public static int Checked()
{
int big = int.MaxValue; // the largest int
return checked(big + 1); // + 1 overflows. checked turns the wrap into an exception.
}
/// <summary>Sums ints into a long, so the total cannot wrap.</summary>
/// <param name="values">The values.</param>
/// <returns>The exact total.</returns>
/// <example>Overflow.SumLong([int.MaxValue, 1]) returns 2147483648.</example>
public static long SumLong(int[] values)
{
long total = 0; // 0 is the empty sum. A long holds up to about 9.2e18.
foreach (int v in values)
{
total += v;
}
return total;
}
/// <summary>The midpoint without overflow. lo + hi can pass int.MaxValue.</summary>
/// <param name="lo">The low end.</param>
/// <param name="hi">The high end, at least lo.</param>
/// <returns>The midpoint, rounded down.</returns>
/// <example>Overflow.Mid(2_000_000_000, 2_100_000_000) returns 2050000000.</example>
public static int Mid(int lo, int hi) => lo + (hi - lo) / 2; // / 2 halves the gap
}
a * b with two ints is computed in 32 bits. Write (long)a * b to widen before multiplying.Math.Abs(int.MinValue) throws OverflowException, because +2³¹ does not fit.a - b overflows when the values are far apart. Always use a.CompareTo(b).long.Covered above. Each += copies the whole string so far, so the loop is O(n²). Use a StringBuilder, or collect pieces and call string.Join once.
Reading counts[key] for a missing key throws KeyNotFoundException. This is the opposite of Python’s Counter. Read with GetValueOrDefault(key), or test with TryGetValue first.
Dijkstra wants to lower a node’s distance in place. PriorityQueue cannot do that. .NET 9 added Remove, but it is an O(n) scan. The standard fix is lazy deletion: push a new entry and skip the stale one when it comes out.
public static class LazyDijkstra
{
/// <summary>Shortest distances, skipping stale heap entries instead of decrease-key.</summary>
/// <param name="n">The number of nodes, 0..n-1.</param>
/// <param name="edges">Directed edges as [from, to, weight], weights 0 or more.</param>
/// <param name="source">The start node.</param>
/// <returns>dist[v], or long.MaxValue when v cannot be reached.</returns>
/// <example>LazyDijkstra.Run(3, [[0,1,4], [0,2,1], [2,1,1]], 0) returns [0, 2, 1].</example>
public static long[] Run(int n, int[][] edges, int source)
{
var adj = new List<(int To, int W)>[n];
for (int u = 0; u < n; u++) // u is a node id. 0 is the first one.
{
adj[u] = [];
}
foreach (int[] e in edges)
{
adj[e[0]].Add((e[1], e[2])); // [0] from, [1] to, [2] weight
}
var dist = new long[n];
Array.Fill(dist, long.MaxValue); // MaxValue stands for "no path yet"
dist[source] = 0; // 0 cost to stay at the source
var heap = new PriorityQueue<int, long>();
heap.Enqueue(source, 0); // 0 is the source's distance
while (heap.TryDequeue(out int u, out long d))
{
// A node can sit in the heap many times. Only the entry that matches dist is live.
if (d > dist[u])
{
continue;
}
foreach (var (v, w) in adj[u])
{
long candidate = d + w;
if (candidate < dist[v])
{
dist[v] = candidate;
heap.Enqueue(v, candidate); // a NEW entry. The old one goes stale.
}
}
}
return dist;
}
}
LINQ reads well and costs more than it looks. Two effects matter in interviews.
public static class LinqCost
{
/// <summary>Counts how often a deferred query runs its selector.</summary>
/// <returns>The selector call count after two passes over 3 items.</returns>
/// <example>LinqCost.DeferredRuns() returns 6.</example>
public static int DeferredRuns()
{
int calls = 0; // 0 calls before anything runs
int[] data = [1, 2, 3]; // sample data, 3 items
// Nothing runs on this line. The query is only a recipe.
IEnumerable<int> doubled = data.Select(x => { calls++; return x * 2; });
int total = doubled.Sum(); // runs the selector 3 times
int biggest = doubled.Max(); // runs it 3 MORE times
return calls; // 6, not 3
}
/// <summary>Keeps values of a found in other. List.Contains makes it O(n * m).</summary>
/// <param name="a">The values to filter.</param>
/// <param name="other">The values to keep.</param>
/// <returns>The kept values, in a's order.</returns>
/// <example>LinqCost.CommonSlow([1, 2, 3], [2, 3, 4]) returns [2, 3].</example>
public static List<int> CommonSlow(int[] a, List<int> other) =>
[.. a.Where(x => other.Contains(x))]; // O(m) scan for every x
/// <summary>The same filter with a HashSet. O(n + m).</summary>
/// <param name="a">The values to filter.</param>
/// <param name="other">The values to keep.</param>
/// <returns>The kept values, in a's order.</returns>
/// <example>LinqCost.CommonFast([1, 2, 3], [2, 3, 4]) returns [2, 3].</example>
public static List<int> CommonFast(int[] a, List<int> other)
{
var lookup = new HashSet<int>(other); // O(m), once
return [.. a.Where(lookup.Contains)]; // O(1) average per x
}
}
ToList() once if you will read the result twice.Count() is not Count. On a plain sequence, Count() walks every item. list.Count is a stored number.Contains, Min, Max, ElementAt and Last are O(n) on a sequence. One inside a loop is a hidden O(n²).for is faster.First() and Single() throw on an empty sequence. Use FirstOrDefault() when empty is possible.Each thread has a fixed stack. The default is about 1 MB on Windows. Linux and macOS often give the main thread more, but worker threads get less. A recursive DFS on a 100,000-node chain can overflow it. A StackOverflowException cannot be caught. The process just dies.
public static class DeepRecursion
{
/// <summary>Measures a tree's height with an explicit Stack, so depth is unlimited.</summary>
/// <param name="root">The root, or null.</param>
/// <returns>The number of nodes on the longest root-to-leaf path.</returns>
/// <example>DeepRecursion.HeightIterative(new TreeNode(1, new TreeNode(2))) is 2.</example>
public static int HeightIterative(TreeNode? root)
{
int best = 0; // 0 is the height of an empty tree
var stack = new Stack<(TreeNode Node, int Depth)>();
if (root is not null)
{
stack.Push((root, 1)); // 1 = the root is on level one
}
// Each pass visits one node. Invariant: every pushed pair has its true depth.
while (stack.TryPop(out var top))
{
best = Math.Max(best, top.Depth);
if (top.Node.Left is not null) stack.Push((top.Node.Left, top.Depth + 1));
if (top.Node.Right is not null) stack.Push((top.Node.Right, top.Depth + 1));
}
return best;
}
/// <summary>Runs work on a new thread with a bigger stack, for deep recursion.</summary>
/// <param name="work">The function to run.</param>
/// <param name="megabytes">The stack size in megabytes.</param>
/// <returns>Whatever work returns.</returns>
/// <example>DeepRecursion.WithBigStack(() => 42, 64) returns 42.</example>
public static TResult WithBigStack<TResult>(Func<TResult> work, int megabytes)
{
TResult result = default!;
// maxStackSize is in bytes. 1024 * 1024 turns megabytes into bytes.
var thread = new Thread(() => result = work(), megabytes * 1024 * 1024);
thread.Start();
thread.Join(); // wait for the worker to finish before reading result
return result;
}
}
public static class IntMath
{
/// <summary>A remainder that is never negative, like Python's %.</summary>
/// <param name="a">The dividend.</param>
/// <param name="m">The modulus, above 0.</param>
/// <returns>A value in 0..m-1.</returns>
/// <example>IntMath.FloorMod(-7, 3) returns 2.</example>
public static int FloorMod(int a, int m) => ((a % m) + m) % m; // + m lifts a negative
/// <summary>Division that rounds down, like Python's //.</summary>
/// <param name="a">The dividend.</param>
/// <param name="b">The divisor, not 0.</param>
/// <returns>The floor of a / b.</returns>
/// <example>IntMath.FloorDiv(-7, 2) returns -4.</example>
public static int FloorDiv(int a, int b)
{
int q = a / b; // C# truncates toward 0, so -7 / 2 is -3
// Step down by 1 when there is a remainder and the signs differ.
bool roundedUp = a % b != 0 && (a < 0) != (b < 0); // 0 = divides evenly
return roundedUp ? q - 1 : q;
}
}
-7 / 2 is -3 and -7 % 3 is -1. C# truncates toward zero, like Java and C++. Python gives -4 and 2.0.1 + 0.2 != 0.3 for double. Stay in integers, compare with a tolerance, or use decimal for money.c - 'a' is an int. Going back needs a cast: (char)('a' + i).== on two class instances compares references, except for string and records, which compare values.public static class KeyEquality
{
/// <summary>Looks up an equal array in a set. Arrays compare by reference.</summary>
/// <returns>Whether the equal array was found.</returns>
/// <example>KeyEquality.ArrayKey() returns false.</example>
public static bool ArrayKey()
{
var seen = new HashSet<int[]> { new[] { 1, 2 } }; // sample key (1, 2)
return seen.Contains([1, 2]); // a different array object, so false
}
/// <summary>Looks up an equal tuple in a set. Value tuples compare by value.</summary>
/// <returns>Whether the equal tuple was found.</returns>
/// <example>KeyEquality.TupleKey() returns true.</example>
public static bool TupleKey()
{
var seen = new HashSet<(int Row, int Col)> { (1, 2) }; // sample key (1, 2)
return seen.Contains((1, 2)); // same values, same hash, so true
}
}
This is why every grid solution on this site keys on (row, col) tuples or a record struct. For a list of values as a key, build a string such as string.Join(",", values).
List.Sort is unstable. Use OrderBy when ties must keep their order.new int[n][] needs each row created.Min() on an empty sequence throws. SortedSet.Min on an empty set returns 0 instead.string.Compare and OrderBy(s => s) use the current culture. Pass StringComparer.Ordinal for predictable results.Array.BinarySearch with duplicates returns some matching index, not the first. See below.public static class Sorting
{
/// <summary>Sorts intervals by start with a Comparison lambda.</summary>
/// <param name="intervals">Intervals as [start, end].</param>
/// <returns>The same array, sorted by start.</returns>
/// <example>Sorting.ByStart([[5, 6], [1, 3]])[0] returns [1, 3].</example>
public static int[][] ByStart(int[][] intervals)
{
// [0] is the start. CompareTo never overflows, unlike a[0] - b[0].
Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
return intervals;
}
/// <summary>Sorts by length, then A to Z, with a stable LINQ sort.</summary>
/// <param name="words">The words.</param>
/// <returns>A new sorted list.</returns>
/// <example>Sorting.ByLengthThenText(["cc", "a", "ab"]) returns ["a", "ab", "cc"].</example>
public static List<string> ByLengthThenText(string[] words) =>
[.. words.OrderBy(w => w.Length).ThenBy(w => w, StringComparer.Ordinal)];
/// <summary>Sorts descending in place without a separate Reverse call.</summary>
/// <param name="values">The values.</param>
/// <returns>The same array, largest first.</returns>
/// <example>Sorting.Descending([3, 1, 2]) returns [3, 2, 1].</example>
public static int[] Descending(int[] values)
{
Array.Sort(values, (a, b) => b.CompareTo(a)); // b first flips the order
return values;
}
/// <summary>Sorts one array by the values in a parallel key array, in place.</summary>
/// <param name="items">The items to reorder.</param>
/// <param name="keys">The sort key for each item, by position.</param>
/// <returns>The items, reordered to follow the sorted keys.</returns>
/// <example>Sorting.ByKeys(["c", "a", "b"], [3, 1, 2]) returns ["a", "b", "c"].</example>
public static string[] ByKeys(string[] items, int[] keys)
{
Array.Sort(keys, items); // sorts keys and moves items the same way
return items;
}
}
To sort by two keys in one comparer, compare tuples: (a.Len, a.Id).CompareTo((b.Len, b.Id)). Value tuples compare element by element, left to right.
Reading the figure. Amber is the index Array.BinarySearch happened to land on. Green is the first 3, which is what LowerBound returns. The violet arrow marks the insertion point for a missing 4. BinarySearch returns its bitwise complement, -5, and ~ turns it back into 4.
public static class Search
{
/// <summary>The insertion point, using Array.BinarySearch and the ~ operator.</summary>
/// <param name="sorted">An ascending array.</param>
/// <param name="value">The value to look for.</param>
/// <returns>An index of value if present, else where it would be inserted.</returns>
/// <example>Search.InsertionPoint([1, 3, 5], 4) returns 2.</example>
public static int InsertionPoint(int[] sorted, int value)
{
int i = Array.BinarySearch(sorted, value); // O(log n)
// A miss returns ~insertionPoint, which is negative. ~ undoes it.
return i >= 0 ? i : ~i; // 0 or more means found
}
/// <summary>The FIRST index whose value is at least value. O(log n).</summary>
/// <param name="sorted">An ascending array.</param>
/// <param name="value">The value to look for.</param>
/// <returns>The first such index, or Length when every value is smaller.</returns>
/// <example>Search.LowerBound([1, 3, 3, 3, 5], 3) returns 1.</example>
public static int LowerBound(int[] sorted, int value)
{
// Half-open window [lo, hi). hi = Length means "past the end".
int lo = 0, hi = sorted.Length;
// Invariant: everything before lo is below value. Everything from hi on is not.
while (lo < hi)
{
int mid = lo + (hi - lo) / 2; // / 2 halves the gap without overflow
if (sorted[mid] < value)
{
lo = mid + 1; // + 1: mid is too small, so skip past it
}
else
{
hi = mid; // mid might be the answer, so keep it
}
}
return lo;
}
}
Array.BinarySearch is fine for “is it there?” and for an insertion point. For first or last occurrence, it is wrong on duplicates. The eight-line loop above is the version interviewers expect. See Pattern 11.public static class GridIdioms
{
// The four moves: down, up, right, left. (1, 0) adds 1 to the row, and so on.
private static readonly (int Dr, int Dc)[] Directions = [(1, 0), (-1, 0), (0, 1), (0, -1)];
/// <summary>Counts open cells (value 0) reachable from the top-left corner.</summary>
/// <param name="grid">The grid. 0 is open, anything else is a wall.</param>
/// <returns>The number of reachable open cells.</returns>
/// <example>GridIdioms.Reachable([[0, 0, 1], [1, 0, 1], [1, 0, 0]]) returns 5.</example>
public static int Reachable(int[][] grid)
{
if (grid.Length == 0 || grid[0][0] != 0) // [0][0] is the start. 0 means open.
{
return 0;
}
var seen = new HashSet<(int, int)> { (0, 0) }; // tuples hash by value
var queue = new Queue<(int R, int C)>();
queue.Enqueue((0, 0)); // start at the top-left
while (queue.TryDequeue(out var cell))
{
foreach (var (dr, dc) in Directions)
{
int r = cell.R + dr, c = cell.C + dc;
bool inside = r >= 0 && r < grid.Length && c >= 0 && c < grid[r].Length;
// seen.Add is false for a repeat, so it tests and marks in one call.
if (inside && grid[r][c] == 0 && seen.Add((r, c)))
{
queue.Enqueue((r, c));
}
}
}
return seen.Count;
}
}
TryGetValue when a missing key needs its own branch.GetValueOrDefault when a missing key should read as zero.CollectionsMarshal.GetValueRefOrAddDefault to count with one hash.HashSet.Add returns bool, so test and insert happen together.record struct as keys. Never arrays.Array.Fill(dist, int.MaxValue) to seed a distance table.foreach (var (key, value) in dict) deconstructs each pair.Math.Max, Math.Min, int.MaxValue as sentinels. Watch the + 1 overflow.int is 32 bits and wraps silently. Use long for sums and products, or checked to fail loudly. Say so when the interviewer thinks in Python.StringBuilder or a char[].Array.Sort and List.Sort are unstable. OrderBy is stable.Dictionary and HashSet order is not guaranteed. Sort before you return if the output order matters.SortedSet of tuples, and lazy deletion.SortedSet and SortedDictionary are red-black trees, which Python lacks.set.Contains is O(1) and list.Contains is O(n). This one line decides more outcomes than any other.GetValueOrDefault and TryGetValue.LinkedList.long, lo + (hi - lo) / 2, and CompareTo.+= in a loop.