ARRAY PATTERN SHEET (C++) - DSA & Interview
1. Traversal & Basic Ops
Pattern: Print / Reverse / Update
Example:
for(int i=0; i<n; i++) cout << arr[i] << " ";
reverse(arr, arr+n); // STL
Problems: Reverse array, Find min/max, Sum of elements
2. Searching
Pattern: Linear Search / Binary Search
Example:
int l=0, r=n-1;
while(l<=r){
int mid = l+(r-l)/2;
if(arr[mid] == target) return mid;
else if(arr[mid] < target) l = mid+1;
else r = mid-1;
}
Problems: Search in sorted array, First/Last occurrence, Square root
3. Sorting
Pattern: Bubble / Selection / Merge / Quick
Example:
sort(arr, arr+n); // STL O(n log n)
Problems: Sort colors (0,1,2), Merge sorted arrays, Kth smallest element
4. Prefix / Suffix
Pattern: Precompute sums/min/max
Example:
prefix[0] = arr[0];
for(int i=1; i<n; i++) prefix[i] = prefix[i-1] + arr[i];
Problems: Range sum queries, Equilibrium index, Trapping rain water
5. Sliding Window
Pattern: Fixed / Variable size window
Example:
int sum=0, ans=0;
for(int i=0; i<k; i++) sum+=arr[i];
for(int i=k; i<n; i++){
sum += arr[i] - arr[i-k];
ans = max(ans, sum);
}
Problems: Max sum subarray size k, Longest substring without repeat
6. Two Pointers
Pattern: Left & Right index move
Example:
int l=0, r=n-1;
while(l<r){
if(arr[l]+arr[r] == target) {...}
else if(arr[l]+arr[r] < target) l++;
ARRAY PATTERN SHEET (C++) - DSA & Interview
else r--;
}
Problems: Pair sum, Move negatives left, Container with most water
7. Hashing / Frequency
Pattern: Use unordered_map or array freq
Example:
unordered_map<int,int> mp;
for(int x: arr) mp[x]++;
Problems: First repeating element, Subarray sum = k
8. Kadane's Algorithm
Pattern: Max subarray sum
Example:
int maxSoFar=arr[0], curr=arr[0];
for(int i=1; i<n; i++){
curr = max(arr[i], curr+arr[i]);
maxSoFar = max(maxSoFar, curr);
}
Problems: Max subarray sum, Max product subarray
9. Matrix (2D Array)
Pattern: Row/Col/Diagonal traversal
Example:
for(int i=0; i<rows; i++)
for(int j=0; j<cols; j++)
cout << mat[i][j] << " ";
Problems: Rotate matrix, Search in sorted matrix, Spiral print
10. Advanced FAANG Patterns
- Binary search on answer (Aggressive cows)
- Bit manipulation (Missing number using XOR)
- Search in rotated sorted array
- Median of two sorted arrays
