Master array sorting techniques, binary search fundamentals, and parametric search. Learn to leverage sorting as preprocessing for optimization, implement efficient binary search variants, and solve problems that depend on pre-sorted data structures.
Sorting and binary search are foundational techniques that unlock efficient solutions. Sorting rearranges data to enable preprocessing-based optimizations, while binary search reduces search space logarithmically.
The System.Array.Sort() method uses TimSort (hybrid of merge sort + insertion sort). Custom sorting is achieved via IComparer<T> implementations or inline comparator functions. Key points:
A robust binary search follows this pattern:
int BinarySearch(int[] arr, int target) { int left = 0, right = arr.Length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; // Not found }
When the problem asks "find the minimum/maximum value such that a condition holds," use binary search on the answer range:
int BinarySearchOnAnswer(int[] nums, int constraint) { int left = 0, right = 1000000; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (CanAchieve(nums, mid, constraint)) { result = mid; left = mid + 1; // Try larger } else { right = mid - 1; // Try smaller } } return result; }
Many optimization techniques rely on sorted input:
Given an array A of N integers, return the number of distinct values. For example: A = [1, 3, 2, 2, 1] should return 3.
public int solution(int[] A) { if (A.Length == 0) return 0; // Sort array O(n log n) Array.Sort(A); int distinctCount = 1; // At least one element // Scan and count transitions for (int i = 1; i < A.Length; i++) { if (A[i] != A[i - 1]) { distinctCount++; } } return distinctCount; }
Input: A = [1, 3, 2, 2, 1]
Given N integers, find the maximum product of any three elements. Elements can be negative. Example: A = [1, 2, 3] → 6 (2×3×1). A = [-5, -2, 3, 4] → 60 (−5×−2×4).
After sorting, the maximum product of three comes from either:
Compare both and return the maximum.
public int solution(int[] A) { Array.Sort(A); int n = A.Length; // Option 1: Three largest values int prod1 = A[n - 1] * A[n - 2] * A[n - 3]; // Option 2: Two smallest (negative) × largest int prod2 = A[0] * A[1] * A[n - 1]; return Math.Max(prod1, prod2); }
Input: A = [-5, -2, 3, 4]
Given N integers representing lengths, determine if any three can form a valid triangle. Triangle inequality: sum of any two sides must be greater than the third. Return 1 if valid, 0 otherwise.
After sorting, for a triangle with sides a ≤ b ≤ c, we only need to check a + b > c (the other inequalities are automatically satisfied). Iterate through sorted array checking consecutive triplets.
public int solution(int[] A) { if (A.Length < 3) return 0; Array.Sort(A); // Check consecutive triplets for (int i = 0; i < A.Length - 2; i++) { // A[i] ≤ A[i+1] ≤ A[i+2], so only check smallest + middle > largest if ((long)A[i] + A[i + 1] > A[i + 2]) { return 1; // Valid triangle found } } return 0; // No valid triangle }
Input: A = [10, 2, 5, 1, 8, 20]
Cast to long when adding to prevent integer overflow with large values.
N discs at positions A[i] with radii A[i]. Count the number of disc pairs that intersect. Discs intersect if distance between centers ≤ sum of radii.
Convert each disc to an interval [center - radius, center + radius]. Count overlapping interval pairs using a sweep-line algorithm with a counter for active intervals.
public int solution(int[] A) { int n = A.Length; int maxIntersections = 0; // Event: (position, type) type: 0=start, 1=end var events = new List<(long, int)>(); for (int i = 0; i < n; i++) { long start = i - (A[i]); // disc left boundary long end = i + (A[i]); // disc right boundary events.Add((start, 0)); // start event events.Add((end + 1, 1)); // end event (exclusive) } events.Sort(); int activeDiscs = 0; long intersections = 0; foreach (var (pos, type) in events) { if (type == 0) { // Start of disc: it intersects with all active discs intersections += activeDiscs; activeDiscs++; } else { // End of disc activeDiscs--; } } return intersections > 10000000 ? -1 : (int)intersections; }
Input: A = [0, 1, 0] (3 discs at positions 0,1,2 with radii 0,1,0)
An array A is rotated at some pivot. Example: [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]. Find target in O(log n) time. Return index or -1.
Binary search: at each step, determine which half is sorted, then check if target lies in that sorted range.
public 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; // Determine which half is sorted if (nums[left] <= nums[mid]) { // Left half is sorted if (target >= nums[left] && target < nums[mid]) { right = mid - 1; // Target in left half } else { left = mid + 1; // Search right } } else { // Right half is sorted if (target > nums[mid] && target <= nums[right]) { left = mid + 1; // Target in right half } else { right = mid - 1; // Search left } } } return -1; }
Input: nums = [4,5,6,7,0,1,2], target = 0
Given sorted array A and integer target, find [first_index, last_index] of target. Return [-1, -1] if not found. Example: [5,7,7,8,8,10], target=8 → [3, 4].
Two binary searches: one to find the leftmost position, another for the rightmost.
public int[] SearchRange(int[] nums, int target) { var result = new int[] { -1, -1 }; if (nums.Length == 0) return result; // Find leftmost position result[0] = FindFirst(nums, target); // Find rightmost position result[1] = FindLast(nums, target); return result; } private int FindFirst(int[] nums, int target) { int left = 0, right = nums.Length - 1, result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { result = mid; right = mid - 1; // Keep searching left } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; } private int FindLast(int[] nums, int target) { int left = 0, right = nums.Length - 1, result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { result = mid; left = mid + 1; // Keep searching right } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return result; }
An m×n matrix where each row is sorted left-to-right and top-to-bottom (rows are sorted). Find target in O(log(m×n)). Example: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 → false.
Treat the 2D matrix as a flattened 1D sorted array. Use binary search with index-to-coordinate conversion.
public bool SearchMatrix(int[][] matrix, int target) { int rows = matrix.Length, cols = matrix[0].Length; int left = 0, right = rows * cols - 1; while (left <= right) { int mid = left + (right - left) / 2; // Convert flat index to 2D coordinates int row = mid / cols; int col = mid % cols; int midVal = matrix[row][col]; if (midVal == target) return true; else if (midVal < target) left = mid + 1; else right = mid - 1; } return false; }
Given array A and integer k, find the kth largest distinct element. Example: [3,2,1,5,6,4], k=2 → 5.
QuickSelect is a divide-and-conquer algorithm (similar to QuickSort) that selects the kth element in O(n) average time. At each step, partition the array and recursively search the partition containing the kth element.
public int FindKthLargest(int[] nums, int k) { return QuickSelect(nums, 0, nums.Length - 1, nums.Length - k); } private int QuickSelect(int[] nums, int left, int right, int kIndex) { if (left == right) return nums[left]; // Partition and get pivot index int pivotIndex = Partition(nums, left, right); if (kIndex == pivotIndex) { return nums[kIndex]; } else if (kIndex < pivotIndex) { return QuickSelect(nums, left, pivotIndex - 1, kIndex); } else { return QuickSelect(nums, pivotIndex + 1, right, kIndex); } } private int Partition(int[] nums, int left, int right) { int pivot = nums[right]; int i = left; for (int j = left; j < right; j++) { if (nums[j] < pivot) { // Swap int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; i++; } } // Place pivot in correct position int temp2 = nums[i]; nums[i] = nums[right]; nums[right] = temp2; return i; }
Sort in descending order and return the element at index k-1. Time: O(n log n), Space: O(1).
Given array of intervals, merge overlapping ones. Example: [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]].
Sort intervals by start position. Iterate through sorted intervals; if current overlaps with last merged, extend the end. Otherwise, add a new merged interval.
public int[][] Merge(int[][] intervals) { var result = new List<int[]>(); // Sort by start position Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0])); int currentStart = intervals[0][0]; int currentEnd = intervals[0][1]; for (int i = 1; i < intervals.Length; i++) { if (intervals[i][0] <= currentEnd) { // Overlapping, extend end currentEnd = Math.Max(currentEnd, intervals[i][1]); } else { // Non-overlapping, add previous interval result.Add(new int[] { currentStart, currentEnd }); currentStart = intervals[i][0]; currentEnd = intervals[i][1]; } } // Add last interval result.Add(new int[] { currentStart, currentEnd }); return result.ToArray(); }
Input: [[1,3],[2,6],[8,10],[15,18]]
Given array of meetings [start, end), find the minimum number of meeting rooms required. Example: [[0,30],[5,10],[15,20]] → 2 rooms (meetings at [0,30] and [5,10] overlap).
Sort meetings by start time. Use a min-heap to track end times of ongoing meetings. When a new meeting starts, if the earliest ending meeting has finished, reuse that room; otherwise, allocate a new room.
public int MinMeetingRooms(int[][] intervals) { if (intervals.Length == 0) return 0; // Sort by start time Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0])); // Min-heap of end times var minHeap = new PriorityQueue<int, int>(); minHeap.Enqueue(intervals[0][1], intervals[0][1]); for (int i = 1; i < intervals.Length; i++) { // If earliest ending meeting is done, reuse room if (minHeap.Peek() <= intervals[i][0]) { minHeap.Dequeue(); } // Add current meeting's end time minHeap.Enqueue(intervals[i][1], intervals[i][1]); } return minHeap.Count; }
Input: [[0,30],[5,10],[15,20]]
An array where nums[i] ≠ nums[i+1] and nums[-1] = nums[n] = -∞. Find any peak index. Example: [1,2,1,3,5,6,4] → 1 or 5.
Binary search: if nums[mid] < nums[mid+1], move right (a peak must exist). Else move left. This guarantees finding a peak in O(log n).
public int FindPeakElement(int[] nums) { int left = 0, right = nums.Length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < nums[mid + 1]) { // Peak is on the right side left = mid + 1; } else { // Peak is on the left side (including mid) right = mid; } } return left; }
If nums[mid] < nums[mid+1], a peak must exist to the right (including mid+1) because either the array keeps increasing (peak at end) or it decreases, creating a peak. Similarly for the left side.
A sorted array is rotated at unknown pivot. Find the minimum element. Example: [3,4,5,1,2] → 1.
Binary search: compare nums[mid] with nums[right]. If mid < right, search left. Else search right.
public int FindMin(int[] nums) { int left = 0, right = nums.Length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < nums[right]) { // Minimum is in left half (including mid) right = mid; } else { // Minimum is in right half left = mid + 1; } } return nums[left]; }
Input: [3,4,5,1,2]
Given two sorted arrays nums1 and nums2 of sizes m and n, find their median in O(log(min(m,n))). Example: nums1=[1,3], nums2=[2] → 2.0.
Binary search on the smaller array to find a partition where left half and right half are balanced. For median, the largest element on the left must be ≤ the smallest on the right.
public double FindMedianSortedArrays(int[] nums1, int[] nums2) { if (nums1.Length > nums2.Length) { return FindMedianSortedArrays(nums2, nums1); // Ensure nums1 is smaller } int m = nums1.Length, n = nums2.Length; int left = 0, right = m; int cut1, cut2; while (left <= right) { cut1 = left + (right - left) / 2; cut2 = (m + n + 1) / 2 - cut1; // Balanced partition int left1 = (cut1 == 0) ? int.MinValue : nums1[cut1 - 1]; int right1 = (cut1 == m) ? int.MaxValue : nums1[cut1]; int left2 = (cut2 == 0) ? int.MinValue : nums2[cut2 - 1]; int right2 = (cut2 == n) ? int.MaxValue : nums2[cut2]; if (left1 <= right2 && left2 <= right1) { // Valid partition found if ((m + n) % 2 == 0) { return (Math.Max(left1, left2) + Math.Min(right1, right2)) / 2.0; } else { return Math.Max(left1, left2); } } else if (left1 > right2) { right = cut1 - 1; } else { left = cut1 + 1; } } return -1; }
Divide array into K non-empty, contiguous blocks. Minimize the maximum sum of any single block. Example: A=[2,1,5,1,2,2,2], K=3 → partition as [2,1], [5], [1,2,2,2] with max sum 5.
Binary search on the answer: the maximum sum ranges from [max(A), sum(A)]. For each candidate max, check if we can partition into K blocks without exceeding it using greedy scanning.
public int solution(int K, int[] A) { long left = A[0], right = 0; for (int i = 0; i < A.Length; i++) { left = Math.Max(left, A[i]); // At least the max element right += A[i]; // At most the sum of all } while (left < right) { long mid = left + (right - left) / 2; if (CanPartition(A, K, mid)) { right = mid; } else { left = mid + 1; } } return (int)left; } private bool CanPartition(int[] A, int K, long maxSum) { int blocks = 1; long currentSum = 0; for (int i = 0; i < A.Length; i++) { if (currentSum + A[i] <= maxSum) { currentSum += A[i]; } else { // Start a new block blocks++; currentSum = A[i]; if (blocks > K) return false; // Too many blocks } } return true; }
Input: A=[2,1,5,1,2,2,2], K=3
Note: The greedy approach partitions greedily left-to-right, so the actual answer depends on the search result.
N planks at positions [A[i], B[i]], M nails at positions C[j]. Each nail covers one plank if within its range. Find minimum nails (prefix) to cover all planks. Return -1 if impossible.
Binary search on the number of nails used (0 to M). For each candidate count, check if those nails cover all planks greedily. Use binary search within the check to find the nearest nail.
public int solution(int[] A, int[] B, int[] C) { Array.Sort(C); // Sort nails int left = 0, right = C.Length; int answer = -1; while (left <= right) { int mid = left + (right - left) / 2; if (CanCoverAll(A, B, C, mid)) { answer = mid; right = mid - 1; // Try fewer nails } else { left = mid + 1; // Need more nails } } return answer; } private bool CanCoverAll(int[] A, int[] B, int[] C, int nailCount) { int nailIdx = 0; for (int i = 0; i < A.Length; i++) { // Find first nail that covers plank [A[i], B[i]] while (nailIdx < nailCount && C[nailIdx] < A[i]) { nailIdx++; } // Check if found nail is within plank range if (nailIdx >= nailCount || C[nailIdx] > B[i]) { return false; // Plank not covered } // Move to next nail (might cover next plank too) nailIdx++; } return true; }
Once we decide on a nail count, greedily cover planks left-to-right. For each plank, use the first nail that covers it; this leaves flexibility for later planks.
Input: A=[1,4,5], B=[2,5,9], C=[4,6,7,10]
Corrected: Plank [1,2] has no nail in range [1,2], so it's impossible → return -1.