Master fundamental array techniques including prefix sum arrays, range queries, lazy propagation, and classic array manipulation patterns. These problems build the foundation for more complex data structures and algorithms.
Understanding prefix sum arrays is essential for solving range query problems efficiently. Learn the concept, implementation patterns, and why certain design choices matter.
A prefix sum array stores cumulative sums: P[i] = A[0] + A[1] + ... + A[i]
Key insight: Sum of elements from index L to R = P[R] - P[L-1], computed in O(1).
long[].// Template: Build Prefix Sum Array long[] BuildPrefixSum(int[] A) { long[] P = new long[A.Length + 1]; P[0] = 0; for (int i = 0; i < A.Length; i++) { P[i + 1] = P[i] + A[i]; } return P; } // Template: Range Sum Query O(1) long RangeSum(long[] P, int L, int R) { // Sum of A[L..R] return P[R + 1] - P[L]; }
Many problems require checking membership. HashSet provides constant-time lookups with good cache locality.
// Efficient membership checking HashSet<int> seen = new HashSet<int>(); for (int i = 1; i <= N; i++) { if (!seen.Contains(A[i])) { // Found missing element } seen.Add(A[i]); }
For problems like GenomicRangeQuery, build separate prefix sums for each category (A, C, G, T).
// Multi-category prefix sums int[][] prefixCount = new int[4][]; // A, C, G, T for (int cat = 0; cat < 4; cat++) { prefixCount[cat] = new int[S.Length + 1]; for (int i = 0; i < S.Length; i++) { prefixCount[cat][i + 1] = prefixCount[cat][i]; if (S[i] == CharForCategory(cat)) { prefixCount[cat][i + 1]++; } } }
Instead of updating each element individually (O(N)), track range updates and apply them lazily during queries.
The smallest missing positive must be in range [1, N+1]. If all 1..N are present, answer is N+1. Otherwise, answer is the first gap. Use a HashSet to mark present values, then iterate 1..N+1 to find the first missing.
Time: O(N) for building set + O(N) for scanning = O(N). Space: O(N) for HashSet.
public int Solution(int[] A) { HashSet<int> present = new HashSet<int>(); for (int i = 0; i < A.Length; i++) { if (A[i] > 0) { present.Add(A[i]); } } for (int candidate = 1; candidate <= A.Length + 1; candidate++) { if (!present.Contains(candidate)) { return candidate; } } return A.Length + 1; }
A permutation has every value 1..N exactly once. Method: (1) Check all values in [1..N], (2) Check no duplicates using HashSet size. If set size = N and all values in range, it's a permutation.
Time: O(N). Space: O(N).
public int Solution(int[] A) { if (A.Length == 0) return 0; HashSet<int> seen = new HashSet<int>(); for (int i = 0; i < A.Length; i++) { // Must be in range [1, N] if (A[i] < 1 || A[i] > A.Length) return 0; // No duplicates if (seen.Contains(A[i])) return 0; seen.Add(A[i]); } return 1; }
Naive: O(M×(R-L)) for M queries. Optimized: Build 4 prefix sum arrays (one per nucleotide). For each query, check if each nucleotide exists in range using prefix sums (O(1) per nucleotide). Return minimum impact of present nucleotides. Total: O(N) preprocessing + O(4M) = O(N + M).
public int[] Solution(string S, int[] P, int[] Q) { int N = S.Length; int M = P.Length; // Prefix sums for A, C, G, T int[][] prefix = new int[4][]; for (int i = 0; i < 4; i++) { prefix[i] = new int[N + 1]; } for (int i = 0; i < N; i++) { for (int j = 0; j < 4; j++) { prefix[j][i + 1] = prefix[j][i]; } int idx = NucleotideIndex(S[i]); prefix[idx][i + 1]++; } int[] result = new int[M]; for (int q = 0; q < M; q++) { int L = P[q], R = Q[q]; for (int nuc = 0; nuc < 4; nuc++) { int count = prefix[nuc][R + 1] - prefix[nuc][L]; if (count > 0) { result[q] = nuc + 1; // Impact: A=1, C=2, G=3, T=4 break; } } } return result; } private int NucleotideIndex(char c) { switch(c) { case 'A': return 0; case 'C': return 1; case 'G': return 2; case 'T': return 3; default: return -1; } }
Naive: O(N²) nested loop. Optimized: For each west car (A[j]=1), count how many east cars (0s) appear before it. Use a running counter of 0s seen so far. When we see a 1, add the counter to result.
Time: O(N). Space: O(1).
public int Solution(int[] A) { long count = 0; int eastCount = 0; for (int i = 0; i < A.Length; i++) { if (A[i] == 0) { eastCount++; } else { count += eastCount; // Prevent overflow: if > 1 billion, return -1 if (count > 1_000_000_000) return -1; } } return (int)count; }
Naive: For each max_counter, loop and set all N counters (O(N)). With M operations, total O(N×M), too slow.
Optimized (Lazy): Track global max without updating all counters. For each counter, track its "checkpoint" (when it was last set to max). During increment, if counter's checkpoint is outdated, first bring it up to checkpoint value. At the end, update all counters based on final checkpoint.
Time: O(N + M). Space: O(N).
public int[] Solution(int N, int[] A) { int[] counters = new int[N]; int maxCounter = 0; int lastMax = 0; // Checkpoint value for (int op = 0; op < A.Length; op++) { int X = A[op] - 1; // 1-indexed to 0-indexed if (X == N) { // Max counter operation lastMax = maxCounter; } else { // Increment counter X if (counters[X] < lastMax) { counters[X] = lastMax; } counters[X]++; maxCounter = Math.Max(maxCounter, counters[X]); } } // Final pass: bring all counters up to lastMax for (int i = 0; i < N; i++) { if (counters[i] < lastMax) { counters[i] = lastMax; } } return counters; }
We need all positions 1 to X covered. Use a HashSet to track which positions have leaves. For each time step, add A[t] to the set. Once the set contains all 1..X, return that time. If we finish the array without covering all positions, return -1.
Time: O(N). Space: O(X).
public int Solution(int X, int[] A) { HashSet<int> covered = new HashSet<int>(); for (int t = 0; t < A.Length; t++) { if (A[t] >= 1 && A[t] <= X) { covered.Add(A[t]); } // Check if all positions 1..X are covered if (covered.Count == X) { return t; } } return -1; }
Formula: Count of multiples of K in [A, B] = ⌊B / K⌋ − ⌊(A − 1) / K⌋
Example: K=5, range [11, 23]. Multiples: 15, 20. Formula: ⌊23/5⌋ − ⌊10/5⌋ = 4 − 2 = 2. ✓
Time: O(1). Space: O(1).
public int Solution(int A, int B, int K) { return (B / K) - ((A - 1) / K); }
Step 1: Find the global leader (appears > N/2 times). Use Boyer-Moore voting algorithm: O(N).
Step 2: Build prefix counts: count[i] = how many times leader appears in A[0..i]. O(N).
Step 3: For each split position P, check if leader appears > (P+1)/2 times on left AND > (N-P-1)/2 times on right. O(N).
Time: O(N). Space: O(N).
public int Solution(int[] A) { int N = A.Length; // Step 1: Find global leader using Boyer-Moore int candidate = 0, count = 0; for (int i = 0; i < N; i++) { if (count == 0) candidate = A[i]; count += (A[i] == candidate) ? 1 : -1; } // Verify candidate is actually the leader count = 0; for (int i = 0; i < N; i++) { if (A[i] == candidate) count++; } if (count <= N / 2) return 0; // No leader int leader = candidate; // Step 2: Build prefix counts int[] leaderCount = new int[N]; leaderCount[0] = (A[0] == leader) ? 1 : 0; for (int i = 1; i < N; i++) { leaderCount[i] = leaderCount[i - 1] + ((A[i] == leader) ? 1 : 0); } // Step 3: Count equi-leader positions int result = 0; for (int P = 0; P < N - 1; P++) { int leftSize = P + 1; int rightSize = N - leftSize; int leftLeaderCount = leaderCount[P]; int rightLeaderCount = leaderCount[N - 1] - leaderCount[P]; if (leftLeaderCount > leftSize / 2 && rightLeaderCount > rightSize / 2) { result++; } } return result; }
Use prefix and suffix products. result[i] = (product of all left of i) × (product of all right of i). Build two passes: one for left products, one for right products.
Time: O(N). Space: O(1) if we don't count output array.
public int[] ProductExceptSelf(int[] nums) { int n = nums.Length; int[] result = new int[n]; // Left pass: result[i] = product of all elements to the left result[0] = 1; for (int i = 1; i < n; i++) { result[i] = result[i - 1] * nums[i - 1]; } // Right pass: multiply by product of all elements to the right int rightProduct = 1; for (int i = n - 1; i >= 0; i--) { result[i] *= rightProduct; rightProduct *= nums[i]; } return result; }
Key insight: If prefix sum up to i = P and we want sum[j..i] = K, then P − sum[j−1] = K, so sum[j−1] = P − K. Use HashMap to count occurrences of each prefix sum. For each position, check if (currentSum − K) exists in the map.
Time: O(N). Space: O(N).
public int SubarraySum(int[] nums, int k) { Dictionary<int, int> prefixMap = new Dictionary<int, int>(); prefixMap[0] = 1; // Base case: sum 0 seen once int count = 0; int currentSum = 0; for (int i = 0; i < nums.Length; i++) { currentSum += nums[i]; int target = currentSum - k; // Check if (currentSum - k) exists in map if (prefixMap.ContainsKey(target)) { count += prefixMap[target]; } // Add current prefix sum to map if (!prefixMap.ContainsKey(currentSum)) { prefixMap[currentSum] = 0; } prefixMap[currentSum]++; } return count; }
Kadane's Algorithm: Track max sum ending at current position. For each element, decide: extend previous subarray or start new one. If adding element to previous sum is worse than just the element, reset.
State: maxEndingHere = max sum of subarray ending at current index. Update global maxSoFar each step.
Time: O(N). Space: O(1).
public int MaxSubArray(int[] nums) { int maxEndingHere = nums[0]; int maxSoFar = nums[0]; for (int i = 1; i < nums.Length; i++) { // Either extend subarray or start fresh maxEndingHere = Math.Max(nums[i], maxEndingHere + nums[i]); // Update global maximum maxSoFar = Math.Max(maxSoFar, maxEndingHere); } return maxSoFar; }
Work backwards from the end. Start with three pointers: end of nums1 (m+n-1), end of filled nums1 (m-1), end of nums2 (n-1). Compare and place the larger element at the current position, moving pointers backward. This avoids overwriting unprocessed elements.
Time: O(m + n). Space: O(1).
public void Merge(int[] nums1, int m, int[] nums2, int n) { int p1 = m - 1; // Pointer for nums1 int p2 = n - 1; // Pointer for nums2 int p = m + n - 1; // Pointer for result position while (p1 >= 0 && p2 >= 0) { if (nums1[p1] > nums2[p2]) { nums1[p] = nums1[p1]; p1--; } else { nums1[p] = nums2[p2]; p2--; } p--; } // Copy remaining nums2 elements (if any) while (p2 >= 0) { nums1[p] = nums2[p2]; p2--; p--; } // No need to copy remaining nums1 elements; they're already in place }
Reverse trick: Rotating right by k is equivalent to: reverse entire array, reverse first k elements, reverse remaining n−k elements.
Example: [1,2,3,4,5], k=2. Reverse all → [5,4,3,2,1]. Reverse first 2 → [4,5,3,2,1]. Reverse last 3 → [4,5,1,2,3]. ✓
Time: O(N). Space: O(1).
public void Rotate(int[] nums, int k) { int n = nums.Length; k = k % n; // Handle k >= n // Reverse entire array Reverse(nums, 0, n - 1); // Reverse first k elements Reverse(nums, 0, k - 1); // Reverse remaining elements Reverse(nums, k, n - 1); } private void Reverse(int[] nums, int start, int end) { while (start < end) { int temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; start++; end--; } }
Use HashSet to track seen elements. For each element, check if already in set. If yes, return true. If we finish without duplicates, return false.
Time: O(N) average. Space: O(min(N, M)) where M is number of distinct values.
public bool ContainsDuplicate(int[] nums) { HashSet<int> seen = new HashSet<int>(); foreach (int num in nums) { if (seen.Contains(num)) { return true; } seen.Add(num); } return false; }
Key insight: Max circular subarray = max(max non-circular, total − min subarray). Non-circular max = standard Kadane. For circular: total sum − minimum subarray = maximum wraparound subarray. Use min-Kadane (track minimum subarray). Return max of the two cases, but handle edge case where min subarray is entire array (all negative numbers).
Time: O(N). Space: O(1).
public int MaxSubarraySumCircular(int[] nums) { int totalSum = 0; int maxSum = int.MinValue; int minSum = int.MaxValue; int maxEndingHere = 0; int minEndingHere = 0; for (int i = 0; i < nums.Length; i++) { totalSum += nums[i]; // Kadane's for maximum maxEndingHere = Math.Max(nums[i], maxEndingHere + nums[i]); maxSum = Math.Max(maxSum, maxEndingHere); // Kadane's for minimum minEndingHere = Math.Min(nums[i], minEndingHere + nums[i]); minSum = Math.Min(minSum, minEndingHere); } // If minSum == totalSum, all elements are minimum (negative) if (minSum == totalSum) { return maxSum; } // Return max of non-circular and circular cases return Math.Max(maxSum, totalSum - minSum); }