Median of Two Sorted Arrays

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

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)

Disadvantage:

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;};