Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

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`

).

```
{
"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.

- 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 * 10^{5} - 1 <= any element of
`arr`

and`brr`

<= 10^{9}

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.

- 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.

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).

O(1).

We only used a constant amount of extra space.

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).

```
/*
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;
}
```

- 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[2] = 3`

and`arr[1] = 2`

, so here`brr[2] > arr[1]`

=>`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[1], brr[1]) = Max(2, 2) = 2`

. - So the median is 2.

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)).

O(1).

We only used a constant amount of extra space.

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).

```
/*
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 answer = 0;
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) {
answer = max_list.get(j - 1);
}
else if (j == 0) {
answer = min_list.get(i - 1);
}
else {
answer = Math.max(min_list.get(i - 1), max_list.get(j - 1));
}
return answer;
}
}
return answer;
}
```

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:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

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

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`

).

```
{
"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.

- 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 * 10^{5} - 1 <= any element of
`arr`

and`brr`

<= 10^{9}

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.

- 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.

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).

O(1).

We only used a constant amount of extra space.

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).

```
/*
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;
}
```

- 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[2] = 3`

and`arr[1] = 2`

, so here`brr[2] > arr[1]`

=>`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[1], brr[1]) = Max(2, 2) = 2`

. - So the median is 2.

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)).

O(1).

We only used a constant amount of extra space.

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).

```
/*
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 answer = 0;
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) {
answer = max_list.get(j - 1);
}
else if (j == 0) {
answer = min_list.get(i - 1);
}
else {
answer = Math.max(min_list.get(i - 1), max_list.get(j - 1));
}
return answer;
}
}
return answer;
}
```

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:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart