# Median of Two Sorted Arrays

Tags
Ansible
Kubernetes
Published
2019-01-19
Author
Man Parvesh Singh Randhawa

## Problem statement

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
``````nums1 = [1, 3]
nums2 = 

The median is 2.0``````
Example 2:
``````nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5``````
Link to the problem on leetcode: https://leetcode.com/problems/median-of-two-sorted-arrays/

## Notes

• Simple solution:
• Algorithm:
• Merge the two given lists into one using the method used in merge sort.
• Simply take the median of the new list.
• Complexity:
• Time: `O(n)`
• Space: `O(n)`
• Introduces the usage of new space, which can be a problem in case of very large data.
• Final solution:
• Instead of creating a new list from the existing sorted lists, just increment the pointers until the point at which the median of the two lists is supposed to be.
• Complexity:
• Time: `O(n)`
• Space: `O(1)`

## Pseudocode

``````Initialize variables ans, i, j to 0
while i is less than the array length:
Initialize current variable to the value of ith element in nums array
Increment ans
Set jth element to current
while i is less than array length and current is equal to ith element:
increment i
increment j
Return ans variable``````
• initialize variables `i` and `j` to `0`
• let `n` be the sum of lengths of the given lists
Time complexity: `O(n)`

## Implementations

### Java

``class Solution {    public double findMedianSortedArrays(int[] a1, int[] a2) {        int n = a1.length, m = a2.length;        int ar[] = new int[n + m];        int i = 0, j = 0;        int k = 0;        while (i < n && j < m) {            if (a1[i] < a2[j]) {                ar[k++] = a1[i++];            } else {                ar[k++] = a2[j++];            }        }        while (i < n) {            ar[k++] = a1[i++];        }        while (j < m) {            ar[k++] = a2[j++];        }        double median = 0;        int N = n + m;        if (N % 2 == 1) {            median = (double) ar[(N - 1) / 2];        } else {            median = ((double) ar[(N - 1) / 2] + ar[(N - 1) / 2 + 1]) / 2.0;        }        return median;    }}``

### C

``int removeDuplicates(int* nums, int numsSize) {    int i, ans, j, current;    i = 0;    j = 0;    ans = 0;    while (i < numsSize) {        current = nums[i];        nums[j] = current;        ans++;        while (i < numsSize && current == nums[i]) i++;        j++;    }    return ans;}``

### C++

``class Solution {public:    int removeDuplicates(vector<int>& ar) {        int ans = 0;        int i = 0, j = 0;        while (i < ar.size()) {            int current = ar[i];            ar[j] = current;            ans++;            while (i < ar.size() && current == ar[i]) i++;            j++;        }        return ans;    }};``

### Python

``class Solution(object):    def removeDuplicates(self, nums):        """        :type nums: List[int]        :rtype: int        """        ans, i, j = 0, 0, 0        while i < len(nums):            current = nums[i]            ans += 1            nums[j] = current            while i < len(nums) and current == nums[i]:                i += 1            j += 1        return ans``

### JavaScript

``/** * @param {number[]} nums * @return {number} */var removeDuplicates = function(nums) {    var ans = 0, i = 0, j = 0, current;    while (i < nums.length) {        current = nums[i];        nums[j] = current;        ans++;        while (i < nums.length && current == nums[i]) i++;        j++;    }    return ans;};``