Skip to main content

81. Median of Two Sorted Arrays

hardAsked at Salesforce

Find the median of two sorted arrays in O(log(min(m, n))). Salesforce uses this as a stretch question to gauge advanced binary-search mastery.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses this in their data-cloud's percentile query optimizer.
  • Blind (2025)— Salesforce L5/L6 stretch question.

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

Example 2

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

Approaches

1. Merge and pick median

Merge both arrays; pick middle element(s).

Time
O(m+n)
Space
O(m+n)
function findMedianSortedArrays(nums1, nums2) {
  const merged = [...nums1, ...nums2].sort((a, b) => a - b);
  const m = merged.length;
  return m % 2 ? merged[(m-1)/2] : (merged[m/2 - 1] + merged[m/2]) / 2;
}

Tradeoff: Violates O(log) requirement.

2. Binary search partition

Binary search the partition of the SHORTER array. At each partition, check four boundary conditions: maxLeftA <= minRightB AND maxLeftB <= minRightA.

Time
O(log(min(m,n)))
Space
O(1)
function findMedianSortedArrays(A, B) {
  if (A.length > B.length) [A, B] = [B, A];
  const m = A.length, n = B.length, half = (m + n + 1) >> 1;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = (lo + hi) >> 1;
    const j = half - i;
    const maxLeftA = i === 0 ? -Infinity : A[i - 1];
    const minRightA = i === m ? Infinity : A[i];
    const maxLeftB = j === 0 ? -Infinity : B[j - 1];
    const minRightB = j === n ? Infinity : B[j];
    if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
      if ((m + n) % 2) return Math.max(maxLeftA, maxLeftB);
      return (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2;
    } else if (maxLeftA > minRightB) hi = i - 1;
    else lo = i + 1;
  }
}

Tradeoff: O(log min(m,n)). The partition trick is notoriously tricky — Salesforce wants to see preparation.

Salesforce-specific tips

Salesforce uses this in their data-cloud's percentile query optimizer (median is the 50th percentile). They flag this as a 'preparation matters' problem — almost nobody solves it cold. Bonus signal: walk through the four boundary conditions explicitly before coding.

Common mistakes

  • Searching the longer array — swap to search the shorter one for O(log min(m,n)).
  • Forgetting the sentinel values (-Infinity, Infinity) at array boundaries.
  • Using (lo + hi) / 2 instead of >> 1 — JS does fine but be explicit.

Follow-up questions

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

  • Median of a stream (LC 295).
  • Find K-th element in two sorted arrays.
  • What if there are 3+ sorted arrays?

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 the shorter array?

To minimize the binary-search range. The longer array's partition is then derived from the shorter's.

What's the invariant of the partition?

Combined left half has (m+n+1)/2 elements. Within each array's partition, left side <= right side. The partition is valid iff maxLeftA <= minRightB AND maxLeftB <= minRightA.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →