CODEWITHSUNDEEP
arrayssortingmerge
Tejaswi Manivannan
Tejaswi Manivannan

Reputation: 19

How do I merge two sorted arrays?

Two arrays (nums1 and nums2) of length m and n respectively have to be merged and the and be sorted in the array nums1. length of nums1 is m+n and last n elements in nums1 are 0. Not to be returned, nums1 has to be modified. LeetCode question

Example

Input
nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3
Output [1, 2, 2, 3, 5, 6]
Explanation

The arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

I have done the question but no idea why its not working.

var merge = function(nums1, m, nums2, n) {
    let j = 0
    for (let i = m; i < n; i++) {
      nums1[i] = nums2[j]
      j++
    } 
};

Driven Code:

let nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
merge(nums1, m, nums2, n)
console.log(nums1)

Output:

[1, 2, 3, 0, 0, 0]

Upvotes: 1

Views: 539

Answers (4)

user1996632
user1996632

Reputation: 11

There you go

public void merge(int[] nums1, int m, int[] nums2, int n) {
    
    if (n == 0) {
        return;
    }

   int i = m - 1;
   int j = n - 1;
    int k = nums1.length - 1;
    while (i >= 0 && j >= 0) {
        if (nums2[j] > nums1[i]) {
            nums1[k--] = nums2[j--];
        } else {
            nums1[k--] = nums1[i--];
        }
    }
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

Upvotes: 0

Md Shafayet Maruf
Md Shafayet Maruf

Reputation: 46

Do you searching something like this?

nums1 = [...nums1, ...nums2].sort().filter(i => i != 0);  
console.log(nums1);

Steps taken here:

  1. First contact two array
  2. Then sort the array in ascending order
  3. Then remove 0 from the array

Check this out:

tempNums1 = nums1.slice(0, m);
tempNums2 = nums2.slice(0, n);
arr = [...tempNums1, ...tempNums2].sort((a,b) => { return a - b; });
nums1.splice(0, nums1.length);  
for(let i=arr.length - 1;i>=0;i--){
    nums1.unshift(arr[i]);
}

Here the hack is splice and unshift takes effect outside of the function scope

Updated:

 nums1.splice(m, nums1.length);// O(n)
 for(let j=0; j< n; j++){
     nums1.unshift(nums2[j]); // O(n)
 }
 nums1.sort((a, b) => a - b); // O(n log n)

Upvotes: 0

Alexander
Alexander

Reputation: 63167

You've misunderstood the purpose of m and n. You should step through this in the debugger, and you'll quickly notice your loop is never entered.

They're not first and last indices of the "zero region". They're the first index, and the count of zeros found after that (which is as long as the num2 array that would be merged into num1. This would be more apparent if the names weren't as useless as m and n.

A performant solution to this would involve doing this in-place (in fact, the problem outline requires that you modify num1 rather than make a new array).

You know both arrays are sorted, so "merging" only requires you pick the smallest element from each. The problem is that all your "free space" in num1 (the 0s) are located at the back, which makes it had to make room at the beginning of the array to insert elements from num2.

Instead, you can rely on this fact: An array that's sorted smallest-to-largest is also sorted when reversed, except from largest-to-smallest. While this may be obvious, it's the key trick: you fill num2 starting from the end, and working towards the start. At every step, you replace a 0 (and eventually, the other numbers)with the largest element from the "tail" ofnum1ornum2`.

Doing this all the way through gives you a time complexity of O(n) with no extra space used.

Upvotes: 2

Pradeep Rajput
Pradeep Rajput

Reputation: 725

Usse concat function of array and then sort function

e.g.

num1 = num1.concat(num2)
num1.sort()

OR

num1 = num1.concat(num2).sort()

Upvotes: 0

Related Questions