Jump to content

News

Leet code 88 - Merging Two Sorted Arrays in JavaScript

Maxammopro#1150

Entry posted by Maxammopro#1150 in NodeJs

54 views

 Share

Merging Two Sorted Arrays in JavaScript

One of the most common tasks you will encounter in algorithmic challenges is merging two sorted arrays. This concept might seem simple at first glance, but it becomes more interesting when constraints are added. For example, in this challenge, we need to merge two sorted arrays in-place in the first array while maintaining a time complexity of O(m + n).

But why is this problem important, and how does it relate to real-world coding scenarios?

Why Merging Sorted Arrays Matters

Merging sorted arrays efficiently is crucial in many areas of software development. Whether you're building an algorithm that needs to combine multiple streams of sorted data (think of combining search results from different sources), or you're working on a system that processes large amounts of sorted data, mastering this problem will help you optimize performance and reduce memory usage.

Additionally, many modern web applications rely on manipulating large datasets. Being able to handle merging operations quickly and without extra memory allocation is an essential skill for building efficient systems.

Before we dive into the solution, give it a go yourself! Can you come up with an efficient algorithm to merge two sorted arrays? Think about the constraints of doing this in-place.

Challenge: Merging Sorted Arrays

If you’re looking for the original challenge, here’s a link to the problem: LeetCode 88: Merge Sorted Array.

Take some time to solve the problem. We'll wait here while you give it a shot!

Our Approach to the Problem

Alright, if you've tried the challenge and are ready for the solution, here’s a step-by-step breakdown of our approach:

  1. Two-Pointer Approach: We use two pointers, one for each of the two arrays. We start from the end of each array and compare the elements. The reason for starting at the end is that it allows us to fill the array nums1 from the back, ensuring we don’t overwrite elements that have not been processed yet.

  2. In-place Merging: The challenge specifies that the result must be stored in nums1, which is already preallocated with enough space to hold the merged result. So, rather than creating a new array, we modify nums1 in place to save memory. This is a key part of the problem.

  3. Efficient Time Complexity: We aim for O(m + n) time complexity, where m is the number of elements in nums1 and n is the number of elements in nums2. This is achieved because each element from both arrays is processed exactly once.

  4. Handling Remaining Elements: Once we’ve finished comparing the elements from the two arrays, there might still be elements left in nums2. If that’s the case, we simply copy them into nums1 since they are already sorted.

Here’s the code for our solution in Node.js: 

 
javascript
CopyEdit
/** * Merges two sorted arrays into the first array in sorted order. * The first array nums1 has enough space to hold all elements from both arrays. * * @param {number[]} nums1 - The first sorted array with extra space at the end. * @param {number} m - The number of valid elements in nums1. * @param {number[]} nums2 - The second sorted array. * @param {number} n - The number of valid elements in nums2. */ function mergeSortedArrays(nums1, m, nums2, n) { let idx1 = m - 1; // Pointer for the last element in the valid part of nums1 let idx2 = n - 1; // Pointer for the last element in nums2 let mergeIdx = m + n - 1; // Pointer for the last position in nums1 (where we merge elements) // Merge the arrays from the back to avoid overwriting elements in nums1 while (idx1 >= 0 && idx2 >= 0) { if (nums1[idx1] > nums2[idx2]) { nums1[mergeIdx] = nums1[idx1]; idx1--; } else { nums1[mergeIdx] = nums2[idx2]; idx2--; } mergeIdx--; } // If there are any remaining elements in nums2, copy them over while (idx2 >= 0) { nums1[mergeIdx] = nums2[idx2]; idx2--; mergeIdx--; } } // Example usage const nums1 = [1, 2, 3, 0, 0, 0]; const m = 3; const nums2 = [2, 5, 6]; const n = 3; mergeSortedArrays(nums1, m, nums2, n); console.log(nums1); // Output: [1, 2, 2, 3, 5, 6]

Key Takeaways:

  • Two-pointer technique: Start merging from the end of the arrays to avoid overwriting elements.
  • In-place merge: We don’t need extra memory space, making the solution more efficient.
  • Efficient time complexity: The algorithm runs in O(m + n) time, which is optimal for this problem.

Your Turn!

Now that you've seen the solution, it's time to test your skills. Try running the code with different inputs and see how quickly you can modify the arrays! Also, if you found this blog helpful, we’d love to hear from you.

Let’s get the conversation going! Post your results in the chat and tell us how you solved the challenge or if you found any alternative approaches. We're excited to see how you tackled it!

Happy coding! 💻🚀

 Share

2 Comments

Recommended Comments

Merzal-1414

The most interesting part to this problem is here imo (I time stamped it in the youtube video), where your first couple numbers are larger in the second array compared to the numbers in the first array.

The most important thing to note is that the first loop works while the n AND m indexes are greater than 0, which means as soon as the first arrays index hits 0 and the second array still has more to go, that loop exists and the second while loop take overs to finish the job.

A simple problem but with a small catch which might not be noticed on first glance if trying to work it out only mentally with no writing / draw ups.
 


 

Link to comment
Maxammopro#1150

Here is the full code from Merging Two Sorted Arrays in JavaScript 

function mergeSortedArrays(nums1, m, nums2, n) {
    let idx1 = m - 1;        // Pointer for the last element in the valid part of nums1
    let idx2 = n - 1;        // Pointer for the last element in nums2
    let mergeIdx = m + n - 1; // Pointer for the last position in nums1 (where we merge elements)

    // Merge the arrays from the back to avoid overwriting elements in nums1
    while (idx1 >= 0 && idx2 >= 0) {
        if (nums1[idx1] > nums2[idx2]) {
            nums1[mergeIdx] = nums1[idx1];
            idx1--;
        } else {
            nums1[mergeIdx] = nums2[idx2];
            idx2--;
        }
        mergeIdx--;
    }

    // If there are any remaining elements in nums2, copy them over
    while (idx2 >= 0) {
        nums1[mergeIdx] = nums2[idx2];
        idx2--;
        mergeIdx--;
    }
}

// Example usage
const nums1 = [1, 2, 3, 0, 0, 0], m = 3;
const nums2 = [2, 5, 6], n = 3;

mergeSortedArrays(nums1, m, nums2, n);
console.log(nums1); // Output: [1, 2, 2, 3, 5, 6]

 

Edited by Maxammopro#1150
Link to comment

Please sign in to comment

You will be able to leave a comment after signing in



Sign In Now
×
×
  • Create New...