Array and string problems are the bread and butter of coding interviews, appearing in over 40% of questions. The key is recognizing which manipulation pattern applies. This guide covers the essential patterns for modifying arrays and strings efficiently — in-place operations, two-pass techniques, encoding/decoding, and matrix manipulations — giving you a toolkit for the most common interview problems.
Pattern 1: In-Place Array Modification
Many problems require modifying an array without extra space (O(1) auxiliary). Techniques: (1) Swap-based — Dutch National Flag (sort 0s, 1s, 2s): three pointers (low, mid, high). Swap elements to their correct region. O(N) time, O(1) space. (2) Overwrite from front — Remove Duplicates from Sorted Array: maintain a write pointer. Scan with a read pointer. When a new value is found, write it at the write pointer and advance both. Return the write pointer as the new length. (3) Overwrite from back — Merge Sorted Array (merge nums2 into nums1 which has enough trailing space): fill from the back to avoid overwriting unprocessed elements. Three pointers: end of nums1 data, end of nums2, and the write position (end of nums1 buffer). (4) Cyclic replacement — Rotate Array by K: each element moves to (i + K) % N. Start at index 0, move element to its destination, move the displaced element, repeat until back at start. If N % K != 0, start a new cycle. General rule: when asked to modify in-place, think about which direction to scan (front-to-back or back-to-front) and whether swapping or overwriting is appropriate.
Pattern 2: Two-Pass Techniques
Some problems require information from both directions. Solve with two passes. Product of Array Except Self: the product at position i is the product of all elements to its left times all elements to its right. First pass (left to right): compute prefix products. result[i] = product of nums[0..i-1]. Second pass (right to left): multiply each result[i] by the suffix product (product of nums[i+1..N-1]). O(N) time, O(1) extra space (using the result array for prefix products). Trapping Rain Water: at each position, the water level is min(max_left, max_right) – height. First pass (left to right): compute max_height_from_left at each position. Second pass (right to left): compute max_height_from_right. Water at i = min(left_max[i], right_max[i]) – height[i]. O(N) time, O(N) space (or O(1) with two pointers). Candy Distribution: each child gets at least 1 candy. Higher-rated children get more than neighbors. First pass (left to right): if rating[i] > rating[i-1], candy[i] = candy[i-1] + 1. Second pass (right to left): if rating[i] > rating[i+1], candy[i] = max(candy[i], candy[i+1] + 1). Two-pass ensures both left and right neighbor constraints are satisfied.
Pattern 3: String Encoding and Transformation
String encoding problems require careful index management: String Compression: replace consecutive duplicates with the character and count. “aabcccccaaa” -> “a2b1c5a3”. Use a read pointer and write pointer. Count consecutive characters, write the character and its count (as characters) at the write pointer. If the compressed string is not shorter, return the original. Decode String: “3[a2[c]]” -> “accaccacc”. Use a stack: push characters until “]”. Pop until “[” to get the inner string. Pop the number before “[“. Repeat the string that many times and push back. Group Anagrams: sort each string (or compute a frequency signature) as a hash key. Group strings with the same key. Time: O(N * K log K) with sorting, O(N * K) with frequency counting. Longest Common Prefix: compare characters column by column across all strings. Stop at the first mismatch. Time: O(S) where S is the total characters across all strings. Zigzag Conversion: distribute characters across rows in a zigzag pattern. Use an array of strings (one per row), iterate through the input placing characters in the correct row.
Pattern 4: Matrix Operations
Matrix problems require careful index mapping: Rotate Image 90 degrees clockwise (in-place): transpose the matrix (swap matrix[i][j] with matrix[j][i]), then reverse each row. O(N^2) time, O(1) space. Counter-clockwise: reverse each row first, then transpose. Or: transpose then reverse each column. Spiral Order: traverse the matrix in spiral order. Maintain four boundaries (top, bottom, left, right). Traverse: left-to-right (top row), top-to-bottom (right column), right-to-left (bottom row), bottom-to-top (left column). After each traversal, shrink the boundary. Stop when boundaries cross. Set Matrix Zeroes: if matrix[i][j] == 0, set entire row i and column j to zero. Naive: O(MN) extra space. Optimized: use the first row and first column as markers. First pass: for each zero, mark matrix[i][0] = 0 and matrix[0][j] = 0. Second pass: set cells to zero based on markers. Handle the first row and column separately (they were used as markers). O(1) extra space. Search a 2D Matrix: if rows are sorted and each row starts after the previous row ends, treat as a 1D sorted array and binary search. If rows and columns are independently sorted, start from top-right corner and eliminate a row or column each step: O(M+N).
Pattern 5: Interval Problems
Interval problems use sorting + linear scan: Merge Intervals: sort by start time. Iterate: if current overlaps previous (current.start <= prev.end), merge by extending prev.end = max(prev.end, current.end). Else start new merged interval. Time: O(N log N). Insert Interval: find the insertion position, merge with any overlapping intervals. Three phases: add all intervals that end before the new interval starts, merge all overlapping intervals with the new interval, add all intervals that start after the new interval ends. Non-Overlapping Intervals (minimum removals): sort by end time. Greedily select the earliest-ending interval. Count intervals that conflict with the selected one (remove them). Answer: total – selected. Interval List Intersections: two sorted lists of intervals. Two pointers, one per list. At each step: the intersection is [max(starts), min(ends)] if max(starts) <= min(ends). Advance the pointer with the earlier end. Meeting Rooms: sort by start. If any interval overlaps the previous, cannot attend all meetings. For minimum rooms: use a min-heap of end times (Meeting Rooms II).
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How do you modify an array in-place without extra space?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Four techniques for O(1) space array modification: (1) Swap-based — Dutch National Flag (sort 0/1/2): three pointers swap elements to correct regions. O(N). (2) Overwrite from front — Remove Duplicates: write pointer advances only on new values. Read pointer scans ahead. Return write pointer as new length. (3) Overwrite from back — Merge Sorted Array: when merging into a buffer with trailing space, fill from the back to avoid overwriting unprocessed elements. (4) Cyclic replacement — Rotate Array by K: move each element to (i+K)%N, following the displacement chain until returning to start. Key decision: scan front-to-back when building a result from the beginning. Scan back-to-front when the buffer overlaps with the source. Use swaps when partitioning elements into regions.”}},{“@type”:”Question”,”name”:”When should you use a two-pass technique for array problems?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use two passes when the answer at each position depends on information from BOTH directions. Product Except Self: result[i] = left_product * right_product. Pass 1 (left to right): compute prefix products. Pass 2 (right to left): multiply by suffix products. O(N) time, O(1) extra space. Trapping Rain Water: water at i = min(max_left, max_right) – height[i]. Pass 1: compute max_height_from_left. Pass 2: compute max_height_from_right. Candy Distribution: Pass 1 (left to right): satisfy left-neighbor constraint. Pass 2 (right to left): satisfy right-neighbor constraint. Take max of both passes. The pattern: whenever you need information from both sides of each element, compute left-to-right in pass 1 and right-to-left in pass 2. Most two-pass solutions are O(N) time.”}},{“@type”:”Question”,”name”:”How do you rotate a matrix 90 degrees in-place?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Rotate 90 degrees clockwise: two steps. (1) Transpose the matrix: swap matrix[i][j] with matrix[j][i] for all i < j. This mirrors across the main diagonal. (2) Reverse each row. The combination of transpose + row reversal equals a 90-degree clockwise rotation. O(N^2) time, O(1) space. For counter-clockwise: reverse each row first, then transpose. Or: transpose then reverse each column. Set Matrix Zeroes (O(1) space): use the first row and first column as markers. Pass 1: for each zero at (i,j), set matrix[i][0]=0 and matrix[0][j]=0. Pass 2: zero out cells based on markers. Handle first row/column separately since they were used as markers. Spiral Order: maintain four boundaries (top, bottom, left, right). Traverse each edge, shrink the boundary, repeat until boundaries cross."}},{"@type":"Question","name":"What interval problem patterns appear most in coding interviews?","acceptedAnswer":{"@type":"Answer","text":"Five core interval patterns: (1) Merge Intervals: sort by start, merge overlapping (current.start extend prev.end). O(N log N). (2) Insert Interval: add intervals before overlap, merge overlapping, add intervals after. (3) Non-Overlapping Intervals (minimum removals): sort by end time, greedily select earliest-ending. Answer = total – selected. (4) Meeting Rooms II (minimum rooms): min-heap of end times. Reuse room if meeting starts after earliest end. Heap size = rooms. (5) Interval List Intersections: two pointers on two sorted lists. Intersection = [max(starts), min(ends)] if valid. Advance pointer with earlier end. All interval problems start with sorting (by start or end time depending on the problem). After sorting, a single pass with greedy logic solves most variants.”}}]}