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 (Extra Space)

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

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

    // 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): Unit {
    var i = m - 1
    var j = n - 1
    var write = m + n - 1
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[write] = nums1[i]
            i--
        } else {
            nums1[write] = nums2[j]
            j--
        }
        write--
    }
    /**
     * We have to copy the remaining element of nums2 to nums1.
     * Ex:
     * nums1 = [5, 6, 0, 0]
     * nums2 = [1, 2]
     * Then [1, 2] will be remaining elements after the first while loop, so we just simply copy the remaining part.
     */
    while (j >= 0) {
        nums1[write] = nums2[j]
        j--
        write--
    }
}

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