Master advanced problem-solving patterns: prefix sums, difference arrays, monotonic structures, event-based algorithms, and essential string/math techniques. Learn when and how to apply each pattern to optimize time complexity from naive O(n²) to O(n) or better.
Transform O(n) range queries into O(1) lookups by precomputing cumulative sums. Essential for interviews involving subarray sums and range queries.
A prefix sum array stores the cumulative sum of elements up to index i. Once built in O(n), any range sum can be answered in O(1).
Key insight: sum(i, j) = prefix[j+1] - prefix[i]
// Build prefix sum array public int[] BuildPrefixSum(int[] nums) { int[] prefix = new int[nums.Length + 1]; for (int i = 0; i < nums.Length; i++) { prefix[i + 1] = prefix[i] + nums[i]; } return prefix; } // Query range sum [left, right] (inclusive) public int RangeSum(int[] prefix, int left, int right) { return prefix[right + 1] - prefix[left]; }
// Template: Prefix Sum for Range Queries class PrefixSumTemplate { int[] prefix; public PrefixSumTemplate(int[] nums) { prefix = new int[nums.Length + 1]; for (int i = 0; i < nums.Length; i++) prefix[i + 1] = prefix[i] + nums[i]; } public int SumRange(int left, int right) { return prefix[right + 1] - prefix[left]; } }
Extend prefix sums to 2D matrices for O(1) rectangle sum queries using inclusion-exclusion principle.
For a 2D matrix, prefix[i][j] = sum of all elements in rectangle from (0,0) to (i-1, j-1).
Inclusion-Exclusion Formula:
sum(r1,c1,r2,c2) = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]
// 2D Prefix Sum class NumMatrix { int[][] prefix; public NumMatrix(int[][] matrix) { int m = matrix.Length; int n = matrix[0].Length; prefix = new int[m + 1][]; for (int i = 0; i <= m; i++) prefix[i] = new int[n + 1]; // Build 2D prefix array for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { prefix[i][j] = matrix[i - 1][j - 1] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1]; } } } // Query rectangle sum: rows [row1..row2], cols [col1..col2] public int SumRegion(int row1, int col1, int row2, int col2) { return prefix[row2 + 1][col2 + 1] - prefix[row1][col2 + 1] - prefix[row2 + 1][col1] + prefix[row1][col1]; } }
Six classic problems demonstrating prefix sum patterns in interviews and competitive programming.
Given an array, answer multiple range sum queries. Simple baseline problem.
class NumArray { int[] prefix; public NumArray(int[] nums) { prefix = new int[nums.Length + 1]; for (int i = 0; i < nums.Length; i++) prefix[i + 1] = prefix[i] + nums[i]; } public int SumRange(int left, int right) { return prefix[right + 1] - prefix[left]; } }
2D matrix range sum queries using 2D prefix sums (shown in 19.2).
Find count of subarrays with sum equal to k. Use prefix sums with HashMap.
public int SubarraySum(int[] nums, int k) { var prefixMap = new Dictionary<int, int>(); prefixMap[0] = 1; // Base case: prefix sum 0 int prefixSum = 0, count = 0; foreach (int num in nums) { prefixSum += num; // Check if (prefixSum - k) exists // If yes: subarray from that point to current has sum k if (prefixMap.ContainsKey(prefixSum - k)) count += prefixMap[prefixSum - k]; if (!prefixMap.ContainsKey(prefixSum)) prefixMap[prefixSum] = 0; prefixMap[prefixSum]++; } return count; }
Check if subarray exists with sum divisible by k. Use modulo prefix sums.
public bool CheckSubarraySum(int[] nums, int k) { var modMap = new Dictionary<int, int>(); modMap[0] = -1; // Track first occurrence int prefixSum = 0; foreach (int i = 0; i < nums.Length; i++) { prefixSum += nums[i]; int mod = prefixSum % k; // Handle negative: mod = ((prefixSum % k) + k) % k if (modMap.ContainsKey(mod)) { if (i - modMap[mod] >= 2) // Length >= 2 return true; } else { modMap[mod] = i; } } return false; }
Find index where left sum equals right sum.
public int PivotIndex(int[] nums) { int total = 0; foreach (int num in nums) total += num; int left = 0; for (int i = 0; i < nums.Length; i++) { int right = total - left - nums[i]; if (left == right) return i; left += nums[i]; } return -1; }
Compute product of all elements except self, without division operator.
public int[] ProductExceptSelf(int[] nums) { int n = nums.Length; int[] result = new int[n]; // Pass 1: prefix products (left to right) result[0] = 1; for (int i = 1; i < n; i++) result[i] = result[i - 1] * nums[i - 1]; // Pass 2: suffix products (right to left) int suffix = 1; for (int i = n - 1; i >= 0; i--) { result[i] *= suffix; suffix *= nums[i]; } return result; }
Perform range updates in O(1) instead of O(n). Critical for interval-heavy problems.
Instead of updating all elements in a range, store differences. Apply all updates at once with a single pass.
// Difference array for range updates class DifferenceArray { int[] diff; public DifferenceArray(int n) { diff = new int[n + 1]; } // Add value to range [left, right] in O(1) public void RangeAdd(int left, int right, int value) { diff[left] += value; diff[right + 1] -= value; } // Apply all updates and return final array public int[] GetResult() { int[] result = new int[diff.Length - 1]; int cumsum = 0; for (int i = 0; i < result.Length; i++) { cumsum += diff[i]; result[i] = cumsum; } return result; } }
Given booking queries, find final seat occupancy. Classic difference array application.
public int[] CorpFlightBookings(int[][] bookings, int n) { int[] diff = new int[n + 1]; // Apply each booking as range update foreach (int[] booking in bookings) { int first = booking[0] - 1; // Convert to 0-indexed int last = booking[1] - 1; int seats = booking[2]; diff[first] += seats; diff[last + 1] -= seats; } // Convert difference array to result int[] result = new int[n]; int cumsum = 0; for (int i = 0; i < n; i++) { cumsum += diff[i]; result[i] = cumsum; } return result; }
Find maximum sum subarray in O(n). Essential greedy dynamic programming pattern.
Find contiguous subarray with largest sum.
public int MaxSubArray(int[] nums) { int maxCurrent = nums[0]; int maxGlobal = nums[0]; for (int i = 1; i < nums.Length; i++) { // At each step: extend current subarray or start fresh maxCurrent = Math.Max(nums[i], maxCurrent + nums[i]); maxGlobal = Math.Max(maxGlobal, maxCurrent); } return maxGlobal; }
Find contiguous subarray with largest product. Trickier due to negatives.
public int MaxProduct(int[] nums) { int maxProd = nums[0]; int minProd = nums[0]; int result = nums[0]; for (int i = 1; i < nums.Length; i++) { // Track both max and min (negative can become max) int newMax = Math.Max(nums[i], Math.Max(maxProd * nums[i], minProd * nums[i])); int newMin = Math.Min(nums[i], Math.Min(maxProd * nums[i], minProd * nums[i])); maxProd = newMax; minProd = newMin; result = Math.Max(result, maxProd); } return result; }
Array is circular. Max sum can wrap around.
public int MaxSubarraySumCircular(int[] nums) { int totalSum = 0; int maxKadane = nums[0]; int minKadane = nums[0]; int curMax = nums[0]; int curMin = nums[0]; for (int i = 1; i < nums.Length; i++) { // Standard Kadane for max curMax = Math.Max(nums[i], curMax + nums[i]); maxKadane = Math.Max(maxKadane, curMax); // Modified Kadane for min curMin = Math.Min(nums[i], curMin + nums[i]); minKadane = Math.Min(minKadane, curMin); totalSum += nums[i]; } // Either take max subarray (normal) or total - min (wrap around) return maxKadane > 0 ? Math.Max(maxKadane, totalSum - minKadane) : maxKadane; }
Find next/previous greater/smaller elements in O(n). Essential for optimization problems.
A monotonic stack maintains elements in increasing or decreasing order, enabling O(n) solutions to problems that naively require O(n²).
For each element, find the next greater element in the array.
public int[] NextGreaterElement(int[] nums1, int[] nums2) { var map = new Dictionary<int, int>(); var stack = new Stack<int>(); // Build map using monotonic stack on nums2 for (int i = nums2.Length - 1; i >= 0; i--) { // Pop smaller elements (they have a greater element) while (stack.Count > 0 && stack.Peek() < nums2[i]) stack.Pop(); // Current top is next greater (or none if stack empty) map[nums2[i]] = stack.Count == 0 ? -1 : stack.Peek(); stack.Push(nums2[i]); } int[] result = new int[nums1.Length]; for (int i = 0; i < nums1.Length; i++) result[i] = map[nums1[i]]; return result; }
Circular version: array wraps around.
public int[] NextGreaterElements(int[] nums) { int n = nums.Length; int[] result = new int[n]; Array.Fill(result, -1); var stack = new Stack<int>(); // Iterate twice to handle circular nature for (int i = 0; i < 2 * n; i++) { int idx = i % n; while (stack.Count > 0 && nums[stack.Peek()] < nums[idx]) { result[stack.Pop()] = nums[idx]; } // Only push on first pass if (i < n) stack.Push(idx); } return result; }
Days until a warmer temperature. Stack stores indices.
public int[] DailyTemperatures(int[] temperatures) { int n = temperatures.Length; int[] result = new int[n]; var stack = new Stack<int>(); // Store indices for (int i = n - 1; i >= 0; i--) { // Pop temperatures <= current while (stack.Count > 0 && temperatures[stack.Peek()] <= temperatures[i]) stack.Pop(); // Days until warmer day if (stack.Count > 0) result[i] = stack.Peek() - i; stack.Push(i); } return result; }
Find largest rectangle area in histogram using monotonic stack.
public int LargestRectangleArea(int[] heights) { var stack = new Stack<int>(); int maxArea = 0; for (int i = 0; i <= heights.Length; i++) { int h = i == heights.Length ? 0 : heights[i]; // Pop smaller heights and calculate areas while (stack.Count > 0 && heights[stack.Peek()] > h) { int height = heights[stack.Pop()]; int width = stack.Count == 0 ? i : i - stack.Peek() - 1; maxArea = Math.Max(maxArea, height * width); } stack.Push(i); } return maxArea; }
Trap rainwater using monotonic stack.
public int Trap(int[] height) { var stack = new Stack<int>(); int water = 0; for (int i = 0; i < height.Length; i++) { while (stack.Count > 0 && height[stack.Peek()] < height[i]) { int bottom = stack.Pop(); if (stack.Count == 0) break; int h = Math.Min(height[stack.Peek()], height[i]) - height[bottom]; int w = i - stack.Peek() - 1; water += h * w; } stack.Push(i); } return water; }
Find min/max in sliding window in O(n). Use deque for efficient front/back operations.
Find max element in every sliding window of size k.
public int[] MaxSlidingWindow(int[] nums, int k) { var deque = new LinkedList<int>(); var result = new List<int>(); for (int i = 0; i < nums.Length; i++) { // Remove elements outside window if (deque.Count > 0 && deque.First.Value < i - k + 1) deque.RemoveFirst(); // Remove smaller elements (they can't be max) while (deque.Count > 0 && nums[deque.Last.Value] <= nums[i]) deque.RemoveLast(); // Add current index deque.AddLast(i); // Add max to result (front of deque) if (i >= k - 1) result.Add(nums[deque.First.Value]); } return result.ToArray(); }
Transform 2D interval problems into 1D by processing events in order.
Minimum conference rooms needed. Use event-based sweep line.
public int MinMeetingRooms(int[][] intervals) { var events = new List<(int, int)>(); // (time, type: 0=start, 1=end) foreach (var interval in intervals) { events.Add((interval[0], 0)); // Start events.Add((interval[1], 1)); // End } // Sort: first by time, then ends before starts events.Sort((a, b) => a.Item1 == b.Item1 ? a.Item2.CompareTo(b.Item2) : a.Item1.CompareTo(b.Item1)); int rooms = 0, maxRooms = 0; foreach (var (time, eventType) in events) { if (eventType == 0) rooms++; else rooms--; maxRooms = Math.Max(maxRooms, rooms); } return maxRooms; }
Validate calendar bookings—no overlaps allowed.
class MyCalendar { List<(int, int)> bookings = new List<(int, int)>(); public bool Book(int start, int end) { foreach (var (s, e) in bookings) { // Check overlap: not (end <= s or start >= e) if (!(end <= s || start >= e)) return false; } bookings.Add((start, end)); return true; } }
When values are huge but count is small, map to compressed range.
// Compress coordinates: 1,100,1000 -> 0,1,2 public int[] CompressCoordinates(int[] coords) { var sorted = new HashSet<int>(coords); var map = new Dictionary<int, int>(); int idx = 0; foreach (int c in sorted.OrderBy(x => x)) map[c] = idx++; return coords.Select(c => map[c]).ToArray(); }
In-place matrix transformations: rotation, spiral traversal, and zero setting.
Traverse matrix in spiral order.
public IList<int> SpiralOrder(int[][] matrix) { var result = new List<int>(); int top = 0, bottom = matrix.Length - 1; int left = 0, right = matrix[0].Length - 1; while (top <= bottom && left <= right) { // Traverse right for (int i = left; i <= right; i++) result.Add(matrix[top][i]); top++; // Traverse down for (int i = top; i <= bottom; i++) result.Add(matrix[i][right]); right--; // Traverse left (if row exists) if (top <= bottom) { for (int i = right; i >= left; i--) result.Add(matrix[bottom][i]); bottom--; } // Traverse up (if column exists) if (left <= right) { for (int i = bottom; i >= top; i--) result.Add(matrix[i][left]); left++; } } return result; }
Rotate n×n matrix 90 degrees clockwise.
public void Rotate(int[][] matrix) { int n = matrix.Length; // Step 1: Transpose (swap across diagonal) for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } // Step 2: Reverse each row for (int i = 0; i < n; i++) { Array.Reverse(matrix[i]); } }
Set entire row/column to 0 if element is 0, using O(1) space.
public void SetZeroes(int[][] matrix) { int m = matrix.Length, n = matrix[0].Length; bool firstRowZero = false, firstColZero = false; // Check if first row/column need zeroing for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstColZero = true; for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRowZero = true; // Use first row/column as markers for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } // Apply zeros based on markers for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0; } } // Zero out first row/column if needed if (firstRowZero) for (int j = 0; j < n; j++) matrix[0][j] = 0; if (firstColZero) for (int i = 0; i < m; i++) matrix[i][0] = 0; }
Pattern matching and substring search: KMP, Rabin-Karp, and Z-Algorithm concepts.
Find pattern in text in O(n+m) without backtracking.
public int KMPSearch(string text, string pattern) { int n = text.Length, m = pattern.Length; int[] lps = BuildLPS(pattern); int i = 0, j = 0; while (i < n) { if (pattern[j] == text[i]) { i++; j++; } if (j == m) return i - j; // Found at index i-j else if (i < n && pattern[j] != text[i]) { j = lps[j - 1]; if (j < 0) { j = 0; i++; } } } return -1; } // Build LPS (Longest Proper Prefix which is also Suffix) private int[] BuildLPS(string pattern) { int m = pattern.Length; int[] lps = new int[m]; int len = 0, i = 1; while (i < m) { if (pattern[i] == pattern[len]) { lps[i] = ++len; i++; } else { if (len != 0) len = lps[len - 1]; else { lps[i] = 0; i++; } } } return lps; }
Fast substring search using polynomial rolling hash.
public int RabinKarp(string text, string pattern) { const int prime = 101; const int mod = 1000000007; int n = text.Length, m = pattern.Length; long patternHash = 0, textHash = 0; long basePower = 1; // Compute hashes and base power for (int i = 0; i < m; i++) { patternHash = (patternHash * prime + pattern[i]) % mod; textHash = (textHash * prime + text[i]) % mod; if (i < m - 1) basePower = (basePower * prime) % mod; } // Slide window for (int i = 0; i <= n - m; i++) { if (patternHash == textHash) if (text.Substring(i, m) == pattern) return i; // Roll hash if (i < n - m) { textHash = (textHash - (text[i] * basePower) % mod + mod) % mod; textHash = (textHash * prime + text[i + m]) % mod; } } return -1; }
Compute longest common prefix with suffix in O(n). Array Z[i] = length of substring starting at i matching prefix.
// Z-Algorithm: Compute Z array where Z[i] = LCP(S, S[i..]) public int[] ZAlgorithm(string s) { int n = s.Length; int[] z = new int[n]; z[0] = n; int l = 0, r = 0; for (int i = 1; i < n; i++) { if (i > r) { l = r = i; while (r < n && s[r - l] == s[r]) r++; z[i] = r - l; r--; } else { int k = i - l; if (z[k] < r - i + 1) z[i] = z[k]; else { l = i; while (r < n && s[r - l] == s[r]) r++; z[i] = r - l; r--; } } } return z; }
GCD, prime sieves, fast exponentiation, and sampling algorithms.
// Euclidean Algorithm for GCD public int GCD(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } // LCM using GCD public long LCM(long a, long b) { return (a / GCD((int)a, (int)b)) * b; }
Generate all primes up to n in O(n log log n).
public bool[] SieveOfEratosthenes(int n) { bool[] isPrime = new bool[n + 1]; for (int i = 2; i <= n; i++) isPrime[i] = true; for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { // Mark multiples as not prime for (int j = i * i; j <= n; j += i) isPrime[j] = false; } } return isPrime; }
Compute a^b mod m in O(log b).
public long FastExponentiation(long baseNum, long exp, long mod) { long result = 1; baseNum %= mod; while (exp > 0) { // If exponent is odd, multiply base with result if ((exp & 1) == 1) result = (result * baseNum) % mod; // Square base and halve exponent baseNum = (baseNum * baseNum) % mod; exp >>= 1; } return result; }
Pick k random elements from stream of unknown size.
public int[] ReservoirSampling(IEnumerable<int> stream, int k) { int[] reservoir = new int[k]; var random = new Random(); int count = 0; foreach (int num in stream) { if (count < k) { reservoir[count] = num; } else { // Random index in [0, count] int idx = random.Next(count + 1); if (idx < k) reservoir[idx] = num; } count++; } return reservoir; }
Essential bitwise operations for interview optimization.
Find element appearing once when others appear twice.
public int SingleNumber(int[] nums) { int result = 0; foreach (int num in nums) result ^= num; // XOR: a ^ a = 0, a ^ 0 = a return result; }
public int CountSetBits(int n) { int count = 0; while (n > 0) { count += n & 1; n >>= 1; } return count; // Alternatively: int count = BitOperations.PopCount((uint)n); }
public bool IsPowerOfTwo(int n) { // Power of 2 has single bit set: n & (n-1) == 0 return n > 0 && (n & (n - 1)) == 0; }
| Operation | Code | Use Case |
|---|---|---|
| Get bit at position i | (n >> i) & 1 |
Check if i-th bit set |
| Set bit at position i | n |= (1 << i) |
Turn on i-th bit |
| Clear bit at position i | n &= ~(1 << i) |
Turn off i-th bit |
| Toggle bit at position i | n ^= (1 << i) |
Flip i-th bit |
| Check if power of 2 | (n & (n-1)) == 0 |
Single bit check |
Identify which technique to apply based on problem constraints and keywords.
| Technique | Time (Build) | Time (Query) | Space |
|---|---|---|---|
| Prefix Sum 1D | O(n) | O(1) | O(n) |
| Prefix Sum 2D | O(m×n) | O(1) | O(m×n) |
| Difference Array | O(k) | O(n) | O(n) |
| Kadane's Algorithm | N/A | O(n) | O(1) |
| Monotonic Stack | N/A | O(n) | O(n) |
| Monotonic Queue | N/A | O(n) | O(k) |
| KMP | O(m) | O(n+m) | O(m) |
| Sieve | O(n log log n) | N/A | O(n) |
((a % m) + m) % m for correct result.