4. Median of Two Sorted Arrays
Median of Two Sorted Arrays (LeetCode 4) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the Median and Kth of Two Sorted Arrays subpattern.
How to solve Median of Two Sorted Arrays
Median of Two Sorted Arrays is a Median of Two Sorted Arrays problem, part of Binary Search Patterns. Master the binary search approach to find median of two sorted arrays in O(log(min(m,n))) time.
Work towards the solution in these steps:
- Think about how binary search can help find the median without merging the two arrays entirely.
- Consider partitioning the arrays such that the left parts and right parts relate to the median position.
- Focus on maintaining the condition that all elements on the left partitions are less than or equal to those on the right.
The reference solution runs in O(log(min(m, n))) time and O(1) space.
The Median of Two Sorted Arrays solution and editorial walks through the full approach with reference code.
Problem statement
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)).
Example 1:
Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Constraints:
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -106 <= nums1[i], nums2[i] <= 106
Topics and companies
Topics: Array, Binary Search, Divide and Conquer.
Reported in interviews at Amazon, Goldman Sachs, Facebook, Microsoft, Apple, Adobe, Google, Bloomberg, Zillow, Uber, Flipkart, Paypal.
How to practise Median of Two Sorted Arrays on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(log(min(m, n))) time and O(1) space.
Open Median of Two Sorted Arrays in the code editor, or read the Median of Two Sorted Arrays editorial for a worked solution with its approach and complexity analysis.
Where Median of Two Sorted Arrays sits in the DSA pattern sheet
- Binary Search Patterns pattern guide
- Median and Kth of Two Sorted Arrays subpattern
- The full DSA patterns sheet
Problems related to Median of Two Sorted Arrays
Other problems that use the same Median and Kth of Two Sorted Arrays and Binary Search Patterns techniques:
- Find K-th Smallest Pair Distance — Hard, same subpattern
- Binary Search — Easy, same pattern
- Capacity To Ship Packages Within D Days — Medium, same pattern
- Find First and Last Position of Element in Sorted Array — Medium, same pattern
- Find in Mountain Array — Hard, same pattern
- Find K Closest Elements — Medium, same pattern
Median of Two Sorted Arrays FAQ
What is the LeetCode number of Median of Two Sorted Arrays?
Median of Two Sorted Arrays is LeetCode problem 4, rated Hard.
What pattern is used to solve Median of Two Sorted Arrays?
Median of Two Sorted Arrays is a Median of Two Sorted Arrays problem. It belongs to the Binary Search Patterns pattern, in the Median and Kth of Two Sorted Arrays subpattern.
What is the time complexity of Median of Two Sorted Arrays?
The reference solution runs in O(log(min(m, n))) time and O(1) space.
Which companies ask Median of Two Sorted Arrays?
Median of Two Sorted Arrays has been reported in interviews at Amazon, Goldman Sachs, Facebook, Microsoft, Apple, Adobe, Google, Bloomberg, Zillow, Uber, Flipkart, Paypal.