DSA: Arrays Advanced Operations
Master classic array algorithms including Kadane's, two-pointer, sliding window, prefix sums, and more.
Array Basics Review
Arrays store elements in contiguous memory locations, giving O(1) index access. Understanding their memory layout is the foundation for every advanced technique on this page.
Static vs Dynamic Arrays
Static arrays have a fixed size set at creation; dynamic arrays (std::vector) grow automatically by reallocating memory.
- Static array: size fixed at declaration, O(1) access, no resize overhead
- std::vector: grows on demand, amortized O(1) push_back
- Both give O(1) random access by index
- Insertion or deletion in the middle costs O(n) because elements must shift
Static vs Dynamic Array Behavior
C++insert is O(n) because it shifts elements; push_back is O(1) amortized.
Multi-dimensional Arrays
A 2D array models grids, matrices, and tables. Accessing element at row i, column j is O(1).
2D Arrays in C++
Declare as int matrix[rows][cols] or use vector of vectors. Iterating all cells is O(rows × cols).
- Static: int matrix[3][3]
- Dynamic: vector<vector<int>> matrix(rows, vector<int>(cols, 0))
- Access: matrix[row][col]
- Full traversal: O(n²) for an n×n matrix
2D Array Traversal
C++Nested loops visit every cell exactly once, giving O(rows × cols) time.
Kadane's Algorithm: Maximum Subarray Sum
Kadane's algorithm finds the contiguous subarray with the largest sum in O(n) time by making one greedy decision at each step: extend the current subarray or start fresh.
Kadane's Algorithm
At each position, decide whether to extend the running sum or restart from the current element.
- Track two values: current sum and global maximum
- At each element: currentSum = max(element, currentSum + element)
- globalMax = max(globalMax, currentSum)
- Time: O(n), Space: O(1), handles negative numbers correctly
Kadane's Algorithm
C++One pass, O(n) time. The subarray [4, -1, 2, 1] gives the maximum sum of 6.
Two-Pointer Technique
Two pointers start at opposite ends of a sorted array and move toward each other based on a condition. This reduces many O(n²) brute-force searches to O(n).
Two-Pointer Pattern
Use two pointers on a sorted array to find pairs, triplets, or subarrays satisfying a condition.
- Requires a sorted array (or sorted order invariant)
- left pointer starts at index 0, right pointer starts at the last index
- If sum too small: move left pointer right; if sum too large: move right pointer left
- Time: O(n) after sorting, Space: O(1)
Two-Pointer: Pair with Target Sum
C++Sorted array lets us move pointers intelligently instead of checking every pair.
Sliding Window Technique
The sliding window technique maintains a running result for a fixed-size or variable-size window as it moves across the array, avoiding full recomputation at each step.
Sliding Window Pattern
Slide a window across the array: add the incoming element and remove the outgoing element each step.
- Fixed window: add arr[i], subtract arr[i - k] at each step
- Variable window: expand right pointer, shrink left pointer based on a constraint
- Reduces O(n×k) brute force to O(n)
- Common uses: max sum of k elements, longest substring without repeats
Sliding Window: Max Sum of k Elements
C++Each slide adds one element and removes one, keeping the window sum current in O(1) per step.
Prefix Sum Arrays
A prefix sum array lets you answer range sum queries in O(1) after an O(n) build step, instead of summing each range from scratch in O(n).
Prefix Sum
prefix[i] stores the sum of all elements from index 0 to i-1. Range sum from l to r is prefix[r+1] - prefix[l].
- Build time: O(n), Space: O(n)
- Each range query answered in O(1)
- Ideal when the array is static but many range queries are needed
- Difference array is the inverse technique for range updates
Prefix Sum: O(1) Range Queries
C++Build the prefix array once in O(n), then answer any range query in O(1).
Difference Array Technique
The difference array makes range update operations O(1) instead of O(n), at the cost of a single O(n) reconstruction at the end.
Difference Array
Store incremental differences so that a range update becomes two point updates.
- To add value v to range [l, r]: diff[l] += v, diff[r+1] -= v
- Reconstruct the updated array with one prefix sum pass
- Ideal for batch range-update problems (e.g. multiple booking events)
- Build time: O(n), Each update: O(1), Reconstruct: O(n)
Difference Array: O(1) Range Updates
C++Two point writes per range update, then one O(n) pass to reconstruct the result.
Array Rotation Algorithms
Rotating an array by k positions can be done in O(n) time and O(1) space using the three-reversal trick.
Three-Reversal Rotation
To rotate right by k: reverse the whole array, then reverse the first k elements, then reverse the rest.
- Right rotation by k: reverse(0, n-1), reverse(0, k-1), reverse(k, n-1)
- Left rotation by k is the same as right rotation by n - k
- Time: O(n), Space: O(1)
- Each element is moved exactly twice across the three reversals
Right Rotation by k (Three Reversal)
C++O(n) time, O(1) space. Three in-place reversals achieve the rotation.
Dutch National Flag Problem
The Dutch National Flag problem sorts an array of three distinct values (0, 1, 2) in a single O(n) pass with O(1) space, using three pointers.
Three-Way Partition
Maintain three regions: low (0s), mid (1s), high (2s) and expand them inward with pointer swaps.
- low pointer: everything before it is 0
- mid pointer: current element under inspection
- high pointer: everything after it is 2
- When arr[mid] = 0: swap with low, advance both; = 2: swap with high, retreat high only
Dutch National Flag
C++One pass with three pointers sorts 0s, 1s, and 2s in place without extra memory.
Majority Element: Boyer-Moore Voting
The Boyer-Moore algorithm finds the element that appears more than n/2 times in O(n) time and O(1) space by maintaining a candidate and a running vote count.
Boyer-Moore Majority Vote
Each pair of different elements cancels out. The last surviving candidate is the majority element.
- Maintain a candidate and a count starting at 0
- count = 0: set candidate to current element, count = 1
- Current element matches candidate: count++; else count--
- Works only when a majority element is guaranteed to exist
Boyer-Moore Majority Vote
C++O(n) time, O(1) space. Non-majority elements cancel out majority votes, but majority always survives.
Knowledge Check
1. What is the time complexity of Kadane's Algorithm?
2. The two-pointer technique works best when the array is:
3. What does the sliding window technique avoid compared to brute force?
4. Given a prefix sum array P, what is the sum of elements from index l to r (inclusive)?
5. The Dutch National Flag problem sorts an array containing how many distinct values?
6. Boyer-Moore Majority Vote algorithm finds the majority element in:
7. Rotating an array of n elements right by k is equivalent to rotating it left by:
8. What is the space complexity of the prefix sum array technique?