Skip to main content

4. Median of Two Sorted Arrays

hardAsked at HP

HP's quality assurance and performance benchmarking tools compute statistical medians over sorted measurement arrays from multiple test runs or device sources. Achieving O(log(m+n)) time rather than O(m+n) requires binary search across array boundaries — a technique HP senior engineers are expected to command.

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

Source citations

Public interview reports confirming this problem appears in HP loops.

  • Glassdoor (2025-Q4)— HP senior SWE onsite feedback cites Median of Two Sorted Arrays as a stretch hard problem in final interview rounds.
  • Blind (2025-11)— HP interview threads acknowledge this as a difficult binary-search problem occasionally asked for senior-level candidates.

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 = [1,2,3]; median = 2.

Example 2

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

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

Approaches

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

Merge both sorted arrays, then return the middle element. Simple but doesn't satisfy 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: O(m+n) time. Correct but suboptimal. Present this first to establish correctness, then tackle the O(log) solution.

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

Binary search on the smaller array to find the correct partition point that divides the combined array into equal halves. The median is determined by the maximum of the left halves and minimum of the right halves.

Time
O(log(min(m, n)))
Space
O(1)
function findMedianSortedArrays(nums1, nums2) {
  // Ensure nums1 is the smaller array
  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 found
      if ((m + n) % 2 === 0) {
        return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
      } else {
        return Math.max(maxLeftX, maxLeftY);
      }
    } else if (maxLeftX > minRightY) {
      hi = partX - 1; // move left in nums1
    } else {
      lo = partX + 1; // move right in nums1
    }
  }
}

Tradeoff: O(log(min(m,n))) time, O(1) space. The canonical optimal solution. The core insight: a valid partition means max(left halves) ≤ min(right halves). Binary search on nums1's partition until this is satisfied.

HP-specific tips

At HP, start by explaining the partition concept visually — draw a vertical dividing line through both arrays such that all elements on the left of both cuts are ≤ all elements on the right. Binary search finds the correct cut. Use -Infinity and Infinity as sentinel values for partition edges — they simplify boundary conditions cleanly. Make sure you swap so you always binary-search the smaller array.

Common mistakes

  • Binary-searching the larger array — always search the smaller for O(log(min(m,n))).
  • Computing partY incorrectly — partY = (m + n + 1) / 2 - partX; the +1 handles odd totals by placing the extra element in the left half.
  • Not using sentinels for partX=0 or partX=m — accessing nums1[-1] or nums1[m] would be out of bounds.
  • Returning the wrong value for even vs odd total length — check (m+n) % 2 explicitly.

Follow-up questions

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

  • Find the k-th smallest element in two sorted arrays — generalize the binary search.
  • What if the arrays are not sorted — how does the approach change?
  • How would you find the median of a stream of numbers using two heaps (LC 295)?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

What is the 'partition' concept?

Imagine drawing a vertical line through each array such that exactly (m+n)/2 elements are to the left of both lines combined. The median is determined by the largest left element and smallest right element at those cuts.

Why use (m + n + 1) / 2 for partY?

When m+n is odd, we want the extra element in the left half (to directly return its maximum as the median). Using +1 before dividing achieves this for both odd and even totals.

Why binary-search only nums1 and not nums2?

Once partX is chosen, partY is fully determined: partY = (m+n+1)/2 - partX. We only need to search one array; choosing the smaller ensures O(log(min(m,n))).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →