📘 C# DSA Cheat Sheet

1️⃣ Time & Space Complexity (Must Know)

Complexity	Meaning
O(1)	Constant
O(log n)	Logarithmic
O(n)	Linear
O(n log n)	Merge/Quick sort
O(n²)	Nested loops
O(2ⁿ)	Exponential

2️⃣ Arrays

Declaration

int[] arr = new int[5];
int[] arr2 = {1, 2, 3};

Access → O(1)

arr[0];

Traverse → O(n)

foreach (var x in arr) { }

Resize → Use List instead

3️⃣ List

var list = new List<int>();
list.Add(1);
list.Remove(1);

Complexities

4️⃣ Dictionary<TKey, TValue>

var dict = new Dictionary<int, string>();
dict[1] = "One";

Complexities

5️⃣ HashSet

var set = new HashSet<int>();
set.Add(1);

• Duplicate detection

• Fast membership checks

6️⃣ Stack (LIFO)

var stack = new Stack<int>();
stack.Push(1);
stack.Pop();

• DFS

• Balanced parentheses

• Backtracking

7️⃣ Queue (FIFO)

var queue = new Queue<int>();
queue.Enqueue(1);
queue.Dequeue();

• BFS

• Scheduling

8️⃣ LinkedList

var list = new LinkedList<int>();

• Frequent insert/delete in middle

• Not for random access

9️⃣ Sorting

Built-in

Array.Sort(arr);
list.Sort();

Custom Sort

list.Sort((a, b) => a - b);

🔟 Binary Search

Array.BinarySearch(arr, target);

• Sorted array

1️⃣1️⃣ Recursion Template

int Factorial(int n)
{
    if (n <= 1) return 1;
    return n * Factorial(n - 1);
}

• Base case

• Recursive case

• Stack overflow risk

1️⃣2️⃣ Two Pointers Pattern

int left = 0;
int right = arr.Length - 1;

while (left < right)
{
    if (arr[left] + arr[right] == target)
        return true;

    left++;
    right--;
}

• Sorted array problems

• Palindromes

1️⃣3️⃣ Sliding Window

int left = 0;
int sum = 0;

for (int right = 0; right < arr.Length; right++)
{
    sum += arr[right];

    while (sum > target)
    {
        sum -= arr[left];
        left++;
    }
}

• Subarray problems

• Longest substring

1️⃣4️⃣ BFS (Queue)

void BFS(Node root)
{
    var queue = new Queue<Node>();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        var node = queue.Dequeue();
        foreach (var child in node.Children)
            queue.Enqueue(child);
    }
}

1️⃣5️⃣ DFS (Stack or Recursion)

void DFS(Node node)
{
    if (node == null) return;

    foreach (var child in node.Children)
        DFS(child);
}

1️⃣6️⃣ Common String Operations

string s = "hello";

s.Length;
s.Substring(0, 2);
s.Contains("he");
s.IndexOf("e");

1️⃣7️⃣ LINQ Quick Recall

list.Where(x => x > 5);
list.Select(x => x * 2);
list.OrderBy(x => x);
list.GroupBy(x => x);
list.Any();
list.All();

1️⃣8️⃣ Common Interview Patterns

• Two Sum → Dictionary

• Detect duplicates → HashSet

• Reverse linked list → pointers

• Balanced parentheses → Stack

• BFS shortest path → Queue

• Binary search → sorted array

• Sliding window → subarray sum

1️⃣9️⃣ Memory Considerations

• List → dynamic array

• Dictionary → hash table

• String → immutable

• Stack overflow in recursion

• Avoid unnecessary allocations

2️⃣0️⃣ Quick Big-O Comparison

• when node reference known