Merging Sorted Array Javascript

Question

I am working through some various LeetCode problems as practice on JavaScript concepts that I don't come across in my day to day.

Starting with the easy section I am confused as to why this merging array does not work? I find that I almost never splice since I am used to just iterating over and returning a new element and rarely am I working with a giant dataset that needs to be modified directly.

My Jasmine error is as follows

Check for Sorted Merge

    ✗ Array values are merged and sorted
      - Expected $.length = 6 to equal 3.
      Expected $[2] = 2 to equal 3.
      Unexpected $[3] = 3 in array.
      Unexpected $[4] = 5 in array.
      Unexpected $[5] = 6 in array.

Below is the code.

//////////////////
// INSTRUCTIONS //
//////////////////

// Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
// The number of elements initialized in nums1 and nums2 are m and n respectively.
// You may assume that nums1 has a size equal to m + n such that it has enough space to hold additional elements from nums2.

const nums1 = [1, 2, 3];
const m = 3;
const nums2 = [2, 5, 6];
const n = 3;

const mergeArray = (nums1, nums2) => {
  for (let index = 0; index < nums1.length - 1; index++) {
    if (nums2[index] >= nums1[index] && nums2[index] < nums1[index+1] ) {
      nums1.splice(index, 0, nums2[index]);
    }
  }
  return nums1;
};

module.exports = function () {
  describe("Check for Sorted Merge", () => {
    it("Array values are merged and sorted", () => {
      expect(nums1.concat(nums2).sort()).toEqual(mergeArray(nums1, nums2));
    });
  });
};

Heads-up: `nums1.concat(nums2).sort()` [would not necessarily sort integers correctly](https://stackoverflow.com/questions/1063007/how-to-sort-an-array-of-integers-correctly). It *does* work for your current input but it wouldn't if you add `12`, for example. — VLAZ, Mar 04 '21 at 06:20
Also relevant: [Looping through array and removing items, without breaking for loop](https://stackoverflow.com/q/9882284) — VLAZ, Mar 04 '21 at 06:24
Start by writing a version of `mergeArray` that doesn't mutate the input array. Instead, it should return a new array. Then, tweak the program to mutate the input array. — Aadit M Shah, Mar 04 '21 at 06:40

Alex L · Accepted Answer · 2021-03-04T10:00:34.260

Maybe something like this? As both arrays are sorted, we don't need to compare every m element with every n element. We can save some time complexity by keeping track of a start point, and update this each time we find a place for our n element from nums2. Hopefully it makes sense, but if not I can try to explain it more thoroughly.

const nums1 = [1, 2, 3]; // will always be sorted
const m = 3;
const nums2 = [2, 5, 6]; // will always be sorted
const n = 4;

const mergeArray = (nums1, nums2) => {
  let start_idx = 0;
  for (let num of nums2) {
    for (let idx = start_idx; idx < nums1.length; idx++){
      if (num <= nums1[idx]) {
        nums1.splice(idx, 0, num);
        start_idx = idx;
        break;
      }
      if (idx == nums1.length - 1){
        nums1.push(num);
        start_idx = idx;
        break;
      }
    }    
  }
  return nums1;
};

const res1 = nums1.concat(nums2).sort((a,b) => a-b);
const res2 = mergeArray(nums1, nums2);
console.log(res1, res2);

//JSON.stringify not ideal for arr/object comparison, but it works here for a quick check:
console.assert(JSON.stringify(res1) == JSON.stringify(res2), "sorts are not identical");

Yeah this checks out! Thanks :) I'm pushing it here: https://github.com/mpaccione/leetcode — Michael Paccione, Mar 14 '21 at 22:15
Great, glad to have helped. NOTE: Your assertion will not always work (it would fail if the inputs were `[1,2,3,13]` and `[2,5,6,11]`). As @VLAZ said above, you need to add a proper numerical sort function like `.sort((a,b) => a-b)` : https://github.com/mpaccione/leetcode/blob/main/easy/sortingSearching/mergeSortedArray.js#L36 — Alex L, Mar 18 '21 at 08:07

Merging Sorted Array Javascript

1 Answers1