23. Median of Two Sorted Arrays

Q: Why binary search on the shorter array specifically?

Binary searching the shorter array of length m gives O(log m) time. Since m ≤ n, this is O(log(min(m,n))). Searching the longer array would be O(log(max(m,n))) — potentially much worse.

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

It biases the left half to be the larger half when the total length is even. This allows the same partition logic to handle both odd and even total lengths uniformly — the median comes from the max of the left halves.

hardAsked at PayPal

Find the median of two sorted arrays in O(log(min(m,n))) time without merging them. PayPal asks this hard binary-search problem to identify engineers who can handle statistical aggregations over large financial data streams where merging is prohibitively expensive.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in PayPal loops.

Glassdoor (2025)— PayPal SWE L5 reported median-of-two-arrays as the hard problem in their system-focused onsite round
LeetCode Discuss (2026)— Thread confirming PayPal uses binary search on sorted arrays in senior engineering interviews

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 must be O(log(m+n)).

Constraints

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-1000000 <= nums1[i], nums2[i] <= 1000000

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

Merge both sorted arrays using the two-pointer merge step, then return the middle element(s).

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) {
    merged.push(nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++]);
  }
  while (i < nums1.length) merged.push(nums1[i++]);
  while (j < nums2.length) merged.push(nums2[j++]);
  const n = merged.length;
  return n % 2 === 1 ? merged[Math.floor(n/2)] : (merged[n/2-1] + merged[n/2]) / 2;
}

Tradeoff: O(m+n) time and space — does not meet the O(log(m+n)) requirement. Present this first to confirm you understand what the median is, then optimize.

2. Binary search on partition

Binary search on the shorter array to find a partition point such that the left half of both arrays combined contains exactly (m+n)/2 elements and every element on the left is ≤ every element on the right. The median is derived from the boundary elements of this partition.

Time: O(log(min(m,n)))
Space: O(1)

function findMedianSortedArrays(nums1, nums2) {
  // Ensure nums1 is the shorter 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);  // partition in nums1
    const partY = Math.floor((m + n + 1) / 2) - partX; // partition in nums2

    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 === 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: The key insight: a valid partition is one where maxLeft ≤ minRight across both arrays. At PayPal, describe this as finding the balance point in two separate sorted ledgers without loading both into memory.

PayPal-specific tips

PayPal interviews focus on payment processing, fraud detection logic, financial reconciliation algorithms, and distributed transaction design. Hash maps, sliding windows, and two-pointer techniques appear frequently.

Common mistakes

Not ensuring nums1 is the shorter array — binary searching on the longer array increases log factor unnecessarily
Forgetting the +1 in `(m+n+1)/2` which handles even-length combined arrays in the odd-half calculation
Missing the -Infinity / +Infinity sentinels for edge partitions (partX = 0 or partX = m)

Follow-up questions

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

Find the kth smallest element across two sorted arrays without merging
Find the median of k sorted arrays — when does the binary-search approach still apply?
Given two sorted streams (not random access), find the running median as elements arrive

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

Binary searching the shorter array of length m gives O(log m) time. Since m ≤ n, this is O(log(min(m,n))). Searching the longer array would be O(log(max(m,n))) — potentially much worse.

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

It biases the left half to be the larger half when the total length is even. This allows the same partition logic to handle both odd and even total lengths uniformly — the median comes from the max of the left halves.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →