 Register for our webinar

### How to Nail your next Technical Interview

1 hour 1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name  Step 1  Step 2
Congratulations!
You have registered for our webinar Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone  Step 1  Step 2 Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.  ## You may be missing out on a 66.5% salary hike* ### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.  ## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.  # Median Of Two Sorted Arrays Problem Statement

Given two sorted arrays `arr` and `brr` of size `n` and `m` respectively, find the median of the array obtained after merging arrays `arr` and `brr` (i.e. array of length `n + m`).

## Example

``````{
"arr": [1, 2],
"brr": [1, 4]
}
``````

Output:

``````1
``````

Here, `arr = [1, 2]`, `brr = [1, 4]`.\ Array after merging `arr` and `brr` = `[1, 1, 2, 4]`.\ Median = Min(1, 2) = 1.

## Notes

• Desired complexity is logarithmic and not linear.
• We define median as following:
• For an array of odd length, the median is the middle element.
• For an array of even length, the median is the smaller number of the 2 middle elements.

Constraints:

• 2 <= `n + m` <= 2 * 105
• 1 <= any element of `arr` and `brr` <= 109

We have provided two solutions. Throughout the editorial, we will refer to the input arrays as `arr` and `brr` and their size as `n` and `m` respectively.

# Median Of Two Sorted Arrays Solution 1: Linear

• We have to find the median of the merged array obtained after merging 2 sorted arrays.
• We start by traversing the 2 array and keeping track of the minimum element so far.
• As we can see, the answer would be the `(n + m) / 2`-th minimum element.
• So, we keep on traversing the arrays and move the current pointer for the array having the smaller element, to the next element.
• Finally, when we reach the `(n + m) / 2`-th element, we return it, as it is our answer.

## Time Complexity

O(n + m).

We simply traverse both the arrays simultaneously and keep on checking for the minimum element. We traverse at most one time. Hence, the time complexity is O(n+m).

## Auxiliary Space Used

O(1).

We only used a constant amount of extra space.

## Space Complexity

O(n + m).

Space used for input: O(n + m).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(n + m).

## Code For Median Of Two Sorted Arrays Solution 1: Linear

``````    /*
Asymptotic complexity in terms of size of input list 'arr' ( = 'n') and 'brr' ( = 'm'):
* Time: O(n + m).
* Auxiliary space: O(1).
* Total space: O(n + m).
*/

static Integer find_median(ArrayList<Integer> arr, ArrayList<Integer> brr) {
int l = arr.size() + brr.size();
int index = 0;

if(l % 2 == 0) {
index = l / 2 - 1;
}

else {
index = l / 2;
}
int ans = Integer.MAX_VALUE;
int i = 0, j = 0;

// We keep on iterating both the lists until we get the index th value.
// We also make sure we traverse in ascending order.
while(index >= 0) {

// If list 'arr' gets exhausted.
if(i == arr.size()) {
ans = brr.get(j++);
}
// If list 'brr' gets exhausted.
else if(j == brr.size()) {
ans = arr.get(i++);
}
// Otherwise we get the smaller one and move that the current pointer pointing to that list.
else {
if(arr.get(i) > brr.get(j)) {
ans = brr.get(j++);
}
else {
ans = arr.get(i++);
}
}
index--;
}
return ans;
}
``````

# Median Of Two Sorted Arrays Solution 2: Optimal

• We have to find the median of the merged array obtained after merging two sorted arrays.
• The goal is to find a partition that divides the combined array in two equal halves (one half having one more element than other in case of odd length) such that the elements in the first half are smaller or equal to the elements in the second half.
• Once we have such a partition, we can simply return the largest element of the first partition which would be the desired output as that would be the element present at the `(n + m - 1) / 2`-th index in the merged array `arr + brr` which is the required answer.
• We use binary search to find such a partition and we start by initializing two pointers `min_index = 0` and `max_index = Math.min(n, m)`.
• We start iterating over the arrays and compare the last element of partition 1 present in array `arr` to the first element of partition 2 present in array `brr` and vice versa. After each comparison, we update `min_index` and `max_index` accordingly.
• Finally, we keep on repeating this until `min_index <= max_index`.
• And we find the median when either we exhaust one of the arrays or none of the if conditions are met.

Example:

• Let's try to find out the median for `arr = [1, 2, 5]`, `brr = [1, 2, 3, 4, 5]`.
• So initially `min_index = 0`, `max_index = n = 3`.
• Now we start iterating until `min_index <= max_index`.
• So, now during first iteration, `i = 1` and `j = 3`
• `brr = 3` and `arr = 2`, so here `brr > arr` => `min_index = i + 1 = 2`.
• So during iteration 2, `i = 2` and `j = 2`.
• So in this case we go to the else condition as none of the if conditions are true.
• Hence we return `Max(arr, brr) = Max(2, 2) = 2`.
• So the median is 2.

## Time Complexity

O(log(min(n, m))).

We use binary search to find the partition. Also, since we are performing binary search until we find the median or we exhaust one of the arrays, time complexity is O(log(min(n, m)).

## Auxiliary Space Used

O(1).

We only used a constant amount of extra space.

## Space Complexity

O(n + m).

Space used for input: O(n + m).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(n + m).

## Code For Median Of Two Sorted Arrays Solution 2: Optimal

``````    /*
Asymptotic complexity in terms of size of input lists 'arr' ( = 'n') and 'brr' ( = 'm'):
* Time: O(log(min(n, m))).
* Auxiliary space: O(1).
* Total space: O(n + m).
*/

static Integer find_median(ArrayList<Integer> arr, ArrayList<Integer> brr) {
int n = arr.size(), m = brr.size();

// We need to keep the smaller list first to ensure that time complexity is O(log(min(n, m))).
ArrayList<Integer> min_list = (n < m) ? arr : brr;
ArrayList<Integer> max_list = (n < m) ? brr : arr;

int min_index = 0, max_index = Math.min(n, m);
int i = 0, j = 0;

while (min_index <= max_index) {
i = (min_index + max_index) / 2;
j = ((n + m + 1) / 2) - i;

// We try to find a partition. We update the \`min_index\` accordingly.
if (i < min_list.size() && j > 0 && max_list.get(j - 1) > min_list.get(i)) {
min_index = i + 1;
}

// We try to find a partition. We update the \`min_index\` accordingly.
else if (i > 0 && j < max_list.size() && max_list.get(j) < min_list.get(i - 1)) {
max_index = i - 1;
}

// We got our desired halves, now we simply find the median.
else {
if (i == 0) {
}
else if (j == 0) {
}
else {
answer = Math.max(min_list.get(i - 1), max_list.get(j - 1));
}
}
}
}
``````

We hope that these solutions to median of two sorted arrays problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

### Try yourself in the Editor

Note: Input and Output will already be taken care of.

# Median Of Two Sorted Arrays Problem Statement

Given two sorted arrays `arr` and `brr` of size `n` and `m` respectively, find the median of the array obtained after merging arrays `arr` and `brr` (i.e. array of length `n + m`).

## Example

``````{
"arr": [1, 2],
"brr": [1, 4]
}
``````

Output:

``````1
``````

Here, `arr = [1, 2]`, `brr = [1, 4]`.\ Array after merging `arr` and `brr` = `[1, 1, 2, 4]`.\ Median = Min(1, 2) = 1.

## Notes

• Desired complexity is logarithmic and not linear.
• We define median as following:
• For an array of odd length, the median is the middle element.
• For an array of even length, the median is the smaller number of the 2 middle elements.

Constraints:

• 2 <= `n + m` <= 2 * 105
• 1 <= any element of `arr` and `brr` <= 109

We have provided two solutions. Throughout the editorial, we will refer to the input arrays as `arr` and `brr` and their size as `n` and `m` respectively.

# Median Of Two Sorted Arrays Solution 1: Linear

• We have to find the median of the merged array obtained after merging 2 sorted arrays.
• We start by traversing the 2 array and keeping track of the minimum element so far.
• As we can see, the answer would be the `(n + m) / 2`-th minimum element.
• So, we keep on traversing the arrays and move the current pointer for the array having the smaller element, to the next element.
• Finally, when we reach the `(n + m) / 2`-th element, we return it, as it is our answer.

## Time Complexity

O(n + m).

We simply traverse both the arrays simultaneously and keep on checking for the minimum element. We traverse at most one time. Hence, the time complexity is O(n+m).

## Auxiliary Space Used

O(1).

We only used a constant amount of extra space.

## Space Complexity

O(n + m).

Space used for input: O(n + m).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(n + m).

## Code For Median Of Two Sorted Arrays Solution 1: Linear

``````    /*
Asymptotic complexity in terms of size of input list 'arr' ( = 'n') and 'brr' ( = 'm'):
* Time: O(n + m).
* Auxiliary space: O(1).
* Total space: O(n + m).
*/

static Integer find_median(ArrayList<Integer> arr, ArrayList<Integer> brr) {
int l = arr.size() + brr.size();
int index = 0;

if(l % 2 == 0) {
index = l / 2 - 1;
}

else {
index = l / 2;
}
int ans = Integer.MAX_VALUE;
int i = 0, j = 0;

// We keep on iterating both the lists until we get the index th value.
// We also make sure we traverse in ascending order.
while(index >= 0) {

// If list 'arr' gets exhausted.
if(i == arr.size()) {
ans = brr.get(j++);
}
// If list 'brr' gets exhausted.
else if(j == brr.size()) {
ans = arr.get(i++);
}
// Otherwise we get the smaller one and move that the current pointer pointing to that list.
else {
if(arr.get(i) > brr.get(j)) {
ans = brr.get(j++);
}
else {
ans = arr.get(i++);
}
}
index--;
}
return ans;
}
``````

# Median Of Two Sorted Arrays Solution 2: Optimal

• We have to find the median of the merged array obtained after merging two sorted arrays.
• The goal is to find a partition that divides the combined array in two equal halves (one half having one more element than other in case of odd length) such that the elements in the first half are smaller or equal to the elements in the second half.
• Once we have such a partition, we can simply return the largest element of the first partition which would be the desired output as that would be the element present at the `(n + m - 1) / 2`-th index in the merged array `arr + brr` which is the required answer.
• We use binary search to find such a partition and we start by initializing two pointers `min_index = 0` and `max_index = Math.min(n, m)`.
• We start iterating over the arrays and compare the last element of partition 1 present in array `arr` to the first element of partition 2 present in array `brr` and vice versa. After each comparison, we update `min_index` and `max_index` accordingly.
• Finally, we keep on repeating this until `min_index <= max_index`.
• And we find the median when either we exhaust one of the arrays or none of the if conditions are met.

Example:

• Let's try to find out the median for `arr = [1, 2, 5]`, `brr = [1, 2, 3, 4, 5]`.
• So initially `min_index = 0`, `max_index = n = 3`.
• Now we start iterating until `min_index <= max_index`.
• So, now during first iteration, `i = 1` and `j = 3`
• `brr = 3` and `arr = 2`, so here `brr > arr` => `min_index = i + 1 = 2`.
• So during iteration 2, `i = 2` and `j = 2`.
• So in this case we go to the else condition as none of the if conditions are true.
• Hence we return `Max(arr, brr) = Max(2, 2) = 2`.
• So the median is 2.

## Time Complexity

O(log(min(n, m))).

We use binary search to find the partition. Also, since we are performing binary search until we find the median or we exhaust one of the arrays, time complexity is O(log(min(n, m)).

## Auxiliary Space Used

O(1).

We only used a constant amount of extra space.

## Space Complexity

O(n + m).

Space used for input: O(n + m).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(n + m).

## Code For Median Of Two Sorted Arrays Solution 2: Optimal

``````    /*
Asymptotic complexity in terms of size of input lists 'arr' ( = 'n') and 'brr' ( = 'm'):
* Time: O(log(min(n, m))).
* Auxiliary space: O(1).
* Total space: O(n + m).
*/

static Integer find_median(ArrayList<Integer> arr, ArrayList<Integer> brr) {
int n = arr.size(), m = brr.size();

// We need to keep the smaller list first to ensure that time complexity is O(log(min(n, m))).
ArrayList<Integer> min_list = (n < m) ? arr : brr;
ArrayList<Integer> max_list = (n < m) ? brr : arr;

int min_index = 0, max_index = Math.min(n, m);
int i = 0, j = 0;

while (min_index <= max_index) {
i = (min_index + max_index) / 2;
j = ((n + m + 1) / 2) - i;

// We try to find a partition. We update the \`min_index\` accordingly.
if (i < min_list.size() && j > 0 && max_list.get(j - 1) > min_list.get(i)) {
min_index = i + 1;
}

// We try to find a partition. We update the \`min_index\` accordingly.
else if (i > 0 && j < max_list.size() && max_list.get(j) < min_list.get(i - 1)) {
max_index = i - 1;
}

// We got our desired halves, now we simply find the median.
else {
if (i == 0) {
}
else if (j == 0) {
}
else {
answer = Math.max(min_list.get(i - 1), max_list.get(j - 1));
}
}
}
}
``````

We hope that these solutions to median of two sorted arrays problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

## Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve. Hosted By
Ryan Valles
Founder, Interview Kickstart Accelerate your Interview prep with Tier-1 tech instructors 360° courses that have helped 14,000+ tech professionals 100% money-back guarantee*