{"title":"C# Crash Course for DSA","description":"","content":"This chapter is a focused crash course on C# features that come up repeatedly in DSA and coding interviews. Instead of covering the entire language, we will concentrate only on the parts that matter for solving problems efficiently in interviews.\n\n---\n\n# Common Using Directives\n\nOn LeetCode, most namespaces are imported automatically. But when writing C# locally or on some interview platforms, you need to know what to include. Here are the using directives that cover 95% of DSA problems:\n\n\n```csharp\nusing System; // Math, Array, String, Console\nusing System.Collections.Generic; // List, Dictionary, HashSet, Queue, Stack, PriorityQueue, etc.\nusing System.Linq; // Min(), Max(), Sum(), OrderBy(), GroupBy(), etc.\nusing System.Text; // StringBuilder\n```\n\n\nThe `System.Collections.Generic` namespace contains heavily used types. It contains every collection commonly used in DSA. `System.Linq` adds query methods that can make your code more concise, though you should use them judiciously in performance-sensitive code. We will cover LINQ in its own section later.\n\nIn a real interview, write these at the top and move on.\n\n---\n\n# Variables, Types, and the Overflow Trap\n\nC# is a statically typed language, which means every variable must have a declared type. For DSA, a small set of value types covers most problems.\n\n\n| Type | Size | Range | DSA Use Case |\n|------|------|-------|--------------|\n| `int` | 4 bytes | -2.1B to 2.1B | Array indices, counters, most values |\n| `long` | 8 bytes | -9.2 x 10^18 to 9.2 x 10^18 | Prefix sums, large products, overflow-prone math |\n| `char` | 2 bytes | 0 to 65,535 | String characters, frequency arrays |\n| `bool` | 1 byte | `true` / `false` | Visited arrays, flags |\n| `double` | 8 bytes | ±1.7 x 10^308 | Rarely used, some geometry problems |\n\n\nC# also has the `var` keyword for implicit typing. The compiler infers the type from the right-hand side:\n\n\n```csharp\nvar nums = new int[5]; // int[]\nvar map = new Dictionary(); // Dictionary\nvar result = new List>(); // List>\n```\n\n\nUse `var` when the type is obvious from the assignment. It reduces verbosity without sacrificing readability, especially with long generic types like `Dictionary>`.\n\nThe most dangerous pitfall with types is **integer overflow**. Consider the classic binary search:\n\n\n```csharp\n// BUG: if left + right > int.MaxValue, this overflows\nint mid = (left + right) / 2;\n\n// CORRECT: safe from overflow\nint mid = left + (right - left) / 2;\n```\n\n\nThis is not a theoretical concern. When `left` and `right` are both above 1 billion, their sum exceeds `int` range and wraps to a negative number. The safe version avoids this by computing the difference first.\n\nC# has a unique feature here: the `checked` keyword. In a `checked` block, arithmetic overflow throws an `OverflowException` instead of silently wrapping:\n\n\n```csharp\nchecked {\n int a = int.MaxValue;\n int b = a + 1; // Throws OverflowException at runtime\n}\n```\n\n\nBy default, C# arithmetic is `unchecked`, meaning it wraps silently on overflow. The `checked` keyword is useful for debugging but too slow for production DSA code. Know it exists, but rely on safe formulas instead.\n\nWhen should you use `long` instead of `int`? Use `long` in these cases:\n\n1. **Prefix sums** of arrays with large values (sum of 10^5 elements each up to 10^9 gives 10^14)\n2. **Multiplication** of two large ints (e.g., `n * (n - 1)` where n is near 10^5)\n3. **Factorial or combination** calculations\n4. **Modulo problems** where intermediate sums can exceed int range before taking mod\n\n\n```csharp\n// Overflow: 100000 * 99999 > int.MaxValue\nint wrong = n * (n - 1);\n\n// Safe: cast to long BEFORE multiplication\nlong correct = (long)n * (n - 1);\n\n// WRONG: casting AFTER multiplication is too late, overflow already happened\nlong stillWrong = (long)(n * (n - 1));\n```\n\n\nThe placement of the cast matters. `(long)n * (n - 1)` first promotes `n` to `long`, then performs `long` multiplication. But `(long)(n * (n - 1))` performs `int` multiplication first (which overflows), then casts the already-corrupted result to `long`.\n\n**The ternary operator** is a compact alternative to if-else for inline decisions:\n\n\n```csharp\nint result = (a > b) ? a : b; // Same as Math.Max(a, b)\nstring label = (count == 1) ? \"item\" : \"items\";\n```\n\n\n---\n\n# Operators and Control Flow\n\nMost operators in C# work as you would expect, but a few deserve special attention for DSA.\n\n**Modular arithmetic** with `%` appears in hashing, cyclic array problems, and math-heavy questions. Remember that C#'s `%` can return negative values for negative operands: `-7 % 3` gives `-1`, not `2`. To get a positive result, use `((n % m) + m) % m`.\n\nMany problems ask you to return the result \"modulo 10^9 + 7\" to prevent overflow in the output. This is a standard pattern:\n\n\n```csharp\nconst int MOD = 1_000_000_007;\n\n// Apply modulo during computation, not just at the end\nlong result = 0;\nfor (int i = 0; i < n; i++) {\n result = (result + values[i]) % MOD;\n}\nreturn (int)result;\n```\n\n\nNote the underscore in `1_000_000_007`. C# allows underscores in numeric literals for readability. This is the same as writing `1000000007`, easier to read and verify.\n\n**Bitwise operators** unlock an entire category of problems:\n\n\n```csharp\n// XOR trick: find the number that appears once (all others appear twice)\n// nums = [4, 1, 2, 1, 2]\nint single = 0;\nforeach (int num in nums) {\n single ^= num; // XOR cancels out duplicates\n}\n// single = 4\n```\n\n\nKey bitwise operators:\n\n\n| Operator | Symbol | DSA Use |\n|----------|--------|---------|\n| AND | `&` | Masking, checking if bit is set: `(n & (1 << i)) != 0` |\n| OR | `\\|` | Setting bits: `n \\| (1 << i)` |\n| XOR | `^` | Finding unique elements, toggling bits |\n| NOT | `~` | Bit inversion |\n| Left shift | `<<` | Multiply by powers of 2: `1 << n` equals 2^n |\n| Right shift | `>>` | Divide by powers of 2 (arithmetic shift, preserves sign) |\n| Unsigned right shift | `>>>` | Divide by powers of 2 (fills with 0, C# 11+) |\n\n\nA common bit manipulation pattern is checking and setting individual bits, which shows up in problems using bitmasks to represent subsets:\n\n\n```csharp\n// Check if bit i is set\nbool isSet = (mask & (1 << i)) != 0;\n\n// Set bit i\nmask = mask | (1 << i);\n\n// Clear bit i\nmask = mask & ~(1 << i);\n\n// Toggle bit i\nmask = mask ^ (1 << i);\n\n// Count number of set bits\nint count = BitOperations.PopCount((uint)mask); // System.Numerics\n// Or without the import:\nint count = Convert.ToString(mask, 2).Count(c => c == '1');\n```\n\n\nFor bit counting, `BitOperations.PopCount` from `System.Numerics` is the most concise approach. It maps to a single CPU instruction on modern hardware.\n\n**Control flow** in C# offers three loop forms. Use each where it fits:\n\n\n```csharp\n// Index-based for: when you need the index\nfor (int i = 0; i < nums.Length; i++) { ... }\n\n// Backward traversal (used in some DP and stack problems)\nfor (int i = n - 1; i >= 0; i--) { ... }\n\n// foreach: when you only need values\nforeach (int num in nums) { ... }\n\n// While: when the termination condition is not index-based\nwhile (left < right) { ... }\n```\n\n\nOne limitation to remember: the `foreach` loop does not give you the index, and you cannot modify the underlying collection while iterating. If you need the index or need to modify elements, use the standard `for` loop.\n\n**Short-circuit evaluation** with `&&` and `||` is important for safety. C# evaluates left to right and stops as soon as the result is determined:\n\n\n```csharp\n// Safe: the second condition is only checked if the first is true\nif (index < nums.Length && nums[index] == target) { ... }\n\n// Without short-circuit, this would throw IndexOutOfRangeException\n// when index >= nums.Length\n```\n\n\n---\n\n# Methods and Parameter Passing\n\nIn DSA problems, extracting logic into helper methods keeps the code clean. On LeetCode, your solution lives inside a class with instance or static methods.\n\n\n```csharp\n// Helper method for swapping elements in an array\nprivate void Swap(int[] arr, int i, int j) {\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n}\n```\n\n\nC# follows a convention of PascalCase for method names. Pick one style and stick with it.\n\nC# passes value types (like `int`, `bool`, `char`) **by value** and reference types (like arrays, lists, classes) **by reference value**. This means:\n\n- **Value type parameters** are copies. Changing them inside a method does not affect the caller.\n- **Reference type parameters** pass a copy of the reference. You can modify the contents (like `arr[i] = 5`), but reassigning the reference itself (`arr = new int[10]`) does not affect the caller.\n\nThis is why the `Swap` method above works: it modifies the array contents through the reference. But you cannot write a method that swaps two `int` variables without special keywords.\n\nC# gives you two tools for this: `ref` and `out` parameters.\n\n\n```csharp\n// ref: pass by reference (variable must be initialized before the call)\nprivate void SwapValues(ref int a, ref int b) {\n int temp = a;\n a = b;\n b = temp;\n}\n\nint x = 1, y = 2;\nSwapValues(ref x, ref y); // x is now 2, y is now 1\n```\n\n\n\n```csharp\n// out: like ref, but the variable does not need to be initialized before the call\n// The method MUST assign a value before returning\nprivate bool TryParse(string s, out int result) {\n // ... parsing logic ...\n result = 42;\n return true;\n}\n\nif (TryParse(\"42\", out int value)) {\n // value is 42\n}\n```\n\n\nThe `out` pattern is used extensively in C#'s standard library, most notably in `Dictionary.TryGetValue()` which we will see in the collections section.\n\nFor DSA specifically, the pass-by-reference behavior of lists matters in recursive and backtracking problems. When you pass a `List` to a recursive call and add elements to it, those additions are visible to the caller. That is why the backtracking pattern works, adding and removing from a shared list as you explore different branches:\n\n\n```csharp\nprivate void Backtrack(List path, List> results) {\n if (IsComplete(path)) {\n results.Add(new List(path)); // MUST copy, not add reference\n return;\n }\n foreach (int choice in choices) {\n path.Add(choice); // Modify shared list\n Backtrack(path, results); // Recurse with modified list\n path.RemoveAt(path.Count - 1); // Undo modification\n }\n}\n```\n\n\nThe `new List(path)` when saving results creates a copy. If you wrote `results.Add(path)` instead, every entry in `results` would be a reference to the same list, and they would all end up empty after backtracking unwinds. This is a common bug in backtracking solutions.\n\n**Variable scope** works the same as in most C-family languages. Variables declared inside a loop body exist only within that iteration:\n\n\n```csharp\nfor (int i = 0; i < n; i++) {\n int temp = nums[i]; // temp is created and destroyed each iteration\n}\n// temp does not exist here\n```\n\n\nIf you need a value to persist across iterations (like a running sum or a previous element), declare it before the loop.\n\n---\n\n# Arrays\n\nArrays are the foundational data structure in C# and the starting point for almost every DSA problem.\n\n\n```csharp\n// Declaration and initialization\nint[] nums = new int[5]; // [0, 0, 0, 0, 0] (defaults to 0)\nint[] nums = {1, 2, 3, 4, 5}; // Literal initialization\nbool[] visited = new bool[n]; // defaults to false\nstring[] words = new string[n]; // defaults to null\n```\n\n\nDefault values matter and they differ by type:\n\n\n| Array Type | Default Value | DSA Significance |\n|-----------|---------------|------------------|\n| `int[]` | `0` | Distance arrays, DP tables start at 0 |\n| `long[]` | `0L` | Same, for large value computations |\n| `bool[]` | `false` | Visited arrays start as unvisited |\n| `char[]` | `'\\0'` | Null character |\n| `string[]`, `object[]` | `null` | Must initialize before use |\n\n\n**The **`.Length`** property** (no parentheses) gives the array size. This is different from `List.Count` (also no parentheses) and `string.Length`. Getting these mixed up is a common mistake:\n\n\n```csharp\nint[] arr = {1, 2, 3};\narr.Length // 3 (property)\n\nstring s = \"hello\";\ns.Length // 5 (property)\n\nList list = new List();\nlist.Count // 0 (property)\n```\n\n\nAll three are properties (no parentheses). But the naming differs: arrays and strings use `Length`, while collections use `Count`.\n\n**2D arrays** in C# come in two flavors:\n\n\n```csharp\n// Rectangular array (true 2D, single memory block)\nint[,] matrix = new int[3, 4];\nmatrix[0, 0] = 1;\nint rows = matrix.GetLength(0); // 3\nint cols = matrix.GetLength(1); // 4\n\n// Jagged array (array of arrays)\nint[][] jagged = new int[3][];\nfor (int i = 0; i < 3; i++) {\n jagged[i] = new int[4];\n}\njagged[0][0] = 1;\nint rows = jagged.Length; // 3\nint cols = jagged[0].Length; // 4\n```\n\n\nFor DSA problems, **jagged arrays (**`int[][]`**) are almost always the right choice**. LeetCode uses them for all matrix inputs, `Array.Sort()` works on them directly, and the syntax matches what you see in problem descriptions. Rectangular arrays (`int[,]`) are mostly useful when you need a single contiguous memory block for performance.\n\nFor DP problems, you often need a table with one extra row and column for the base case:\n\n\n```csharp\n// DP table with n+1 rows to handle 0-indexed base case\nint[] dp = new int[n + 1];\nint[][] dp = new int[m + 1][];\nfor (int i = 0; i <= m; i++) dp[i] = new int[n + 1];\n```\n\n\nThe 4-directional neighbor pattern is common in matrix problems:\n\n\n```csharp\nint[][] directions = { new[]{-1, 0}, new[]{1, 0}, new[]{0, -1}, new[]{0, 1} };\n\nforeach (int[] dir in directions) {\n int newRow = row + dir[0];\n int newCol = col + dir[1];\n if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {\n // Process neighbor\n }\n}\n```\n\n\nFor 8-directional movement (including diagonals), add the four diagonal pairs: `{-1,-1}, {-1,1}, {1,-1}, {1,1}`.\n\n\n```mermaid\nflowchart TD\n subgraph Matrix[\"matrix[3][3]\"]\n direction TB\n R0[\"[0,0] [0,1] [0,2]\"]\n R1[\"[1,0] [1,1] [1,2]\"]\n R2[\"[2,0] [2,1] [2,2]\"]\n end\n\n UP[\"Up
[-1, 0]\"]\n DOWN[\"Down
[+1, 0]\"]\n LEFT[\"Left
[0, -1]\"]\n RIGHT[\"Right
[0, +1]\"]\n\n UP --> R1\n DOWN --> R1\n LEFT --> R1\n RIGHT --> R1\n\n style R0 fill:#00ceff,stroke:#000,color:#000\n style R1 fill:#ffa94d,stroke:#000,color:#000\n style R2 fill:#00ceff,stroke:#000,color:#000\n style UP fill:#69db7c,stroke:#000,color:#000\n style DOWN fill:#69db7c,stroke:#000,color:#000\n style LEFT fill:#69db7c,stroke:#000,color:#000\n style RIGHT fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe `Array` class provides static operations:\n\n\n```csharp\nArray.Sort(nums); // Sort in ascending order\nArray.Fill(dist, int.MaxValue); // Fill with a value\nArray.Copy(nums, copy, nums.Length); // Copy to another array\nArray.Reverse(nums); // Reverse in place\nint[] copy = (int[])nums.Clone(); // Shallow copy\n```\n\n\n`Array.Sort()`** with a range** lets you sort a portion of an array:\n\n\n```csharp\nArray.Sort(nums, 1, 3); // Sort 3 elements starting at index 1\n```\n\n\n`Array.BinarySearch()` performs binary search on a sorted array:\n\n\n```csharp\nint[] sorted = {1, 3, 5, 7, 9};\nint index = Array.BinarySearch(sorted, 5); // Returns 2\nint missing = Array.BinarySearch(sorted, 4); // Returns -3 (bitwise complement of insertion point)\n```\n\n\nThe return value for a missing element is the bitwise complement (`~`) of the index where it would be inserted. So `~missing` gives you the insertion point. This is useful but confusing, so writing your own binary search is often clearer.\n\n`Array.Sort()` uses IntroSort for primitive types (a hybrid of Quicksort, Heapsort, and Insertion Sort) which guarantees O(n log n) worst case.\n\n---\n\n# Strings\n\nStrings in C# are **immutable**. Every time you modify a string, C# creates a new object. This has a performance implication for DSA:\n\n\n```csharp\n// BAD: O(n^2) because each += creates a new string\nstring result = \"\";\nforeach (char c in chars) {\n result += c; // Creates a new string every iteration\n}\n\n// GOOD: O(n) with StringBuilder\nvar sb = new StringBuilder();\nforeach (char c in chars) {\n sb.Append(c);\n}\nstring result = sb.ToString();\n```\n\n\n**C# string comparison with **`==`** compares content, not references:**\n\n\n```csharp\nstring a = \"hello\";\nstring b = string.Concat(\"hel\", \"lo\"); // distinct instance (avoids interning)\n\na == b // true (C# overloads == to compare content)\na.Equals(b) // also true\nReferenceEquals(a, b) // false (they are different objects)\n```\n\n\nBoth `==` and `.Equals()` work for content comparison.\n\nCommon string methods:\n\n\n| Method | Returns | Example | DSA Use |\n|--------|---------|---------|---------|\n| `s[i]` | `char` | `s[0]` | Access individual characters (indexer, not a method) |\n| `Length` | `int` | `s.Length` | Loop bounds (property, no parentheses) |\n| `Substring(start, len)` | `string` | `s.Substring(0, 3)` | Extract portions (start index, length, not end index!) |\n| `ToCharArray()` | `char[]` | `s.ToCharArray()` | When you need in-place modification |\n| `Split(sep)` | `string[]` | `s.Split(' ')` | Tokenize strings |\n| `IndexOf(str)` | `int` | `s.IndexOf(\"ab\")` | Find substrings (-1 if not found) |\n| `Equals(other)` | `bool` | `s.Equals(t)` | Content comparison (same as ==) |\n| `CompareTo(other)` | `int` | `s.CompareTo(t)` | Lexicographic comparison |\n| `Trim()` | `string` | `s.Trim()` | Remove leading/trailing whitespace |\n| `string.IsNullOrEmpty(s)` | `bool` | | Check for null or empty |\n| `StartsWith(prefix)` | `bool` | `s.StartsWith(\"ab\")` | Prefix check |\n| `Contains(seq)` | `bool` | `s.Contains(\"ab\")` | Substring check |\n\n\n**Watch out:** C#'s `Substring(startIndex, length)` takes a **length**, not an end index. Getting this wrong is a common bug:\n\n\n```csharp\nstring s = \"hello world\";\ns.Substring(0, 5) // \"hello\" (start at 0, take 5 characters)\ns.Substring(6, 5) // \"world\" (start at 6, take 5 characters)\n```\n\n\nC# also supports range syntax with `..` (C# 8+) for slicing:\n\n\n```csharp\nstring s = \"hello world\";\ns[0..5] // \"hello\"\ns[6..] // \"world\"\ns[^5..] // \"world\" (^5 means 5 from the end)\n```\n\n\n**StringBuilder** is your tool for building strings efficiently:\n\n\n```csharp\nvar sb = new StringBuilder();\nsb.Append(\"hello\"); // Add to end\nsb.Append(' '); // Append char\nsb.Insert(0, \"say \"); // Insert at position\nsb.Remove(0, 4); // Remove 4 chars starting at index 0\nsb.Replace('l', 'r'); // Replace all occurrences of a char\nsb[2] = 'x'; // Direct character access via indexer\nsb.Length; // Current length\nstring result = sb.ToString(); // Convert back to string\n```\n\n\n`StringBuilder` supports direct indexing with `sb[i]` for both reading and writing characters.\n\n**Character utilities** come up in problems involving letter manipulation:\n\n\n```csharp\nchar.IsLetterOrDigit(c) // Alphanumeric check (valid palindrome)\nchar.IsLetter(c) // Letter only\nchar.IsDigit(c) // Digit only\nchar.IsUpper(c) // Uppercase check\nchar.ToLower(c) // Case conversion\nchar.ToUpper(c) // Case conversion\nc - 'a' // Map 'a'-'z' to 0-25 (frequency arrays)\nc - '0' // Map '0'-'9' to 0-9 (digit extraction)\n(char)('a' + index) // Map 0-25 back to 'a'-'z'\n```\n\n\nThe `c - 'a'` pattern works because characters are stored as numbers. Subtracting `'a'` from a lowercase letter gives its zero-based position. This is how you build frequency arrays without a `Dictionary`:\n\n\n```csharp\n// Frequency array for lowercase letters (26 slots)\nint[] freq = new int[26];\nforeach (char c in s) {\n freq[c - 'a']++;\n}\n// freq[0] = count of 'a', freq[1] = count of 'b', etc.\n```\n\n\nThis is faster and more memory-efficient than `Dictionary` when you know the character set is limited to lowercase (or uppercase, or digits).\n\n---\n\n# Collections Framework\n\nThe `System.Collections.Generic` namespace provides the data structures used in nearly every DSA problem. Choosing the right collection is often the difference between an O(n) and an O(n^2) solution.\n\n\n```mermaid\nflowchart TD\n IE[\"IEnumerable<T>\"]\n IC[\"ICollection<T>\"]\n IL[\"IList<T>\"]\n IS[\"ISet<T>\"]\n ID[\"IDictionary<K,V>
(separate hierarchy)\"]\n\n LST[\"List<T>\"]\n HS[\"HashSet<T>\"]\n SS[\"SortedSet<T>\"]\n QUE[\"Queue<T>\"]\n STK[\"Stack<T>\"]\n LL[\"LinkedList<T>\"]\n DIC[\"Dictionary<K,V>\"]\n SD[\"SortedDictionary<K,V>\"]\n PQ[\"PriorityQueue<E,P>\"]\n\n IE --> IC\n IC --> IL\n IC --> IS\n IL --> LST\n IS --> HS\n IS --> SS\n IE --> QUE\n IE --> STK\n IC --> LL\n ID --> DIC\n ID --> SD\n IE --> PQ\n\n style IE fill:#00ceff,stroke:#000,color:#000\n style IC fill:#00ceff,stroke:#000,color:#000\n style IL fill:#00ceff,stroke:#000,color:#000\n style IS fill:#00ceff,stroke:#000,color:#000\n style ID fill:#00ceff,stroke:#000,color:#000\n style LST fill:#38d9a9,stroke:#000,color:#000\n style HS fill:#38d9a9,stroke:#000,color:#000\n style SS fill:#38d9a9,stroke:#000,color:#000\n style QUE fill:#38d9a9,stroke:#000,color:#000\n style STK fill:#38d9a9,stroke:#000,color:#000\n style LL fill:#38d9a9,stroke:#000,color:#000\n style DIC fill:#ffa94d,stroke:#000,color:#000\n style SD fill:#ffa94d,stroke:#000,color:#000\n style PQ fill:#38d9a9,stroke:#000,color:#000\n```\n\n\n### List\\: Dynamic Arrays\n\nWhen you do not know the size upfront, or need to build a result list, `List` is your go-to:\n\n\n```csharp\nList result = new List();\nresult.Add(42); // Append: O(1) amortized\nresult[0]; // Access by index: O(1)\nresult[0] = 99; // Update by index: O(1)\nresult.Count; // Current size\nresult.Contains(42); // Search: O(n)\nresult.RemoveAt(0); // Remove by index: O(n) (shifts elements)\nresult.Remove(42); // Remove first occurrence of value: O(n)\nresult.Insert(0, 10); // Insert at index: O(n) (shifts elements)\nresult.IndexOf(42); // Find index of value: O(n), returns -1 if not found\n```\n\n\n`RemoveAt` removes by index, `Remove` removes by value. The naming is clear: there is no ambiguity between the two.\n\nA common pattern is building a list of lists for results like permutations or combinations:\n\n\n```csharp\nList> results = new List>();\nresults.Add(new List(currentPath)); // Add a COPY of current state\n```\n\n\n**Useful List methods:**\n\n\n```csharp\nlist.Sort(); // Sort ascending in place\nlist.Reverse(); // Reverse in place\nlist.ToArray(); // Convert to array\nlist.AddRange(otherList); // Append all elements from another collection\nlist.RemoveAll(x => x % 2 == 0); // Remove all even numbers (predicate)\nlist.BinarySearch(target); // Binary search (list must be sorted)\n```\n\n\n### Dictionary\\: O(1) Lookups\n\n`Dictionary` appears in most DSA problems. It provides O(1) average-case lookups, inserts, and deletes.\n\n\n```csharp\n// Frequency counting: the most common Dictionary pattern\nvar freq = new Dictionary();\nforeach (char c in s) {\n if (freq.ContainsKey(c))\n freq[c]++;\n else\n freq[c] = 1;\n}\n\n// Shorter with TryGetValue\nforeach (char c in s) {\n freq.TryGetValue(c, out int count);\n freq[c] = count + 1;\n}\n```\n\n\nThe `TryGetValue` pattern is a C# idiom you should know well. It attempts to get the value and returns `false` if the key does not exist, without throwing an exception. When the key is missing, the `out` variable gets the default value for the type (`0` for `int`, `null` for reference types):\n\n\n```csharp\nvar map = new Dictionary();\n\n// DANGEROUS: throws KeyNotFoundException if key is missing\nint val = map[\"missing\"]; // Throws!\n\n// SAFE: TryGetValue returns false if key is missing\nif (map.TryGetValue(\"missing\", out int value)) {\n // key exists, value is set\n} else {\n // key does not exist, value is 0 (default for int)\n}\n\n// Also safe: ContainsKey check first\nif (map.ContainsKey(\"key\")) {\n int val = map[\"key\"];\n}\n```\n\n\nIterating over a dictionary:\n\n\n```csharp\n// Iterate over all entries (KeyValuePair)\nforeach (var kvp in freq) {\n char key = kvp.Key;\n int value = kvp.Value;\n}\n\n// Deconstruct into key and value (C# 7+)\nforeach (var (key, value) in freq) {\n // use key and value directly\n}\n\n// Iterate over keys only\nforeach (char key in freq.Keys) { ... }\n\n// Iterate over values only\nforeach (int value in freq.Values) { ... }\n```\n\n\nThe deconstruction syntax `var (key, value)` is more concise than `kvp.Key` and `kvp.Value`. Use it when you need both.\n\n### HashSet\\: O(1) Membership Testing\n\n\n```csharp\nvar visited = new HashSet();\nvisited.Add(node); // Returns true if newly added, false if already present\nvisited.Contains(node); // O(1) lookup\nvisited.Remove(node); // O(1) removal\nvisited.Count; // Number of elements\n```\n\n\n`Add()` returns a boolean telling you whether the element was newly added (i.e., was not already present). This lets you detect duplicates in a single operation:\n\n\n```csharp\nvar seen = new HashSet();\nforeach (int num in nums) {\n if (!seen.Add(num)) {\n // num is a duplicate\n }\n}\n```\n\n\n`HashSet` also supports set operations:\n\n\n```csharp\nvar setA = new HashSet {1, 2, 3, 4};\nvar setB = new HashSet {3, 4, 5, 6};\n\nsetA.IntersectWith(setB); // setA = {3, 4}\nsetA.UnionWith(setB); // setA = {1, 2, 3, 4, 5, 6}\nsetA.ExceptWith(setB); // setA = {1, 2} (elements in A but not in B)\nsetA.IsSubsetOf(setB); // bool\nsetA.Overlaps(setB); // true if any element in common\n```\n\n\n### SortedDictionary and SortedSet: Sorted Collections\n\nWhen you need keys in sorted order, `SortedDictionary` and `SortedSet` provide O(log n) operations backed by a red-black tree.\n\n\n```csharp\nvar map = new SortedDictionary();\nmap[5] = 10;\nmap[1] = 20;\nmap[10] = 30;\n\n// Iterate in sorted order of keys\nforeach (var kvp in map) {\n // Keys come out as 1, 5, 10\n}\n\n// First and last keys\nint firstKey = map.Keys.First(); // 1 (requires System.Linq)\nint lastKey = map.Keys.Last(); // 10\n```\n\n\nHowever, `SortedDictionary` lacks direct floor/ceiling/lower/higher key navigation methods. For these operations, use `SortedSet` which has `GetViewBetween()`, or consider a different approach.\n\n`SortedSet` provides richer navigation:\n\n\n```csharp\nvar set = new SortedSet {1, 3, 5, 7, 9};\n\nset.Min; // 1 (smallest element)\nset.Max; // 9 (largest element)\nset.GetViewBetween(3, 7); // {3, 5, 7} (inclusive range)\nset.Count; // 5\n```\n\n\nFor true floor/ceiling operations, you can use LINQ or write helper methods:\n\n\n```csharp\nvar set = new SortedSet {1, 3, 5, 7, 9};\n\n// Floor: largest element <= target\n// Ceiling: smallest element >= target\nint? floor = set.GetViewBetween(set.Min, 6).Max; // 5\nint? ceiling = set.GetViewBetween(6, set.Max).Min; // 7\n```\n\n\n### Queue\\: BFS Foundation\n\nEvery BFS implementation starts with a queue:\n\n\n```csharp\nvar queue = new Queue();\nqueue.Enqueue(new int[]{startRow, startCol}); // Enqueue\nwhile (queue.Count > 0) {\n int size = queue.Count; // Capture size for level-order traversal\n for (int i = 0; i < size; i++) {\n int[] cell = queue.Dequeue(); // Dequeue\n // Process cell, add neighbors\n queue.Enqueue(new int[]{newRow, newCol});\n }\n}\n```\n\n\nC# uses `Enqueue` and `Dequeue` for queue operations. The methods throw `InvalidOperationException` if you try to dequeue from an empty queue, so always check `queue.Count > 0` first. Use `queue.Peek()` to view the front element without removing it.\n\nThe `queue.Count` capture before the inner loop is a common pattern for level-order BFS, where you need to process all nodes at the current level before moving to the next.\n\n### Stack\\: LIFO Operations\n\nC#'s `Stack` is the standard LIFO collection:\n\n\n```csharp\nvar stack = new Stack();\nstack.Push(42); // Push to top\nstack.Pop(); // Remove and return top (throws if empty)\nstack.Peek(); // View top without removing (throws if empty)\nstack.Count; // Number of elements\nstack.Contains(42); // O(n) search\n```\n\n\nAlways check `stack.Count > 0` before calling `Pop()` or `Peek()` to avoid exceptions.\n\n### LinkedList\\: Double-Ended Operations\n\n`LinkedList` in C# is a doubly-linked list that supports efficient operations at both ends, making it useful as a deque:\n\n\n```csharp\nvar deque = new LinkedList();\ndeque.AddFirst(1); // Add to front: O(1)\ndeque.AddLast(2); // Add to back: O(1)\ndeque.RemoveFirst(); // Remove from front: O(1)\ndeque.RemoveLast(); // Remove from back: O(1)\ndeque.First.Value; // View front\ndeque.Last.Value; // View back\ndeque.Count; // Number of elements\n```\n\n\nThis is useful for sliding window maximum and monotonic deque problems where you need to add/remove from both ends.\n\n### PriorityQueue\\: Heaps\n\n`PriorityQueue` was added in .NET 6 and separates the element from its priority. You enqueue both, and the queue dequeues the element with the smallest priority first.\n\n\n```csharp\n// Min-heap (default): smallest priority comes out first\nvar minHeap = new PriorityQueue();\nminHeap.Enqueue(42, 42); // Enqueue element with priority\nminHeap.Dequeue(); // Remove and return element with smallest priority\nminHeap.Peek(); // View element with smallest priority\nminHeap.Count; // Number of elements\n\n// For DSA, element and priority are often the same value\nminHeap.Enqueue(value, value);\n```\n\n\n**Making a max-heap** requires extra work because there is no built-in reverse comparator. You have three options:\n\n\n```csharp\n// Option 1: Negate the priority (works for numeric types)\nvar maxHeap = new PriorityQueue();\nmaxHeap.Enqueue(42, -42); // Negate priority to flip ordering\n\n// Option 2: Custom comparer\nvar maxHeap = new PriorityQueue(Comparer.Create((a, b) => b.CompareTo(a)));\nmaxHeap.Enqueue(42, 42); // Now largest priority comes out first\n\n// Option 3: For complex objects, negate in the priority parameter\n// Dijkstra example: process closest nodes first\nvar pq = new PriorityQueue(); // (node, distance)\npq.Enqueue(startNode, 0);\n```\n\n\nFor most DSA problems, Option 1 (negating the priority) is the simplest and fastest approach. Option 2 reads more clearly when you want explicit ordering.\n\nC#'s `PriorityQueue` does not support decreasing an element's priority (there is no decrease-key operation) or removing arbitrary elements efficiently. It does have an `EnqueueDequeue` method that is useful for maintaining a fixed-size heap (like top-K problems). For problems that need priority updates (like Dijkstra), re-enqueue the node with its new priority and skip stale entries when dequeuing by checking whether the node was already finalized.\n\n### Collections Quick Reference\n\n\n| Collection | C# Type | Key Methods | Time Complexity | DSA Use Case |\n|------------|---------|-------------|-----------------|--------------|\n| Dynamic Array | `List` | `Add`, `[]`, `RemoveAt`, `Count` | O(1) get, O(1) add | Result lists, dynamic arrays |\n| Hash Map | `Dictionary` | `[]`, `TryGetValue`, `ContainsKey` | O(1) average | Frequency counting, lookups |\n| Hash Set | `HashSet` | `Add`, `Contains`, `Remove` | O(1) average | Visited tracking, duplicates |\n| Sorted Map | `SortedDictionary` | `[]`, `Keys`, `ContainsKey` | O(log n) | Sorted access, range queries |\n| Sorted Set | `SortedSet` | `Add`, `Min`, `Max`, `GetViewBetween` | O(log n) | Sorted unique elements |\n| Queue | `Queue` | `Enqueue`, `Dequeue`, `Peek` | O(1) | BFS queues |\n| Stack | `Stack` | `Push`, `Pop`, `Peek` | O(1) | DFS, monotonic stack |\n| Linked List | `LinkedList` | `AddFirst`, `AddLast`, `RemoveFirst` | O(1) ends | Deque, sliding window |\n| Heap | `PriorityQueue` | `Enqueue`, `Dequeue`, `Peek` | O(log n) enq/deq | Top-K, Dijkstra |\n\n\n---\n\n# Sorting and Comparators\n\nSorting is a prerequisite for many algorithms: binary search, two pointers on sorted arrays, merge intervals, and greedy approaches.\n\n\n```csharp\n// Sort primitive array\nint[] nums = {3, 1, 4, 1, 5};\nArray.Sort(nums); // [1, 1, 3, 4, 5]\n\n// Sort a portion of an array (start index 1, count 3)\nArray.Sort(nums, 1, 3);\n\n// Sort a list\nvar list = new List {3, 1, 4};\nlist.Sort();\n```\n\n\nFor custom sorting, C# uses `Comparison` delegates. The delegate receives two elements and returns a negative number if the first should come before the second, zero if they are equal, and a positive number if the first should come after:\n\n\n```csharp\n// Sort intervals by start time (merge intervals pattern)\nint[][] intervals = new int[][] { new[]{1,3}, new[]{2,6}, new[]{8,10} };\nArray.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));\n\n// Sort strings by length, then alphabetically for ties\nArray.Sort(words, (a, b) => {\n if (a.Length != b.Length) return a.Length.CompareTo(b.Length);\n return a.CompareTo(b);\n});\n\n// Sort a List with a lambda\nlist.Sort((a, b) => a.CompareTo(b));\n```\n\n\nFor descending order:\n\n\n```csharp\n// Sort array in descending order (two steps for primitive arrays)\nArray.Sort(nums);\nArray.Reverse(nums);\n\n// Sort list descending with comparator\nlist.Sort((a, b) => b.CompareTo(a)); // Note: b.CompareTo(a), not a.CompareTo(b)\n\n// For object arrays, use a reverse comparer\nstring[] words = {\"banana\", \"apple\", \"cherry\"};\nArray.Sort(words, Comparer.Create((a, b) => b.CompareTo(a)));\n```\n\n\nThe pattern for descending order is either sort-then-reverse for arrays, or flip the comparison in the lambda.\n\n---\n\n# LINQ Essentials for DSA\n\nLINQ (Language Integrated Query) is a C#-specific feature that adds query operations to collections. It can make certain DSA patterns significantly more concise, but you need to know when it helps and when it hurts.\n\n**Useful LINQ methods for DSA:**\n\n\n```csharp\nusing System.Linq;\n\nint[] nums = {3, 1, 4, 1, 5, 9, 2, 6};\n\n// Aggregation\nnums.Min() // 1\nnums.Max() // 9\nnums.Sum() // 31\nnums.Average() // 3.875\n\n// Filtering and transformation\nnums.Where(x => x > 3) // {4, 5, 9, 6} (lazy, returns IEnumerable)\nnums.Select(x => x * 2) // {6, 2, 8, 2, 10, 18, 4, 12}\nnums.Distinct() // {3, 1, 4, 5, 9, 2, 6}\n\n// Sorting\nnums.OrderBy(x => x) // ascending\nnums.OrderByDescending(x => x) // descending\nnums.OrderBy(x => x % 2).ThenBy(x => x) // evens first, then odds, each ascending\n\n// Conversion\nnums.ToList() // Convert to List\nnums.ToArray() // Convert to int[]\nnums.ToHashSet() // Convert to HashSet\n\n// Grouping (useful for anagram grouping problems)\nstring[] words = {\"eat\", \"tea\", \"tan\", \"ate\", \"nat\", \"bat\"};\nvar groups = words.GroupBy(w => new string(w.OrderBy(c => c).ToArray()));\n// Groups: \"aet\" -> [\"eat\", \"tea\", \"ate\"], \"ant\" -> [\"tan\", \"nat\"], \"abt\" -> [\"bat\"]\n\n// Zip (combine two sequences element-by-element)\nint[] a = {1, 2, 3};\nint[] b = {4, 5, 6};\nvar zipped = a.Zip(b, (x, y) => x + y); // {5, 7, 9}\n```\n\n\n**When to use LINQ in DSA:**\n\n- Quick one-liners for min/max/sum when you do not need the loop for anything else\n- `GroupBy` for grouping problems (anagrams, categorization)\n- `OrderBy` when you need a sorted copy without modifying the original\n- `Distinct` for removing duplicates\n- `ToHashSet()` for converting a list to a set\n\n**When to avoid LINQ in DSA:**\n\n- Inside nested loops or hot paths (LINQ has overhead from delegate invocations and iterator objects)\n- When you need early termination (a `for` loop with `break` is more efficient than `Where().First()`)\n- When the manual approach is just as readable\n\n\n```csharp\n// LINQ: clean but allocates an iterator\nint maxVal = nums.Max();\n\n// Manual: slightly more verbose but zero allocation\nint maxVal = int.MinValue;\nforeach (int num in nums) {\n maxVal = Math.Max(maxVal, num);\n}\n```\n\n\nFor most interview problems, the performance difference is negligible. Use LINQ when it makes your code shorter, but be prepared to explain the trade-off if asked.\n\n---\n\n# Null Handling\n\n`null` is a source of many runtime errors in C#. In DSA, you encounter it primarily in three situations: tree/linked list problems, dictionary lookups, and uninitialized reference type arrays.\n\n**Rule 1: Always check for null before accessing fields or calling methods on an object.**\n\n\n```csharp\n// Tree traversal: always check for null children\nif (node.Left != null) {\n queue.Enqueue(node.Left);\n}\n\n// Linked list: check before advancing\nwhile (current != null) {\n // process current\n current = current.Next;\n}\n```\n\n\n**Rule 2: Use **`TryGetValue`** instead of the indexer for dictionaries.**\n\n\n```csharp\n// Dangerous: throws KeyNotFoundException if key missing\nint count = map[\"key\"];\n\n// Safe: returns false if key missing, value gets default(int) = 0\nmap.TryGetValue(\"key\", out int count);\n```\n\n\n**Rule 3: Use C#'s null-safety operators.**\n\nC# provides null-handling operators that simplify common patterns:\n\n\n```csharp\n// Null-conditional operator (?.)\n// Returns null if the left side is null, instead of throwing\nint? length = node?.Left?.Right?.Val;\n\n// Null-coalescing operator (??)\n// Returns the left side if not null, otherwise the right side\nstring name = input ?? \"default\";\n// ?? only works with nullable types. For int values, see TryGetValue above\n\n// Null-coalescing assignment (??=)\n// Assigns only if the left side is null\nnode.Left ??= new TreeNode(0);\n```\n\n\n**Rule 4: Combine null and empty checks.**\n\n\n```csharp\nif (nums == null || nums.Length == 0) return new int[0];\nif (string.IsNullOrEmpty(s)) return \"\";\n```\n\n\nThese checks at the top of your solution handle edge cases cleanly. They short-circuit on empty or null input so the rest of the method can assume valid data. `string.IsNullOrEmpty()` is a C# convenience that checks both conditions in one call.\n\n**Nullable value types** use `?` syntax:\n\n\n```csharp\nint? result = null; // Nullable int\nif (result.HasValue) {\n int actual = result.Value;\n}\nint actual = result ?? -1; // Use -1 if null\n```\n\n\nThis is useful when you need to distinguish between \"no value\" and \"zero\" (e.g., a function that returns the index of a found element, or null if not found).\n\n---\n\n# Iterating and Modifying Collections Safely\n\nOne of C#'s most common runtime errors is `InvalidOperationException` with the message \"Collection was modified; enumeration operation may not execute.\" This is thrown when you modify a collection while iterating over it with a `foreach` loop:\n\n\n```csharp\n// WRONG: throws InvalidOperationException\nvar list = new List {1, 2, 3, 4, 5};\nforeach (int num in list) {\n if (num % 2 == 0) {\n list.Remove(num);\n }\n}\n```\n\n\nThere are three safe alternatives:\n\n\n```csharp\n// Option 1: Iterate backward with index-based loop\nfor (int i = list.Count - 1; i >= 0; i--) {\n if (list[i] % 2 == 0) {\n list.RemoveAt(i);\n }\n}\n\n// Option 2: Collect items to remove, then remove after the loop\nvar toRemove = new List();\nforeach (int num in list) {\n if (num % 2 == 0) toRemove.Add(num);\n}\nforeach (int num in toRemove) list.Remove(num);\n\n// Option 3: Use RemoveAll with a predicate (most concise for List)\nlist.RemoveAll(num => num % 2 == 0);\n```\n\n\nOption 3 is idiomatic for `List`. It is a single line, efficient (O(n)), and reads clearly.\n\nFor `HashSet` and `Dictionary`, the same rules apply. If you need to remove entries while iterating, collect the keys first, then remove:\n\n\n```csharp\nvar keysToRemove = new List();\nforeach (var kvp in dictionary) {\n if (ShouldRemove(kvp.Value)) keysToRemove.Add(kvp.Key);\n}\nforeach (string key in keysToRemove) dictionary.Remove(key);\n```\n\n\nIn practice though, most DSA problems do not require removing during iteration. You are far more likely to build a new collection with the desired elements.\n\n---\n\n# Recursion and the Call Stack\n\nRecursion underlies tree traversal, graph DFS, backtracking, and divide-and-conquer. It helps to know how C# handles it.\n\nEvery method call in C# goes on the **call stack**, which has limited space (typically 1 MB by default on Windows, which translates to a few thousand frames depending on frame size). If your recursion goes too deep, you get a `StackOverflowException`:\n\n\n```csharp\n// This will crash for large n (the exact limit depends on stack\n// size and frame size, often around 10,000 to 50,000)\nint Factorial(int n) {\n if (n <= 1) return 1;\n return n * Factorial(n - 1);\n}\n```\n\n\n**When to worry about stack depth:**\n\n\n| Scenario | Typical Depth | Risk |\n|----------|--------------|------|\n| Balanced binary tree (n nodes) | O(log n) | Safe for n up to 10^6 |\n| Linked list / skewed tree (n nodes) | O(n) | Dangerous if n > 5,000-10,000 |\n| Backtracking (k choices, depth d) | O(d) | Usually safe (d is small) |\n| DFS on graph (n nodes) | O(n) | Dangerous for large n |\n\n\n**The fix:** Convert deep recursion to an iterative approach using an explicit stack:\n\n\n```csharp\n// Recursive DFS (risks stack overflow for deep graphs)\nvoid Dfs(int node, bool[] visited) {\n visited[node] = true;\n foreach (int neighbor in graph[node]) {\n if (!visited[neighbor]) Dfs(neighbor, visited);\n }\n}\n\n// Iterative DFS (safe for any depth)\nvoid Dfs(int start, bool[] visited) {\n var stack = new Stack();\n stack.Push(start);\n while (stack.Count > 0) {\n int node = stack.Pop();\n if (visited[node]) continue;\n visited[node] = true;\n foreach (int neighbor in graph[node]) {\n if (!visited[neighbor]) stack.Push(neighbor);\n }\n }\n}\n```\n\n\nNote that C# does **not** optimize tail recursion in the standard runtime (though the JIT compiler can sometimes do it in specific cases). If your recursion depth is proportional to input size and the input can be large, convert to iteration.\n\n---\n\n# Graph Representation Patterns\n\nGraphs appear in a large portion of DSA problems. C# does not have a built-in graph class, so you need to build representations yourself. There are two common approaches:\n\n**Approach 1: Adjacency list with **`List>`**.** Use this when nodes are numbered 0 to n-1.\n\n\n```csharp\nint n = 5; // number of nodes\nvar graph = new List>();\nfor (int i = 0; i < n; i++) {\n graph.Add(new List());\n}\n\n// Add edges\nforeach (int[] edge in edges) {\n graph[edge[0]].Add(edge[1]);\n graph[edge[1]].Add(edge[0]); // Omit for directed graphs\n}\n\n// Access neighbors\nforeach (int neighbor in graph[node]) { ... }\n```\n\n\n**Approach 2: Adjacency list with **`Dictionary>`**.** Use this when node IDs are not contiguous or are very large.\n\n\n```csharp\nvar graph = new Dictionary>();\nforeach (int[] edge in edges) {\n if (!graph.ContainsKey(edge[0])) graph[edge[0]] = new List();\n if (!graph.ContainsKey(edge[1])) graph[edge[1]] = new List();\n graph[edge[0]].Add(edge[1]);\n graph[edge[1]].Add(edge[0]);\n}\n\n// Access neighbors (with safety check)\nif (graph.TryGetValue(node, out var neighbors)) {\n foreach (int neighbor in neighbors) { ... }\n}\n```\n\n\nA shorter version using `TryGetValue` for building:\n\n\n```csharp\nforeach (int[] edge in edges) {\n if (!graph.TryGetValue(edge[0], out var list0)) {\n list0 = new List();\n graph[edge[0]] = list0;\n }\n list0.Add(edge[1]);\n}\n```\n\n\n**Weighted graphs** use tuples or `int[]` to store neighbor and weight:\n\n\n```csharp\n// Adjacency list for weighted graph using tuples\nvar graph = new List>();\nfor (int i = 0; i < n; i++) graph.Add(new List<(int, int)>());\n\ngraph[from].Add((to, weight));\n\n// Used in Dijkstra:\nvar pq = new PriorityQueue(); // (node, distance as priority)\npq.Enqueue(startNode, 0);\n```\n\n\n\n```mermaid\nflowchart LR\n subgraph AdjList[\"Adjacency List (List of Lists)\"]\n N0[\"Node 0\"] --> L0[\"[1, 2]\"]\n N1[\"Node 1\"] --> L1[\"[0, 3]\"]\n N2[\"Node 2\"] --> L2[\"[0, 3]\"]\n N3[\"Node 3\"] --> L3[\"[1, 2]\"]\n end\n\n subgraph AdjMap[\"Adjacency Map (Dictionary)\"]\n K0[\"Key: 0\"] --> V0[\"[1, 2]\"]\n K1[\"Key: 1\"] --> V1[\"[0, 3]\"]\n K2[\"Key: 2\"] --> V2[\"[0, 3]\"]\n K3[\"Key: 3\"] --> V3[\"[1, 2]\"]\n end\n\n style N0 fill:#00ceff,stroke:#000,color:#000\n style N1 fill:#00ceff,stroke:#000,color:#000\n style N2 fill:#00ceff,stroke:#000,color:#000\n style N3 fill:#00ceff,stroke:#000,color:#000\n style L0 fill:#38d9a9,stroke:#000,color:#000\n style L1 fill:#38d9a9,stroke:#000,color:#000\n style L2 fill:#38d9a9,stroke:#000,color:#000\n style L3 fill:#38d9a9,stroke:#000,color:#000\n style K0 fill:#ffa94d,stroke:#000,color:#000\n style K1 fill:#ffa94d,stroke:#000,color:#000\n style K2 fill:#ffa94d,stroke:#000,color:#000\n style K3 fill:#ffa94d,stroke:#000,color:#000\n style V0 fill:#69db7c,stroke:#000,color:#000\n style V1 fill:#69db7c,stroke:#000,color:#000\n style V2 fill:#69db7c,stroke:#000,color:#000\n style V3 fill:#69db7c,stroke:#000,color:#000\n```\n\n\n\n| Approach | Pros | Cons | Use When |\n|----------|------|------|----------|\n| `List>` | Fast index access, no hashing overhead | Wastes space if node IDs are sparse | Nodes are 0 to n-1 |\n| `Dictionary>` | Handles any node IDs, no wasted space | Slightly slower due to hashing | Node IDs are large, sparse, or non-numeric |\n\n\n---\n\n# Tuples and ValueTuple\n\nC# has built-in tuple support with named fields, value equality, and the ability to use them as dictionary keys, all out of the box.\n\n**Basic tuple syntax:**\n\n\n```csharp\n// Creating tuples\n(int row, int col) cell = (0, 1);\nvar pair = (5, 10); // Unnamed tuple\nvar named = (x: 3, y: 4); // Named tuple\n\n// Accessing fields\nint r = cell.row; // Named access\nint c = cell.col;\nint a = pair.Item1; // Default names when unnamed\nint b = pair.Item2;\n```\n\n\n**Tuples as dictionary keys** (a common DSA pattern):\n\n\n```csharp\n// Track visited states in BFS with multiple dimensions\nvar visited = new HashSet<(int row, int col)>();\nvisited.Add((0, 0));\nif (visited.Contains((newRow, newCol))) { ... }\n\n// Memoization with multiple parameters\nvar memo = new Dictionary<(int index, int remaining), int>();\nif (memo.TryGetValue((i, k), out int cached)) return cached;\nmemo[(i, k)] = result;\n```\n\n\nTuples give you value-based hashing and equality out of the box, so they work directly as dictionary keys without writing a custom equality implementation.\n\n**Tuple deconstruction:**\n\n\n```csharp\n// Deconstruct into individual variables\nvar (row, col) = queue.Dequeue();\n\n// Deconstruct in foreach\nforeach (var (key, value) in dictionary) {\n // use key and value directly\n}\n\n// Swap two variables using tuple deconstruction\n(a, b) = (b, a); // No temp variable needed!\n```\n\n\nThat last pattern, swapping via tuple deconstruction, replaces the three-line temp variable swap with a single line.\n\n**Tuple comparison** uses value equality (compares each field):\n\n\n```csharp\n(1, 2) == (1, 2) // true (value equality)\n(1, 2) == (1, 3) // false\n```\n\n\n**Using tuples in priority queues:**\n\n\n```csharp\n// Dijkstra with tuple: (node, distance)\nvar pq = new PriorityQueue<(int node, int dist), int>();\npq.Enqueue((startNode, 0), 0); // element, priority\n\n// BFS with state: (row, col, steps)\nvar queue = new Queue<(int row, int col, int steps)>();\nqueue.Enqueue((0, 0, 0));\nvar (r, c, steps) = queue.Dequeue();\n```\n\n\n---\n\n# Deduplication Patterns\n\nMany DSA problems require avoiding duplicate results (e.g., 3Sum, 4Sum, permutations with duplicates). C# offers two approaches:\n\n**Approach 1: Sort and skip duplicates (preferred for sorted array problems)**\n\n\n```csharp\nArray.Sort(nums);\nfor (int i = 0; i < nums.Length; i++) {\n // Skip duplicates: if this value is the same as the previous, skip it\n if (i > 0 && nums[i] == nums[i - 1]) continue;\n // Process nums[i]\n}\n```\n\n\nThis is the standard approach for problems like 3Sum and 4Sum. It runs in O(1) extra space (beyond the sort) and produces results in sorted order.\n\n**Approach 2: Use a HashSet to collect unique results**\n\n\n```csharp\nvar resultSet = new HashSet<(int, int, int)>(); // Tuples have value equality!\n// ... generate candidates ...\nresultSet.Add((a, b, c)); // Duplicates are automatically ignored\nreturn resultSet.Select(t => new List {t.Item1, t.Item2, t.Item3}).ToList();\n```\n\n\nC# tuples work well here. Because tuples have value equality, you can put them directly in a `HashSet` for deduplication.\n\n---\n\n# Common DSA Idioms in C#\n\nThis section collects the small patterns and utility calls that come up repeatedly across problems.\n\n**Swapping elements:**\n\n\n```csharp\n// Traditional swap\nint temp = arr[i];\narr[i] = arr[j];\narr[j] = temp;\n\n// Tuple swap (shorter)\n(arr[i], arr[j]) = (arr[j], arr[i]);\n```\n\n\nThe tuple swap is a C# exclusive that makes your code shorter and less error-prone.\n\n**Sentinel values** for tracking min/max:\n\n\n```csharp\nint minVal = int.MaxValue; // 2,147,483,647\nint maxVal = int.MinValue; // -2,147,483,648\nforeach (int num in nums) {\n minVal = Math.Min(minVal, num);\n maxVal = Math.Max(maxVal, num);\n}\n```\n\n\nBe careful with `int.MinValue`. Negating it (`-int.MinValue`) overflows because the positive range is one less than the negative range. If you need to negate values that might be `int.MinValue`, use `long`.\n\n**Math utilities:**\n\n\n```csharp\nMath.Max(a, b); // Larger of two values\nMath.Min(a, b); // Smaller of two values\nMath.Abs(a); // Absolute value (careful with MinValue)\n(int)Math.Pow(2, 10); // Power (returns double, cast to int)\nMath.Sqrt(n); // Square root (returns double)\nMath.Log(n); // Natural logarithm\nMath.Ceiling(a / (double)b); // Ceiling division (cast to double first!)\n```\n\n\n**Ceiling division** without floating point:\n\n\n```csharp\n// Integer ceiling division: ceil(a / b) for positive a, b\nint ceil = (a + b - 1) / b;\n// Or equivalently:\nint ceil = (a - 1) / b + 1;\n```\n\n\n**Type conversions:**\n\n\n```csharp\n// int[] to List\nList list = new List(nums); // Constructor accepts IEnumerable\n// Or with LINQ:\nList list = nums.ToList();\n\n// List to int[]\nint[] arr = list.ToArray();\n\n// string <-> char[]\nchar[] chars = str.ToCharArray();\nstring str = new string(chars);\n\n// string <-> int\nint num = int.Parse(\"42\");\nstring str = 42.ToString();\n// Safe parsing:\nif (int.TryParse(\"42\", out int result)) { ... }\n\n// int <-> long\nlong big = (long)smallInt;\nint small = (int)bigLong; // Careful: truncates if value exceeds int range\n```\n\n\n\n```mermaid\nflowchart LR\n IA[\"int[]\"]\n LI[\"List<int>\"]\n STR[\"string\"]\n CA[\"char[]\"]\n INT[\"int\"]\n\n IA -->|\"new List(arr)
or .ToList()\"| LI\n LI -->|\".ToArray()\"| IA\n STR -->|\".ToCharArray()\"| CA\n CA -->|\"new string(arr)\"| STR\n STR -->|\"int.Parse()\"| INT\n INT -->|\".ToString()\"| STR\n\n style IA fill:#00ceff,stroke:#000,color:#000\n style LI fill:#00ceff,stroke:#000,color:#000\n style STR fill:#ffa94d,stroke:#000,color:#000\n style CA fill:#ffa94d,stroke:#000,color:#000\n style INT fill:#69db7c,stroke:#000,color:#000\n```\n\n\nConverting between `int[]` and `List` is straightforward in C#. The `List` constructor directly accepts arrays, and `.ToList()` / `.ToArray()` handle the reverse. No manual loops needed.\n\n**Deep copy vs shallow copy:**\n\nWhen you add a list to another list, you are adding a reference. If the original list changes later, the \"copy\" changes too:\n\n\n```csharp\nvar path = new List {1, 2};\nvar results = new List>();\n\nresults.Add(path); // BAD: adds reference\npath.Add(3);\n// results[0] now contains [1, 2, 3], not [1, 2]\n\nresults.Add(new List(path)); // GOOD: adds a copy\n```\n\n\nFor arrays, use `Clone()` or `Array.Copy()`:\n\n\n```csharp\nint[] copy = (int[])original.Clone();\n// Or:\nint[] copy = new int[original.Length];\nArray.Copy(original, copy, original.Length);\n```\n\n\nFor 2D jagged arrays, `Clone()` only copies the outer array. The inner arrays are still shared references. You need a manual deep copy:\n\n\n```csharp\nint[][] deepCopy = new int[matrix.Length][];\nfor (int i = 0; i < matrix.Length; i++) {\n deepCopy[i] = (int[])matrix[i].Clone();\n}\n```\n\n\n---\n\n# OOP Basics for DSA\n\nDSA problems often define custom node classes. These definitions appear throughout the course:\n\n\n```csharp\n// Linked list node\npublic class ListNode {\n public int val;\n public ListNode next;\n\n public ListNode(int val = 0, ListNode next = null) {\n this.val = val;\n this.next = next;\n }\n}\n\n// Binary tree node\npublic class TreeNode {\n public int val;\n public TreeNode left;\n public TreeNode right;\n\n public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {\n this.val = val;\n this.left = left;\n this.right = right;\n }\n}\n\n// Graph node with neighbors\npublic class Node {\n public int val;\n public IList neighbors;\n\n public Node(int val = 0) {\n this.val = val;\n this.neighbors = new List();\n }\n}\n\n// Trie node\npublic class TrieNode {\n public TrieNode[] children;\n public bool isEndOfWord;\n\n public TrieNode() {\n this.children = new TrieNode[26]; // For lowercase a-z\n this.isEndOfWord = false;\n }\n}\n```\n\n\nThe `public` keyword on fields makes them accessible from anywhere. In production C#, you would use properties with getters and setters, but for DSA, public fields are standard practice. You are not building production software here. You are solving problems under time pressure, and the overhead of encapsulation adds no value.\n\nC# supports **default parameter values** in constructors (like `val = 0, next = null`), which reduces the need for constructor overloading. One constructor can handle multiple call patterns.\n\nLeetCode often provides these node definitions. The default parameter constructor is handy for building data structures concisely:\n\n\n```csharp\n// Build list: 1 -> 2 -> 3 -> null\nListNode head = new ListNode(1, new ListNode(2, new ListNode(3)));\n```\n\n\n**The **`this`** keyword** refers to the current instance. It appears most often in constructors to distinguish the parameter from the field (`this.val = val`).","pageType":"dsa"}

Get Premium