What is the brute force approach and complexity for Median of Two Sorted Arrays?

Merge both arrays into a new sorted array and read the middle with time complexity O(m + n) and space complexity O(m + n).

What is the optimal approach and complexity for Median of Two Sorted Arrays?

Binary search how many values the left half takes from the smaller array; check the 4 border values with optimal time complexity O(log(min(m, n))) and space complexity O(1).

Median of Two Sorted Arrays

Q: How do you identify the pattern for Median of Two Sorted Arrays?

Look for key signals in the prompt: "two sorted arrays" indicates The smaller half is always a front part of each array → described by one cut per array.; "median" indicates Only the border between the smaller half and the bigger half matters.; "O(log(m + n))" indicates Linear walking is too slow → binary search something.; "left half size is fixed" indicates Choosing the cut in one array forces the cut in the other: j = half − i..

Hard·LeetCode #4 Pro OnlyTricky / Edge Case

LeetCode

Problem Statement

You are given two sorted arrays, nums1 (size m) and nums2 (size n). Imagine putting all m + n numbers together in sorted order. Return the median of that combined list:

If the total count is odd, the median is the single middle number.
If it is even, the median is the average of the two middle numbers (this can be a .5 value).

The expected time is O(log(m + n)). One of the arrays may be empty.

Input

Two integer arrays nums1 and nums2, each sorted in non-decreasing order.

Output

A double: the median of all the numbers from both arrays.

Example 1

Input: nums1 = [1,3], nums2 = [2]

Output: 2.00000

All numbers together: [1, 2, 3]. Three numbers, so the middle one, 2, is the median.

Example 2

Input: nums1 = [1,2], nums2 = [3,4]

Output: 2.50000

All numbers together: [1, 2, 3, 4]. Four numbers, so the median is (2 + 3) / 2 = 2.5.

Constraints

• 0 ≤ m, n ≤ 1000
• 1 ≤ m + n ≤ 2000
• −10^6 ≤ nums1[i], nums2[i] ≤ 10^6
• Both arrays are sorted in non-decreasing order (duplicates allowed).

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“two sorted arrays”

→ The smaller half is always a front part of each array → described by one cut per array.

“median”

→ Only the border between the smaller half and the bigger half matters.

“O(log(m + n))”

→ Linear walking is too slow → binary search something.

“left half size is fixed”

→ Choosing the cut in one array forces the cut in the other: j = half − i.

Approach Complexity Ladder

Brute Force — merge everything, take the middleO(m + n)O(m + n)

Merge both arrays into a new sorted array and read the middle

Better — merge walk to the middle onlyO(m + n)O(1)

Same two-pointer merge, but stop at the middle and keep only the last two values

Optimal — binary search the cut in the smaller arrayO(log(min(m, n)))O(1)

Binary search how many values the left half takes from the smaller array; check the 4 border values

Brute Force Intuition

Merge the two sorted arrays like in merge sort (two pointers, always take the smaller front value). Then the median is all[total / 2] when total is odd, or the average of all[total/2 − 1] and all[total/2] when it is even.

Recognition rule for this sub-pattern:

Search a sorted matrix as one flat array, or binary search on where to cut two sorted arrays.

Remember this · Binary Search

Trigger

Sorted data, "minimum X such that…", "maximum X such that…", rotated arrays, answers that are monotonic (if X works, X+1 also works).

Think

Is there a yes/no question whose answers look like NNNNYYYY? Then binary search for the first Y.

Key question

What is my check function, and is it monotonic?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Binary Search translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Order Book Price Level Matching

std::lower_bound lookup in sorted price ticks for limit orders.

Explore Track

C++ Internals

CPU Branch Prediction & Cache Efficiency

Branch mispredictions in binary search and branchless mid-point arithmetic.

Explore Track

Search a 2D Matrix II