| Prefix Sum | Subarray queries |
|---|---|
| Sliding Window | Fixed/variable length subarray problems |
Once you're confident with the basics, move to the following array problem-solving patterns:
Use when array is sorted or you're checking pairs. O(n²) ā O(n)
if unsorted > first sort it > O(n²) ā O( n logn )
š Problems:
finding duplicates / palindrome / pair related - sub , difference of any pair
reverse of any particular section
merge two sorted
Pair with target sum
Remove duplicates
Reverse array
Sort colors (Dutch national flag)
š§ Pattern: Left and right pointer, move inward based on condition.
š§ Code Template:
int left = 0, right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) break;
else if (sum < target) left++;
else right--;
}