Skip to main content

4. Median of Two Sorted Arrays

hardAsked at HubSpot

HubSpot includes Median of Two Sorted Arrays to assess whether candidates can binary search on a partition index rather than on array values — a conceptual leap that separates strong algorithmic thinkers from those who rely on rote solutions.

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

Source citations

Public interview reports confirming this problem appears in HubSpot loops.

  • Glassdoor (2026-Q1)— HubSpot SWE senior-level interview reports include Median of Two Sorted Arrays as an advanced binary search hard problem.
  • Levels.fyi (2025-11)— Listed in HubSpot staff+ interview reports as a problem testing deep binary search understanding.

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.00000

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

Example 2

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

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

Approaches

1. Brute force merge

Merge both sorted arrays into one sorted array in O(m+n) time, then find the median directly. Simple but doesn't meet the O(log(m+n)) requirement.

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: Correct and easy to explain, but O(m+n) — doesn't satisfy the O(log(m+n)) constraint. State this upfront and pivot to binary search on partition.

2. Binary search on partition

Binary search on the partition index of the smaller array. Find a cut in each array such that all elements on the left of both cuts are smaller than all elements on the right, and the total left side has exactly half the combined elements.

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 cut1 = Math.floor((lo + hi) / 2);
    const cut2 = Math.floor((m + n + 1) / 2) - cut1;
    const maxLeft1 = cut1 === 0 ? -Infinity : nums1[cut1 - 1];
    const minRight1 = cut1 === m ? Infinity : nums1[cut1];
    const maxLeft2 = cut2 === 0 ? -Infinity : nums2[cut2 - 1];
    const minRight2 = cut2 === n ? Infinity : nums2[cut2];
    if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
      const maxLeft = Math.max(maxLeft1, maxLeft2);
      if ((m + n) % 2 === 1) return maxLeft;
      return (maxLeft + Math.min(minRight1, minRight2)) / 2;
    } else if (maxLeft1 > minRight2) {
      hi = cut1 - 1;
    } else {
      lo = cut1 + 1;
    }
  }
}

Tradeoff: O(log(min(m,n))) — optimal. Binary searching on the smaller array's partition index ensures convergence. The -Infinity/Infinity sentinels handle edge cases where one side of the cut is empty. This requires careful explanation; walk through a worked example.

HubSpot-specific tips

Lead with the brute force to show you know it, then explicitly say: 'The constraint says O(log(m+n)), so I need to binary search. The key insight is binary searching on the partition index, not the value.' HubSpot interviewers for senior roles expect you to code the binary-search approach with full correctness. Walk through nums1=[1,3], nums2=[2] on paper. Always ensure you binary search on the smaller array to keep complexity at O(log(min(m,n))).

Common mistakes

  • Binary searching on values instead of partition indices — loses the structural advantage of sorted arrays.
  • Not swapping to always binary search on the smaller array — O(log(max(m,n))) instead of O(log(min(m,n))).
  • Off-by-one in cut2 = (m+n+1)/2 - cut1 — the +1 ensures the left half is at least as large for odd total lengths.
  • Using 0 and -1 as sentinels for empty sides instead of -Infinity/Infinity — causes incorrect comparisons.

Follow-up questions

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

  • Find the Kth Smallest Element in Two Sorted Arrays — generalization of this exact binary-search-on-partition approach.
  • How would you extend this to find the median of k sorted arrays?
  • What if the arrays are not fully in memory — how would you adapt for a streaming / disk-based scenario?

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 partition and not on value?

The partition encodes how many elements go to each side — it has the right monotonic structure for binary search. Value-based binary search doesn't have a clean monotone predicate over two unsorted-relative arrays.

Why +1 in (m+n+1)/2?

This ensures the left half always has at least as many elements as the right half for odd total lengths. It makes the median the maximum of the left halves regardless of parity.

Why always binary search on the smaller array?

cut2 = (m+n+1)/2 - cut1 must be non-negative. If nums1 is smaller (m <= n), cut1 ranges from 0 to m and cut2 is always within [0, n]. Swapping ensures this invariant.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →