Divide and Conquer Interview Questions
Last updated 2026-11-19
Divide and conquer splits a problem into smaller independent pieces, solves each recursively and combines the results. Merge sort, quickselect, fast exponentiation and the closest pair of points all follow it. The skill interviewers test is spotting the combine step and proving the total cost, usually with a recurrence.
This page works through eleven problems, from merge sort to closest pair, with Python and Java code, complexity and edge cases. The recursion fundamentals are in recursion interview questions. Counting problems built on the same merge idea can also be solved with a Fenwick tree, and interval versions are in interval DP interview questions.
| Three steps | Divide, conquer, combine |
|---|---|
| Typical recurrence | T(n) = 2T(n/2) + O(n), giving O(n log n) |
| Examples | Merge sort, quickselect, closest pair |
| Versus DP | Subproblems do not overlap |
The pattern and when to spot it
Divide and conquer fits when a problem can be cut into independent subproblems of the same kind, and combining their answers is cheaper than solving the whole directly. Halving the input is the usual cut. Signals include the words sorted, median, count pairs across a split, nearest, and tasks where a crossing case exists between two halves, such as the maximum subarray that straddles the middle.
Analyse cost with the recurrence T(n) = a T(n / b) + f(n). Two halves with a linear merge give O(n log n). One half with a linear partition, as in quickselect, gives O(n) on average because the sizes shrink geometrically. When subproblems overlap, as in the parenthesisation problem, add memoisation and it becomes dynamic programming. Counting pairs between two sorted halves before merging is the powerful trick behind inversions and reverse pairs.
Common mistakes
- Merging before counting cross pairs, which destroys the order you need for the count.
- Using int mid = (lo + hi) / 2 where lo + hi can overflow, instead of lo + (hi - lo) / 2 or an unsigned shift.
- Off-by-one errors between inclusive and half-open ranges.
- Choosing a fixed pivot in quickselect, which gives O(n^2) on sorted input.
- Forgetting a base case for empty ranges.
Divide and Conquer Interview Questions: questions with worked answers
1 Merge sort
easySplit the array in half, sort each half recursively and merge the two sorted halves with two pointers. The merge step is where the work happens, and taking from the left half when values tie keeps the sort stable. The recursion has log n levels each doing O(n) work. Time O(n log n) in every case, space O(n) for the merge buffer. Edge cases: empty or one-element arrays (return as they are), many duplicates, already sorted input, using <= in the merge for stability.
pythondef merge_sort(a): if len(a) <= 1: return a mid = len(a) // 2 l, r = merge_sort(a[:mid]), merge_sort(a[mid:]) out, i, j = [], 0, 0 while i < len(l) and j < len(r): if l[i] <= r[j]: out.append(l[i]); i += 1 else: out.append(r[j]); j += 1 return out + l[i:] + r[j:]javavoid mergeSort(int[] a, int lo, int hi, int[] tmp) { // sorts a[lo..hi) if (hi - lo <= 1) return; int mid = (lo + hi) >>> 1; mergeSort(a, lo, mid, tmp); mergeSort(a, mid, hi, tmp); int i = lo, j = mid, k = lo; while (i < mid && j < hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++]; while (i < mid) tmp[k++] = a[i++]; while (j < hi) tmp[k++] = a[j++]; System.arraycopy(tmp, lo, a, lo, hi - lo); }2 Fast exponentiation: compute x to the power n
easyUse x^n = (x^(n/2))^2 when n is even, and x * x^(n-1) when odd. This halves the exponent each step, so only O(log n) multiplications are needed. Handle a negative exponent by inverting x and negating n; use a wider type for n because negating the minimum int overflows. Time O(log n), space O(log n) recursive, O(1) iterative. Edge cases: n equal to 0 (1), negative n, x equal to 0 with negative n (division by zero), n equal to the minimum integer value.
pythondef my_pow(x, n): if n < 0: x, n = 1 / x, -n result = 1.0 while n: if n & 1: result *= x x *= x n >>= 1 return resultjavadouble myPow(double x, int n) { long e = n; if (e < 0) { x = 1 / x; e = -e; } double result = 1.0; while (e > 0) { if ((e & 1) == 1) result *= x; x *= x; e >>= 1; } return result; }3 Majority element by divide and conquer
easyThe majority element of a range must be the majority of at least one half. Find the majority of each half recursively; if they agree, that is the answer, otherwise count each candidate over the whole range and choose the one with more occurrences. The Boyer-Moore voting method does it in O(1) space, but this shows the divide and conquer structure. Time O(n log n), space O(log n). Edge cases: a single element, a guaranteed majority (more than n/2 occurrences) so the result always exists, ties between candidates resolved by counting.
pythondef majority(nums): def rec(lo, hi): if lo == hi: return nums[lo] mid = (lo + hi) // 2 a, b = rec(lo, mid), rec(mid + 1, hi) if a == b: return a ca = sum(1 for i in range(lo, hi + 1) if nums[i] == a) cb = sum(1 for i in range(lo, hi + 1) if nums[i] == b) return a if ca > cb else b return rec(0, len(nums) - 1)javaint majority(int[] nums) { return rec(nums, 0, nums.length - 1); } private int rec(int[] a, int lo, int hi) { if (lo == hi) return a[lo]; int mid = (lo + hi) >>> 1; int x = rec(a, lo, mid), y = rec(a, mid + 1, hi); if (x == y) return x; int cx = 0, cy = 0; for (int i = lo; i <= hi; i++) { if (a[i] == x) cx++; else if (a[i] == y) cy++; } return cx > cy ? x : y; }4 Quickselect: kth largest element
mediumPartition around a random pivot so smaller values are on the left and larger ones on the right, then recurse into only the side that contains the target index n - k. This discards about half of the data each time, giving O(n) on average. A random pivot avoids the O(n^2) worst case on sorted input. Time O(n) average, O(n^2) worst case, space O(1) iterative. Edge cases: k equal to 1 or n, duplicates (Lomuto handles them but can slow on many equals), already sorted input, k out of range.
pythonimport random def kth_largest(nums, k): target = len(nums) - k lo, hi = 0, len(nums) - 1 while True: p = random.randint(lo, hi) nums[p], nums[hi] = nums[hi], nums[p] pivot, store = nums[hi], lo for i in range(lo, hi): if nums[i] < pivot: nums[i], nums[store] = nums[store], nums[i] store += 1 nums[store], nums[hi] = nums[hi], nums[store] if store == target: return nums[store] if store < target: lo = store + 1 else: hi = store - 1javaint kthLargest(int[] nums, int k) { int target = nums.length - k, lo = 0, hi = nums.length - 1; Random rnd = new Random(); while (true) { int p = lo + rnd.nextInt(hi - lo + 1); int t = nums[p]; nums[p] = nums[hi]; nums[hi] = t; int pivot = nums[hi], store = lo; for (int i = lo; i < hi; i++) if (nums[i] < pivot) { t = nums[i]; nums[i] = nums[store]; nums[store] = t; store++; } t = nums[store]; nums[store] = nums[hi]; nums[hi] = t; if (store == target) return nums[store]; if (store < target) lo = store + 1; else hi = store - 1; } }5 Count inversions with merge sort
mediumWhile merging two sorted halves, whenever the right element is smaller than the current left element, it is smaller than all remaining left elements too. Add the number of remaining left elements to the inversion count. Cross-half inversions are counted at the merge, and in-half ones recursively. Time O(n log n), space O(n). Edge cases: duplicates are not inversions (merge on <=), sorted input (0), reverse sorted (n(n-1)/2, so use long).
pythondef count_inversions(a): def sort(lo, hi): # sorts a[lo:hi], returns inversions if hi - lo <= 1: return 0 mid = (lo + hi) // 2 inv = sort(lo, mid) + sort(mid, hi) l, r, out = a[lo:mid], a[mid:hi], [] i = j = 0 while i < len(l) and j < len(r): if l[i] <= r[j]: out.append(l[i]); i += 1 else: out.append(r[j]); j += 1 inv += len(l) - i out += l[i:] + r[j:] a[lo:hi] = out return inv return sort(0, len(a))javalong countInversions(int[] a) { return sort(a, 0, a.length, new int[a.length]); } private long sort(int[] a, int lo, int hi, int[] tmp) { if (hi - lo <= 1) return 0; int mid = (lo + hi) >>> 1; long inv = sort(a, lo, mid, tmp) + sort(a, mid, hi, tmp); int i = lo, j = mid, k = lo; while (i < mid && j < hi) { if (a[i] <= a[j]) tmp[k++] = a[i++]; else { tmp[k++] = a[j++]; inv += mid - i; } } while (i < mid) tmp[k++] = a[i++]; while (j < hi) tmp[k++] = a[j++]; System.arraycopy(tmp, lo, a, lo, hi - lo); return inv; }6 Maximum subarray sum by divide and conquer
mediumThe best subarray lies entirely in the left half, entirely in the right half, or crosses the middle. The crossing case is the best suffix sum ending at the middle of the left half plus the best prefix sum starting right after it in the right half. Take the maximum of the three. Kadane gives O(n), but this is the classic divide and conquer example. Time O(n log n), space O(log n). Edge cases: all negative numbers (the least negative single element), a single element, the crossing sum needing at least one element on each side.
pythondef max_subarray(nums): def rec(lo, hi): if lo == hi: return nums[lo] mid = (lo + hi) // 2 left_best = float('-inf'); s = 0 for i in range(mid, lo - 1, -1): s += nums[i]; left_best = max(left_best, s) right_best = float('-inf'); s = 0 for i in range(mid + 1, hi + 1): s += nums[i]; right_best = max(right_best, s) return max(rec(lo, mid), rec(mid + 1, hi), left_best + right_best) return rec(0, len(nums) - 1)javaint maxSubarray(int[] nums) { return rec(nums, 0, nums.length - 1); } private int rec(int[] a, int lo, int hi) { if (lo == hi) return a[lo]; int mid = (lo + hi) >>> 1; int lb = Integer.MIN_VALUE, s = 0; for (int i = mid; i >= lo; i--) { s += a[i]; lb = Math.max(lb, s); } int rb = Integer.MIN_VALUE; s = 0; for (int i = mid + 1; i <= hi; i++) { s += a[i]; rb = Math.max(rb, s); } return Math.max(Math.max(rec(a, lo, mid), rec(a, mid + 1, hi)), lb + rb); }7 Merge k sorted lists by pairwise merging
mediumMerging the lists one after another costs O(k * N). Instead merge them in pairs, halving the number of lists each round. There are log k rounds, each touching every node once, so the total is O(N log k), matching the heap solution without a priority queue. Time O(N log k) for N total nodes, space O(log k) recursion. Edge cases: empty input (null), null lists in the array, a single list, k not a power of two (the middle split handles it).
pythondef merge_k(lists): def merge2(a, b): dummy = tail = ListNode(0) while a and b: if a.val <= b.val: tail.next, a = a, a.next else: tail.next, b = b, b.next tail = tail.next tail.next = a or b return dummy.next def rec(lo, hi): if lo > hi: return None if lo == hi: return lists[lo] mid = (lo + hi) // 2 return merge2(rec(lo, mid), rec(mid + 1, hi)) return rec(0, len(lists) - 1)javaListNode mergeK(ListNode[] lists) { return rec(lists, 0, lists.length - 1); } private ListNode rec(ListNode[] lists, int lo, int hi) { if (lo > hi) return null; if (lo == hi) return lists[lo]; int mid = (lo + hi) >>> 1; return merge2(rec(lists, lo, mid), rec(lists, mid + 1, hi)); } private ListNode merge2(ListNode a, ListNode b) { ListNode dummy = new ListNode(0), tail = dummy; while (a != null && b != null) { if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; } tail = tail.next; } tail.next = a != null ? a : b; return dummy.next; }8 Different ways to add parentheses to an expression
mediumSplit the expression at each operator. Compute all results for the left part and for the right part recursively, then combine every left value with every right value using that operator. A string with no operator is a number. Memoising on the substring avoids recomputation for long inputs. Time Catalan-number many results, exponential in the number of operators, space O(results) plus recursion. Edge cases: a single number (one result), duplicate results appear as separate entries because different groupings count, multi-digit numbers (split only at operators), subtraction ordering.
pythonfrom functools import lru_cache def diff_ways(expr): @lru_cache(None) def ways(s): res = [] for i, c in enumerate(s): if c in '+-*': for a in ways(s[:i]): for b in ways(s[i + 1:]): res.append(a + b if c == '+' else a - b if c == '-' else a * b) return tuple(res) if res else (int(s),) return list(ways(expr))javaMap<String, List<Integer>> memo = new HashMap<>(); List<Integer> diffWays(String s) { if (memo.containsKey(s)) return memo.get(s); List<Integer> res = new ArrayList<>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c == '+' || c == '-' || c == '*') { for (int a : diffWays(s.substring(0, i))) for (int b : diffWays(s.substring(i + 1))) res.add(c == '+' ? a + b : c == '-' ? a - b : a * b); } } if (res.isEmpty()) res.add(Integer.parseInt(s)); memo.put(s, res); return res; }9 Median of two sorted arrays in O(log(min(m, n)))
hardBinary search for a partition of the shorter array so that the left parts of both arrays together contain half of all elements and every left element is at most every right element. The median comes from the boundary values around that partition. Use infinities for empty sides so comparisons stay valid. Time O(log(min(m, n))), space O(1). Edge cases: one array empty, different lengths (search the shorter one), odd versus even total count, duplicates, partition at the very ends.
pythondef find_median(a, b): if len(a) > len(b): a, b = b, a m, n = len(a), len(b) lo, hi, half = 0, m, (m + n + 1) // 2 while lo <= hi: i = (lo + hi) // 2 j = half - i a_left = a[i - 1] if i > 0 else float('-inf') a_right = a[i] if i < m else float('inf') b_left = b[j - 1] if j > 0 else float('-inf') b_right = b[j] if j < n else float('inf') if a_left <= b_right and b_left <= a_right: if (m + n) % 2: return float(max(a_left, b_left)) return (max(a_left, b_left) + min(a_right, b_right)) / 2 if a_left > b_right: hi = i - 1 else: lo = i + 1javadouble findMedian(int[] a, int[] b) { if (a.length > b.length) { int[] t = a; a = b; b = t; } int m = a.length, n = b.length, lo = 0, hi = m, half = (m + n + 1) / 2; while (lo <= hi) { int i = (lo + hi) >>> 1, j = half - i; double al = i > 0 ? a[i - 1] : Double.NEGATIVE_INFINITY; double ar = i < m ? a[i] : Double.POSITIVE_INFINITY; double bl = j > 0 ? b[j - 1] : Double.NEGATIVE_INFINITY; double br = j < n ? b[j] : Double.POSITIVE_INFINITY; if (al <= br && bl <= ar) { if ((m + n) % 2 == 1) return Math.max(al, bl); return (Math.max(al, bl) + Math.min(ar, br)) / 2.0; } if (al > br) hi = i - 1; else lo = i + 1; } return 0.0; }10 Reverse pairs with merge sort: count i < j where a[i] > 2 * a[j]
hardUse the merge sort inversion idea with a stricter condition. After sorting both halves, count cross pairs with a two-pointer sweep: for each left element, advance a right pointer while left > 2 * right. Then do the ordinary merge. Counting before merging is essential, since merging destroys the relation between the halves. Use long to avoid overflow when doubling. Time O(n log n), space O(n). Edge cases: doubling overflow (cast to long), duplicates, negative numbers (the condition still holds with strict inequality), single element.
pythondef reverse_pairs(a): def sort(lo, hi): if hi - lo <= 1: return 0 mid = (lo + hi) // 2 cnt = sort(lo, mid) + sort(mid, hi) j = mid for i in range(lo, mid): while j < hi and a[i] > 2 * a[j]: j += 1 cnt += j - mid a[lo:hi] = sorted(a[lo:mid] + a[mid:hi]) return cnt return sort(0, len(a))javaint reversePairs(int[] a) { return sort(a, 0, a.length, new int[a.length]); } private int sort(int[] a, int lo, int hi, int[] tmp) { if (hi - lo <= 1) return 0; int mid = (lo + hi) >>> 1; int cnt = sort(a, lo, mid, tmp) + sort(a, mid, hi, tmp); int j = mid; for (int i = lo; i < mid; i++) { while (j < hi && (long) a[i] > 2L * a[j]) j++; cnt += j - mid; } int i = lo, k = lo; j = mid; while (i < mid && j < hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++]; while (i < mid) tmp[k++] = a[i++]; while (j < hi) tmp[k++] = a[j++]; System.arraycopy(tmp, lo, a, lo, hi - lo); return cnt; }11 Closest pair of points in the plane
hardSort the points by x and split at the median. Find the smallest distance d among pairs entirely in each half. A closer pair could straddle the dividing line, so collect points within d of the line, sort them by y, and compare each with the next few (at most seven) points in that order, since a d by 2d box holds a bounded number of points. Return the minimum. Time O(n log^2 n) with sorting the strip each time, O(n log n) with merging, space O(n). Edge cases: fewer than two points, duplicate points (distance 0), all points on a vertical line, ties in x, using squared distance to avoid square roots.
pythonfrom math import dist, inf def closest_pair(points): pts = sorted(points) def rec(lo, hi): if hi - lo <= 3: return min((dist(pts[i], pts[j]) for i in range(lo, hi) for j in range(i + 1, hi)), default=inf) mid = (lo + hi) // 2 midx = pts[mid][0] d = min(rec(lo, mid), rec(mid, hi)) strip = sorted((p for p in pts[lo:hi] if abs(p[0] - midx) < d), key=lambda p: p[1]) for i in range(len(strip)): for j in range(i + 1, len(strip)): if strip[j][1] - strip[i][1] >= d: break d = min(d, dist(strip[i], strip[j])) return d return rec(0, len(pts))javadouble closestPair(double[][] points) { double[][] pts = points.clone(); Arrays.sort(pts, (a, b) -> Double.compare(a[0], b[0])); return rec(pts, 0, pts.length); } private double rec(double[][] p, int lo, int hi) { if (hi - lo <= 3) { double d = Double.POSITIVE_INFINITY; for (int i = lo; i < hi; i++) for (int j = i + 1; j < hi; j++) d = Math.min(d, Math.hypot(p[i][0] - p[j][0], p[i][1] - p[j][1])); return d; } int mid = (lo + hi) >>> 1; double midx = p[mid][0]; double d = Math.min(rec(p, lo, mid), rec(p, mid, hi)); List<double[]> strip = new ArrayList<>(); for (int i = lo; i < hi; i++) if (Math.abs(p[i][0] - midx) < d) strip.add(p[i]); strip.sort((a, b) -> Double.compare(a[1], b[1])); for (int i = 0; i < strip.size(); i++) for (int j = i + 1; j < strip.size() && strip.get(j)[1] - strip.get(i)[1] < d; j++) d = Math.min(d, Math.hypot(strip.get(i)[0] - strip.get(j)[0], strip.get(i)[1] - strip.get(j)[1])); return d; }
Frequently asked questions
What is the difference between divide and conquer and dynamic programming?
Divide and conquer splits into independent subproblems that are solved once. Dynamic programming handles overlapping subproblems and stores results to avoid recomputation.
How do I find the complexity of a divide and conquer algorithm?
Write the recurrence T(n) = a T(n/b) + f(n) and apply the master theorem or draw the recursion tree. Two halves with linear merge cost give O(n log n).
Why is quickselect O(n) on average?
Each round does linear work and keeps, on average, a constant fraction of the data, so the total is n + n/2 + n/4 and so on, which sums to about 2n.
Do interviews ask divide and conquer directly?
Merge sort, quickselect and inversion counting are common. See the DSA coding round guide for how to prepare across topics.
Related guides
More in DSA Interview Questions
- Dynamic Programming Interview Questions
- Edit Distance and String DP Interview Questions
- Fast and slow pointers interview questions with solutions
- Fenwick Tree (Binary Indexed Tree) Interview Questions
- Graph Interview Questions and Answers
- Greedy algorithm interview questions with worked solutions
- Grid and Matrix DP Interview Questions
- Hashing interview questions with worked solutions
- Heap and Priority Queue Interview Questions
- Interval DP Interview Questions
- Interval interview questions with worked solutions
- Kadane algorithm interview questions with worked solutions