88.merge-sorted-array.md

88. Merge Sorted Array

Straightforward

Merge two arrays first and then sort.

fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int) {
    for (i in m until (m + n)) {
        nums1[i] = nums2[i - m]
    }
    nums1.sort()
}

• Time Complexity: O(k log k) where k = m + n.
• Space Complexity: O(m + n) for the total size of array.

Two Pointers

fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
    val results = IntArray(m + n)
    var i = 0
    var j = 0
    var k = 0

    // Merge at the same length
    while (i < m && j < n) {
        if (nums1[i] < nums2[j]) {
            results[k] = nums1[i]
            i++
        } else {
            results[k] = nums2[j]
            j++
        }
        k++
    }
    
    // Merge the remaining part (for different size of two array)
    if (i < m) {
        for (x in i until m) {
            results[k] = nums1[x]
            k++
        }
    } else if (j < n) {
        for (y in j until n) {
            results[k] = nums2[y]
            k++
        }
    }

    // Copy result back to nums1
    for (k in 0 until (m + n)) {
        nums1[k] = results[k]
    }
}

• Time Complexity: O(m + n).
• Space Complexity: O(m + n) for result array.

Two Pointers (In-Place)

Compare the last elements of both arrays one by one, then put the larger num to the last position.

fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int) {
    var first = m - 1
    var second = n - 1
    var toInsertIndex = m + n - 1

    // Compare the common part
    while (first >= 0 && second >= 0) {
        if (nums1[first] > nums2[second]) {
            nums1[toInsertIndex] = nums1[first]
            first--
            toInsertIndex--
        } else {
            nums1[toInsertIndex] = nums2[second]
            second--
            toInsertIndex--
        }
    }

    // For the cases:
    // 1. nums1.size < nums2.size and the remaining elements are all less then nums1
    // 2. All elements in nums1 are greater then nums2.
    // We just copy the remaining element of nums2 to nums1.
    // 
    // Ex:
    //  nums1 = [5, 6]
    //  nums2 = [1, 2, 9, 10]
    // Then [1, 2] will be remaining elements after the first while loop, so we just simply copy the remaining part.
    while (second >= 0) {
        nums1[toInsertIndex] = nums2[second]
        second--
        toInsertIndex--
    }
}

• Time Complexity: O(m + n), the maximum iteration of while loop will be m + n times.
• Space Complexity: O(1).