Programming with Memory

The question is to determine the median of an array formed by blending two sorted arrays.
That is:

Given two sorted arrays nums1 and nums2 of size m and n, respectively, return the median of the two sorted arrays.

• Example 1:

  Input: nums1 = [1,3], nums2 = [2]
  Output: 2.00000
  Explanation: merged array = [1,2,3] and median is 2.

• Example 2:

  Input: nums1 = [1,2], nums2 = [3,4]
  Output: 2.50000
  Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

• The overall run time complexity should be O(log (m+n)).
• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

Approaches

S1: Insertion through halfway

Speed:2ms | Memory: 40.3MB

The approach fills a new ArrayList with the entirety from nums1 array, then proceeds to insert nums2 elements until the counter reaches the median index.

 public double findMedianArrayList1(int[] nums1, int[] nums2) {
        int i1 = 0;
        int i2 = 0;

        int imed = (nums1.length + nums2.length) / 2;

        List<Integer> list = new ArrayList();

        for (int n : nums1) {
            list.add(n);
        }

        while (i1 <= imed && i2 < nums2.length) {
            while (i1 < list.size() && nums2[i2] >= list.get(i1)) {
                i1++;
            }

            list.add(i1, nums2[i2]);
            i2++;
        }

        if ((nums1.length + nums2.length) % 2 == 0) {
            return (list.get(imed) + list.get(imed - 1)) / 2D;
        }

        return list.get(imed);
    }

S2: Retain Last Two Additions -- Two-Loops

Speed: 3ms | Memory: 40.4MB

A prototype to S3, this method first toggle-adds the smaller of latest num1[i] and num2[j] throughout the length of num1. Then it proceeds to add the remainder in num2 in the second loop until the counter reaches the median size.

During the run, (only )the last two additions to the arrays are kept track of by cycling one after another.

In turn, either the last or its average with the second last one will be returned, depending on the oddity of the blended array.

public double findMedianArrayList2(int[] nums1, int[] nums2) {
        int prev2 = - 1;
        int prev1 = -1;

        int i = 0, j = 0;
        int med = (nums1.length + nums2.length) / 2;

        for (; i < nums1.length && i+j < med + 1;) {
            if (j < nums2.length && nums2[j] < nums1[i]) {
                prev2 = prev1;
                prev1 = nums2[j];
                j++;

            } else {
                prev2 = prev1;
                prev1 = nums1[i];
                i++;
            }
        }

        for (; j < nums2.length && i+j <= med; j++) {
            prev2 = prev1;
            prev1 = nums2[j];
        }

        return ((nums1.length + nums2.length) % 2 == 0) ? (prev1 + prev2) / 2D
                                                        :  prev1;
    }

S3: Retain Last Two Additions -- Unified Loop

Speed : 2ms | Memory: 40.1MB

The final edition, this method unifies the two loops in S2 as a while loop.
It toggle-adds between the lesser of latest num1[i] and num2[j], unconditionally adding one side all if another was all iterated over.

    public double findMedianArrayList3(int[] num1, int[] num2) {
        int j = 0;
        int i = 0;
        int mid = (num1.length + num2.length) / 2;
        int prev2 = -1, prev1 = -1;

        while ((i+j) <= mid) {
            prev2 = prev1;

            if (i < num1.length && (j >= num2.length || num1[i] <= num2[j])) {
                prev1 = num1[i];
                i++;
            } else {
                prev1 = num2[j];
                j++;
            }
        }

        return ((num1.length + num2.length) % 2 == 0) ? (prev1 + prev2) / 2D
                                                      :  prev1;
    }

Conclusion

While the three methods show similar performances at minimal level, testing on extensive dataset revealed following comparison:

For dataset (n = 100,000) with (0 <= nums*.length < 10000)

[TEST-LOG]: [RESULTS]: 
            #1: [Uni-Loop Retainer] -- Average: 0.000043s -- Efficiency: 100% -- [FASTEST]
            #2: [Two-Way Retainer]  -- Average: 0.000069s -- Efficiency: 63%
            #3: [Insertion Halfwayer]   -- Average: 0.000831s -- Efficiency: 5% -- [SLOWEST]

While a much more efficient mechanism would be expected in such gigantic usage, this still proves the improvement at S3, emphasizing the need for a clearer and compact algorithm.