pattern / MEDIUM
Divide and conquer on sorted data
complexity
time
O(log n)
space
O(1)
02' — visual
interactive
Maximum sum subarray
03'
mental
model.
Maintain a search space [low, high]. At each step, check the middle. Based on the condition, eliminate half the search space.
Binary Search finds a target in a sorted array in O(log n) time by repeatedly dividing the search interval in half. The pattern extends far beyond simple search.
when to use ✓
when not ✗
04'
Sorted array or rotated sorted array
Find minimum/maximum satisfying condition
Monotonic function or property
Search space can be split in half
05'
1# Beginner: Fixed-size sliding window2def max_sum_k(nums, k):3 n = len(nums)4 if n < k:5 return 06 window_sum = sum(nums[:k])7 max_sum = window_sum8 for i in range(k, n):9 window_sum += nums[i] - nums[i - k]10 max_sum = max(max_sum, window_sum)11 return max_sum
common mistakes
interview tips
06'
10 curated problems from LeetCode
07'