Comprehensive Guide for Solving Problems with Sorted Arrays in DSA

Photo by Kaleidico on Unsplash

cheat sheet to solve Sorted Array DSA problems

1. Binary Search

• Problem Type: Searching an element in a sorted array.
• Approach: Divide and conquer; narrow down the search range by comparing the middle element.
• Time Complexity: O(log n)

Steps:

1. Set low = 0, high = n - 1.
2. Calculate mid = low + (high - low) / 2.
3. If arr[mid] == target, return mid.
4. If arr[mid] > target, search the left half.
5. If arr[mid] < target, search the right half.

Key Use Cases:

• Search element in a sorted array.
• Finding the first/last occurrence of an element.

2. Two Pointers Approach

• Problem Type: Find pairs or triplets that satisfy a condition (e.g., sum, difference).
• Approach: Use two pointers, one starting from the beginning and one from the end, and adjust based on conditions.
• Time Complexity: O(n)

Steps:

1. Initialize two pointers i = 0 (start) and j = n - 1 (end).
2. Calculate sum = arr[i] + arr[j].
3. If sum == target, return the pair.
4. If sum > target, decrement j (move the right pointer left).
5. If sum < target, increment i (move the left pointer right).

Key Use Cases:

• Two Sum problem.
• Three Sum problem (with a nested loop for third element).
• Find if there are two numbers with a given difference.

3. Rotated Sorted Array

• Problem Type: Search in a rotated sorted array.
• Approach: A variation of binary search that accounts for the rotation.
• Time Complexity: O(log n)

Steps:

1. Perform binary search, but decide whether to search in the left or right half by checking which half is sorted.
2. If the left half is sorted, check if the target lies in that range.
3. Otherwise, search the right half.

Key Use Cases:

• Find the minimum element in a rotated sorted array.
• Search for a target in a rotated sorted array.

4. Find the Peak Element

• Problem Type: Find a local peak in a sorted or unsorted array.
• Approach: Use binary search to locate the peak element.
• Time Complexity: O(log n)

Steps:

1. If arr[mid] is greater than its neighbors, it's the peak.
2. If arr[mid] < arr[mid + 1], search the right half.
3. Else, search the left half.

Key Use Cases:

• Find peak in a mountain array.
• Local maxima in a strictly increasing or decreasing array.

5. Find First and Last Occurrence

• Problem Type: Find the first and last positions of a given element in a sorted array.
• Approach: Modify binary search to find the boundaries.
• Time Complexity: O(log n)

Steps:

1. To find the first occurrence, search while arr[mid] == target and mid == 0 or arr[mid - 1] != target.
2. To find the last occurrence, search while arr[mid] == target and mid == n - 1 or arr[mid + 1] != target.

6. Find Minimum or Maximum in a Rotated Sorted Array

• Problem Type: Find the minimum or maximum element in a rotated sorted array.
• Approach: Binary search for the point of inflection.
• Time Complexity: O(log n)

Steps:

1. If arr[low] <= arr[high], return arr[low] (already sorted).
2. Otherwise, find the smallest element in the unsorted part using binary search.

7. Merge Two Sorted Arrays

• Problem Type: Merging two sorted arrays into a single sorted array.
• Approach: Use two pointers to compare elements from both arrays.
• Time Complexity: O(n + m)

Steps:

1. Use two pointers i and j to compare elements from arr1 and arr2.
2. Insert the smaller element into the result array and move the pointer.
3. When one array is exhausted, add remaining elements from the other array.

8. Find the Intersection of Two Sorted Arrays

• Problem Type: Find common elements between two sorted arrays.
• Approach: Use two pointers, one for each array.
• Time Complexity: O(n + m)

Steps:

1. Initialize pointers i and j.
2. Compare arr1[i] and arr2[j].
3. If arr1[i] == arr2[j], add it to the result and increment both pointers.
4. If arr1[i] < arr2[j], increment i.
5. If arr1[i] > arr2[j], increment j.

9. Remove Duplicates in a Sorted Array

• Problem Type: Remove duplicates and return the new length.
• Approach: Use two pointers to overwrite duplicates.
• Time Complexity: O(n)

Steps:

1. Use two pointers i and j where i tracks the non-duplicate elements.
2. If arr[j] != arr[i], increment i and copy arr[j] to arr[i].
3. Return i + 1 as the new length.

10. Sliding Window for Fixed or Variable Size Problems

• Problem Type: Sum or product of subarrays in a sorted array.
• Approach: Use a sliding window to find sums or other operations efficiently.
• Time Complexity: O(n)

Steps:

1. Initialize a window with the first k elements.
2. Slide the window by removing the element going out of the window and adding the next element.
3. Track the sum (or product) for each window.

11. Median of Two Sorted Arrays

• Problem Type: Find the median of two sorted arrays.
• Approach: Use binary search on the smaller array to partition both arrays.
• Time Complexity: O(log(min(n, m)))

Steps:

1. Perform binary search to partition both arrays.
2. Ensure that the left half contains smaller elements than the right half.
3. Calculate the median based on partition indices.