Blog

Hey everyone, welcome back to Krick Stacks! Today, we’re going to dive deep into the concept of merging arrays efficiently, and I’ll also show you how to optimize both time and space complexity in the process.

Merging arrays might sound simple, but it can get tricky when dealing with large datasets. So let’s break it down, understand what’s happening under the hood, and find ways to make it faster and more memory-efficient!

Part 1: Basic Array Merging

First things first, let’s start with the basics. Let’s say we have two sorted arrays, and our task is to merge them into one sorted array. Here’s a simple example:

let nums1 = [1, 3, 5];
let nums2 = [2, 4, 6];
let merged = nums1.concat(nums2).sort((a, b) => a - b);

console.log(merged);  // Output: [1, 2, 3, 4, 5, 6]

So far, so good. We’re using concat() to combine the arrays and sort() to make sure the result is sorted. But… it’s not the most efficient way, especially if the arrays are already sorted! Sorting a merged array from scratch introduces unnecessary time complexity.

Part 2: Optimizing Time Complexity

Instead of using sort(), which costs O((m+n) log(m+n)) time complexity, we can merge the arrays in a much faster way, taking advantage of the fact that they are already sorted. The goal here is to do this in O(m + n) time.

Let’s look at how we can merge two sorted arrays in one go, by comparing their elements step by step:

function mergeSortedArrays(nums1, nums2) {
    let i = 0, j = 0;
    let merged = [];

    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            merged.push(nums1[i]);
            i++;
        } else {
            merged.push(nums2[j]);
            j++;
        }
    }

    // If any elements are left in nums1 or nums2, add them
    return merged.concat(nums1.slice(i)).concat(nums2.slice(j));
}

console.log(mergeSortedArrays([1, 3, 5], [2, 4, 6]));
// Output: [1, 2, 3, 4, 5, 6]

Now, we’re talking! By comparing each element of the arrays and merging them on the go, we achieve a linear time complexity of O(m + n)—much faster than sorting after the fact.

Part 3: Space Complexity Consideration

Next up, let’s talk space complexity. In our previous example, we created a new array, merged, which required additional memory proportional to the size of nums1 and nums2.

In some scenarios, especially when working with large datasets, we want to minimize the amount of additional space we use. What if we could merge the second array directly into the first?

Part 4: Merging Arrays In-Place (Optimizing Space Complexity)

Let’s assume nums1 has enough space to hold all elements from nums2. We’ll use a two-pointer approach to merge these arrays in place, starting from the end of both arrays. This way, we won’t need extra space for the merged array.

function mergeInPlace(nums1, m, nums2, n) {
    let i = m - 1;  // Pointer for nums1's last initialized element
    let j = n - 1;  // Pointer for nums2's last element
    let k = m + n - 1;  // Pointer for the last position in nums1

    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k] = nums1[i];
            i--;
        } else {
            nums1[k] = nums2[j];
            j--;
        }
        k--;
    }

    // Add remaining elements of nums2 if any
    while (j >= 0) {
        nums1[k] = nums2[j];
        j--;
        k--;
    }
}

let nums1 = [1, 3, 5, 0, 0, 0];
let nums2 = [2, 4, 6];
mergeInPlace(nums1, 3, nums2, 3);

console.log(nums1);  // Output: [1, 2, 3, 4, 5, 6]

By merging from the end, we avoid overwriting values in nums1 as we go. The great thing about this approach is that we achieve the same O(m + n) time complexity, but now we’ve reduced the space complexity to O(1), because we aren’t using any additional memory for the merge.

If you were to start with nums1 = [1,2,3] array than space complexity would be O(m+n) since javascript will automatically resize the array to fit new data. In other programing languages like Java you would have to create a new array to store all data. Javascript is flexible and will automatically resize your array but will new to allocate more space in memory.

Part 5: Recap & Conclusion

To wrap up, here’s what we’ve learned:

1. Using concat() and sort() is simple but inefficient for large datasets.

2. A more efficient approach uses the two-pointer technique to merge sorted arrays in O(m + n) time.

3. To optimize space complexity, we can merge arrays in place by starting from the end, achieving O(1) space complexity.

That’s it for today! I hope you’ve enjoyed this dive into array merging and learned some new optimization techniques along the way. If you found this helpful, don’t forget to like, subscribe, and hit the notification bell for more programming tips and tricks! See you in the next video.