Skip to main content

4. Median of Two Sorted Arrays

hardAsked at Cohere

Find the median of two sorted arrays in O(log(m+n)) time. Cohere asks this hard problem because binary search on partition boundaries is the same mathematical discipline applied to efficient percentile estimation in model evaluation pipelines.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Cohere loops.

  • Glassdoor (2025-Q3)— Reported in Cohere senior SWE onsite threads as a hard problem used to test binary search mastery.
  • Blind (2025-08)— Cohere candidates at senior level mention this as a stretch problem for L5+ positions.

Problem

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Constraints

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -10^6 <= nums1[i], nums2[i] <= 10^6

Examples

Example 1

Input
nums1 = [1,3], nums2 = [2]
Output
2.0

Explanation: Merged array [1,2,3], median is 2.

Example 2

Input
nums1 = [1,2], nums2 = [3,4]
Output
2.5

Explanation: Merged array [1,2,3,4], median is (2+3)/2 = 2.5.

Approaches

1. Merge then find median (O(m+n))

Merge both arrays in sorted order using the two-pointer technique, then return the median element(s). Does not meet the O(log(m+n)) requirement but demonstrates understanding of the problem.

Time
O(m + n)
Space
O(m + n)
function findMedianSortedArrays(nums1, nums2) {
  const merged = [];
  let i = 0, j = 0;
  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] <= nums2[j]) merged.push(nums1[i++]);
    else merged.push(nums2[j++]);
  }
  while (i < nums1.length) merged.push(nums1[i++]);
  while (j < nums2.length) merged.push(nums2[j++]);
  const mid = Math.floor(merged.length / 2);
  return merged.length % 2 === 0
    ? (merged[mid - 1] + merged[mid]) / 2
    : merged[mid];
}

Tradeoff: Clear and correct but O(m+n) — only acceptable as a stepping stone before the binary search solution.

2. Binary search on partition (O(log(min(m,n))))

Binary search on the shorter array to find a partition point such that the left halves of both arrays form the combined left half. The median is determined by the max of the left halves and min of the right halves.

Time
O(log(min(m,n)))
Space
O(1)
function findMedianSortedArrays(nums1, nums2) {
  if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
  const m = nums1.length, n = nums2.length;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const partX = Math.floor((lo + hi) / 2);
    const partY = Math.floor((m + n + 1) / 2) - partX;
    const maxLeftX  = partX === 0 ? -Infinity : nums1[partX - 1];
    const minRightX = partX === m ?  Infinity : nums1[partX];
    const maxLeftY  = partY === 0 ? -Infinity : nums2[partY - 1];
    const minRightY = partY === n ?  Infinity : nums2[partY];
    if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
      // Correct partition
      if ((m + n) % 2 === 1) return Math.max(maxLeftX, maxLeftY);
      return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
    } else if (maxLeftX > minRightY) {
      hi = partX - 1; // move partition left in nums1
    } else {
      lo = partX + 1; // move partition right in nums1
    }
  }
}

Tradeoff: O(log(min(m,n))) time, O(1) space — the required solution. Subtle but elegant: the key insight is that the correct partition satisfies two cross-conditions on four boundary values.

Cohere-specific tips

This is one of the hardest problems Cohere may ask at senior level. Start with the O(m+n) merge approach and explicitly say: 'This doesn't meet the O(log(m+n)) requirement — let me think about binary search on the partition boundary.' Then articulate the invariant before writing code: 'I want to find a partition of both arrays such that all left elements are ≤ all right elements, and the left half has exactly (m+n+1)/2 elements.' Walking through the invariant verbally is more important than bug-free code on the first attempt.

Common mistakes

  • Not ensuring nums1 is the shorter array — binary search on the shorter array keeps the implementation correct and avoids partY going negative.
  • Forgetting to handle edge partitions with -Infinity and Infinity sentinels — when a partition is at 0 or the full length, there are no elements on that side.
  • Off-by-one in the total-half calculation — use (m+n+1)/2 (floor) to correctly handle both odd and even total lengths.
  • Trying to implement this without first stating the partition invariant — the code is hard to write correctly without a clear mental model.

Follow-up questions

An interviewer at Cohere may pivot to one of these next:

  • Kth Smallest Element in Two Sorted Arrays — generalise to an arbitrary quantile.
  • Find the Kth Smallest Pair Distance — binary search on the answer space.
  • How would you compute streaming percentiles over a large model evaluation result set?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why binary search on the smaller array?

The partition of the smaller array uniquely determines the partition of the larger array. Searching the smaller array bounds the number of iterations to O(log(min(m,n))) and ensures partY stays non-negative.

What does the +1 in (m+n+1)/2 do?

It biases the left half to be larger when (m+n) is odd, so the median is the max of the left elements — avoiding a separate even/odd branch for the left-half case.

Can you do O(log(m+n)) without O(1) space?

The merge approach is O(m+n) time and space. The binary search approach achieves O(log(min(m,n))) ≤ O(log(m+n)) time with O(1) space — it satisfies the problem requirement.

Practice these live with InterviewChamp.AI

Drill Median of Two Sorted Arrays and other Cohere interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →