Sorting and Searching Problems — Interview Guide with Solutions
In this tutorial, you'll learn about Sorting and Searching Problems. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
Sorting and searching form the backbone of algorithm interviews. Most problems require sorting as a preprocessing step or use binary search as the optimal solution. Master these patterns to unlock hundreds of LeetCode problems.
Learning Path
flowchart LR A["DP Problems"] --> B["Sorting & Searching
You are here"] B --> C["Heap, Stack & Queue"] C --> D["System Design Prep"] style B fill:#f90,color:#fff,stroke-width:2px
QuickSort
Quicksort is a divide-and-conquer algorithm that selects a pivot and partitions the array around it.
def quicksort(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
pivot = partition(arr, low, high)
quicksort(arr, low, pivot - 1)
quicksort(arr, pivot + 1, high)
return arr
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
print(quicksort([3, 6, 8, 10, 1, 2, 1]))
[1, 1, 2, 3, 6, 8, 10]
import java.util.Arrays;
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {3, 6, 8, 10, 1, 2, 1};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
[1, 1, 2, 3, 6, 8, 10]
#include <vector>
#include <iostream>
using namespace std;
int partition(vector<int>& arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quicksort(vector<int>& arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quicksort(arr, low, pivot - 1);
quicksort(arr, pivot + 1, high);
}
}
int main() {
vector<int> arr = {3, 6, 8, 10, 1, 2, 1};
quicksort(arr, 0, arr.size() - 1);
for (int v : arr) cout << v << " ";
return 0;
}
1 1 2 3 6 8 10
Binary Search Variants
Binary search is not just for finding a target. It solves boundary-finding problems like first/last occurrence and peak element.
def binary_search_bounds(nums, target):
def first_occurrence():
left, right = 0, len(nums) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
result = mid
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
def last_occurrence():
left, right = 0, len(nums) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
result = mid
left = mid + 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
return [first_occurrence(), last_occurrence()]
print(binary_search_bounds([1, 2, 3, 3, 3, 4, 5], 3))
print(binary_search_bounds([1, 2, 3, 4, 5], 6))
[2, 4]
[-1, -1]
Search in Rotated Sorted Array
A sorted array rotated at an unknown pivot requires modified binary search that determines which half is sorted.
def search_rotated(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))
4
-1
public class RotatedSearch {
public static int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else {
if (target > nums[mid] && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] nums = {4, 5, 6, 7, 0, 1, 2};
System.out.println(search(nums, 0));
System.out.println(search(nums, 3));
}
}
4
-1
Merge Sort
Merge sort divides the array, recursively sorts halves, then merges them. It is stable and guarantees O(n log n).
def mergesort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = mergesort(arr[:mid])
right = mergesort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
print(mergesort([38, 27, 43, 3, 9, 82, 10]))
[3, 9, 10, 27, 38, 43, 82]
Common Mistakes
- Binary search off-by-one errors -- Use
left <= rightfor standard search,left < rightfor boundary search. Test with single-element and two-element arrays. - Quicksort worst-case O(n^2) -- Choosing the last element as pivot on already-sorted arrays causes O(n^2). Use random pivot or median-of-three.
- Merge sort extra space -- Merge sort requires O(n) auxiliary space. For in-place sorting, use heapsort or quicksort with O(log n) stack space.
- Mutation during sorting -- Sorting in place changes original array order. Copy the array if the original order must be preserved.
- Wrong comparison function -- For descending order or custom objects, provide the correct comparator. In Python, use
keyorfunctools.cmp_to_key. - Stability assumptions -- Quicksort is not stable. Use mergesort when stable sorting is required (e.g., sorting by multiple keys).
- Integer overflow in mid calculation --
(left + right) // 2can overflow in languages with fixed-width integers. Useleft + (right - left) // 2.
Practice Questions
1. Find the k-th largest element in an unsorted array.
Use QuickSelect (partition-based selection) for O(n) average time, or a min-heap of size k for O(n log k).
2. Search in a nearly sorted array where each element may be misplaced by up to k positions.
Modify binary search to check mid, mid-k, and mid+k. Adapt the search range to account for displacement.
3. Challenge: Count of Smaller Numbers After Self (Leetcode 315)
For each element, count how many elements to its right are smaller. Use merge sort and count during the merge phase.
FAQ
Related Tutorials
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro. Updated 2026-06-23.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro