Java O(m+n) Easy To Understand, Optimal Solution


  • 0
    B

    Explanation
    The idea to this question is to merge the two arrays starting from their ends, by keeping track of a pointer index for each array, index1 and index2.

    Since nums1 has size at least m+n, we can write the results of our comparisons, max(nums1[index1], nums2[index2]) to nums1 starting from index m+n-1 and ending at index 0. We won't ever overwrite useful nums1 data because we will have already moved it to another location in nums1 as a result of our earlier comparisons.

    Scenario 1: All elements in nums2 are greater than all elements in nums1. So, we simply append the contents of nums2 after the contents in nums1, without moving any nums1 elements at all.

    nums1 = { 1, 2, 3, 4 }; nums2 = { 5, 6, 7, 8 }
    
    merge(nums1, 4, nums2, 4) => nums1 = { 1, 2, 3, 4, 5, 6, 7, 8 }
    

    Scenario 2: Some elements in nums2 are greater than all elements in nums1. So, we will end up with an intermixed nums1 array. Some nums1 elements were copied over to an index greater than n-1 in nums1. Key point: no nums1 data was lost.

    nums1 = { 1, 3, 5, 7 }; nums2 = { 2, 4, 6, 8 }
    
    merge(nums1, 4, nums2, 4) => nums1 = { 1, 2, 3, 4, 5, 6, 7, 8 }
    

    Scenario 3: All elements in nums2 are less than all elements in num1. So, we copy over all nums1 elements such that they now reside to the right of all nums2 elements.

    nums1 = { 5, 6, 7, 8 }; nums2 = { 1, 2, 3, 4 }
    
    merge(nums1, 4, nums2, 4) => nums1 = { 1, 2, 3, 4, 5, 6, 7, 8 }
    

    Time Complexity
    The time complexity is O(m+n) where m and n corresponds to the inputs m, n, since we iterate through all the elements in nums1 and num2 to form our merged array.

    class Solution {
       public void merge(int[] nums1, int m, int[] nums2, int n) {
           int index1 = m - 1;
           int index2 = n - 1;
            
            // Iterate starting from index m + n - 1 and ending at 0
           for (int i = m + n - 1; i >= 0; i--) {         
              // Case 1: nums1[index1] should be chosen over nums2[index2]
              if (index2 < 0 || index1 >= 0 && nums1[index1] > nums2[index2]) {
                    nums1[i] = nums1[index1];
                    index1--;
              } 
              // Case 2: nums2[index2] should be chosen over nums1[index1]
              else {
                  nums1[i] = nums2[index2];
                  index2--;
              }    
           }
       }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.