LeetCode #88. Merge Sorted Array

Extra Space solution

Time Complexity: O((m + n) log(m + n))

Breaking it down by operations:

First loop (adding m elements from nums1): O(m)
Second loop (adding n elements from nums2): O(n)
Collections.sort(): O((m + n) log(m + n)) - This dominates!
Final loop (copying back to nums1): O(m + n)

Total: O(m) + O(n) + O((m + n) log(m + n)) + O(m + n) = O((m + n) log(m + n))

Space Complexity: O(m + n)

ArrayList numList: Stores all m + n elements → O(m + n) extra space
Collections.sort(): Uses additional O(log(m + n)) space for the recursive call stack (Timsort implementation)
Other variables: O(1)

Total: O(m + n) auxiliary space

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        List<Integer> numList = new ArrayList<>();

        // Add first m elements from nums1
        for (int i = 0; i < m; i++) {
            numList.add(nums1[i]);
        }

        // Add all n elements from nums2
        for (int i = 0; i < n; i++) {
            numList.add(nums2[i]);
        }

        Collections.sort(numList);

        // Copy back to nums1
        for (int i = 0; i < numList.size(); i++) {
            nums1[i] = numList.get(i);
        }
    }
}