0
$\begingroup$

I came up with a solution for LeetCode Problem 4:
Median of Two Sorted Arrays

The expected efficiency of this should be $O(\log(m+n))$, where $m$ and $n$ are the lengths of nums1 and nums2.

For my solution I decided only to process only the first half of nums1 and nums2.
Does that count as logarithmic time, or is it still linear time?

My Java code:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Don't need the entire array - only the first half
        int maxSize = nums1.length + nums2.length;
        int size = maxSize / 2 + 1;
        
        // Merged array and its index
        int[] merged = new int[size];
        int m = 0;
        
        // Left index, right index
        int l = 0;
        int r = 0;
        
        // Build the merged array
        while (m < merged.length) {
            if (l >= nums1.length) {
                // Left array exhausted - just add the right array
                merged[m] = nums2[r];
                m++;
                r++;
            } else if (r >= nums2.length) {
                // Vice versa
                merged[m] = nums1[l];
                m++;
                l++;
            } else {
                // Compare left and right
                int a = nums1[l];
                int b = nums2[r];

                if (a > b) {
                    merged[m] = b;
                    m++;
                    r++;
                } else {
                    merged[m] = a;
                    m++;
                    l++;
                }   
            }
        }
        
        // Debug
        // for (int x : merged) {
        //     System.out.print(x + ", ");
        // }
        // System.out.println();
        
        // Find median based on the first half
        if (maxSize % 2 == 0) {
            // Divide with 2.0 instead of 2: important!
            return (merged[size-1] + merged[size-2]) / 2.0;
        } else {
            return merged[size-1];   
        }
    }
}

Pseudocode:

  • Make a new array $m$, which is the size of the first half of both arrays combined

  • Merge both arrays together in the correct order into the array $m$
    (note that this will not fully iterate the first or second array, since $m$ is only the size of the first half of both combined arrays)

  • Return the last element of 'm', or the average of the 2 last elements of $m$ (the median of both sorted arrays)

Leetcode result:

Runtime: 2 ms, faster than 99.75% of Java online submissions for Median of Two Sorted Arrays.
Memory Usage: 40.1 MB, less than 81.65% of Java online submissions for Median of Two Sorted Arrays.
$\endgroup$
2
  • 1
    $\begingroup$ Can you describe your algorithm without using Java? $\endgroup$ – Yuval Filmus Jan 16 at 16:54
  • $\begingroup$ I have updated the post to explain the algorithm using pseudocode and removed the comment about binary search since it was confusing. What I was trying to say is that just like binary search is O(log(n)) because it divides the array in half each time, my algorithm only processes the first half of the merged array to find the median. $\endgroup$ – Taimoor Ahmad Jan 16 at 18:10
1
$\begingroup$

Judging from your description and your code, you are basically doing a merge of the two array but stop at the median. This means that your main loop (body) is executed $(m + n) / 2 \in O(m + n)$ times, which is linear in $m + n$. You could also figure that one out experimentally by trying your algorithm on a range of different inputs and plotting the time taken against $m + n$, I guess.

If you want to find a solution which takes $O(\log (m + n))$ time you could try working backwards: A binary search over a (sorted) array of length $n$ takes $O(\log(n))$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.