Merge Two Arrays And Sort The Final One

August 20, 2024 Post a Comment

In an interview I was asked the following question. I am given two arrays, both of them are sorted. BUT Array 1 will have few -1's and Array 2 will have total numbers as the total

Solution 1:

You can try following approach:

Logic

Create a new array that will be returned.
Check for first element in arrayTwo and keep it in a variable say val.
Loop over arrayOne and check if current value is greater than val, push it in array and decrement value of i by 1 to check next value as well with current element.
Now check for current element. If it is less than 0, ignore it, else push value to array.
Return this array.

functionmergeAndSort(a1, a2) {
  var matchCount = 0;
  var ret = [];

  for (var i = 0; i < a1.length; i++) {
    var val = a2[matchCount];
    if (a1[i] > val) {
      ret.push(val)
      matchCount++
      i--;
      continue;
    }
    if (a1[i] > 0) {
      ret.push(a1[i]);
    }
  }
  console.log(ret.join())
  return ret;
}


var arrayOne = [3, 6, -1, 11, 15, -1, 23, 34, -1, 42]
var arrayTwo = [7, 19, 38];
var arrayThree = [1, 9, 28];
var arrayFour = [1,2,5]

mergeAndSort(arrayOne, arrayTwo)
mergeAndSort(arrayOne, arrayThree)
mergeAndSort(arrayOne, arrayFour)

.as-console-wrapper {
  max-height: 100%!important;
  top: 0;
}

Note: Not putting check for number of elements in arrayTwo as its clearly mentioned in question that it will be same.

Solution 2:

There is a clean O(N) in-place solution.

First "pack" arrayOne by moving all -1 (-- below) to the front. This takes a single backward pass.

Then perform a merge by iteratively moving the smallest element among arrayTwo and the tail of arrayOne and overwriting the next --. The gap will narrow down but there will always remain room for the elements of arrayTwo.

3,  6, --, 11, 15, --, 23, 34, --, 421,  9, 28

Packing:

3,  6, --, 11, 15, --, 23, 34, --, 423,  6, --, 11, 15, --, 23, --, 34, 423,  6, --, 11, 15, --, --, 23, 34, 423,  6, --, 11, --, --, 15, 23, 34, 423,  6, --, --, --, 11, 15, 23, 34, 423, --, --, --,  6, 11, 15, 23, 34, 42--, --, --, 3,  6, 11, 15, 23, 34, 42

Merging:

--, --, --,  3,  6, 11, 15, 23, 34, 421,  9, 281, --, --,  3,  6, 11, 15, 23, 34, 42--,  9, 281,  3, --, --,  6, 11, 15, 23, 34, 42--,  9, 281,  3,  6, --, --, 11, 15, 23, 34, 42--,  9, 281,  3,  6,  9, --, 11, 15, 23, 34, 42--, --, 281,  3,  6,  9, 11, --, 15, 23, 34, 42--, --, 281,  3,  6,  9, 11, 15, --, 23, 34, 42--, --, 281,  3,  6,  9, 11, 15, 23, --, 34, 42--, --, 281,  3,  6,  9, 11, 15, 23, 28, 34, 42--, --, --

Solution 3:

You should do something like insertion sort. As both the arrays are sorted (except -1s), the smallest number in array2 will be placed somewhere between first element and the first -1, 2nd element of array2 will be placed somewhere anywhere after the 1st -1 in array1 and before or at the 2nd -1 in array1 and so on.

So you have to insert a particular element of array2 in only a segment of array1 and not the whole array. Also each element of array2 have to consider different segment or subarray of array1. So, effective time complexity of this logic will be O(n+m) where n is the length of array1 and m is the length of array2.

Solution 4:

Couldn't it be something like

compare each item of arrayTwo with each item of arrayOne If it comes to bigger that that of arrayOne, insert the item and while iterating arrayOne delete all the -1 .

Solution 5:

That's actually an interesting question. There are many sorting algorithms, and the most efficient ones always starts from one "unchangeable" array, so without changing the values inside that. Yet here your goal is to change the value when it encounters -1, so that the value is taken from the second array.

So, you need a sorting algorithm that doesn't divide the array in pieces because if the last element of your second array is 1 (the lowest), it has to be moved to the start. If you're using a sorting algorithm that breaks the array in pieces (the divide-and-conquer tactic like quick sort) or that uses recursion, it can be problematic because it cannot be moved to the start of your main array. Unless you are aware of the main array.

What you need is an algorithm that performs a step-by-step algorithm.

The algorithm that I've used is a bubble sort, which checks each element step by step. It's then easier to replace the value if it's -1 and move its position correctly to the array. However, it is not so efficient. Maybe I will edit my post to see if I can improve that.

functionmergeAndSort(arr1, arrMergeIn) {
  // merge + sort using arr1 as large onevar mergeIndex = 0;

  for (var i = 0; i < arr1.length; ++i) {
    if (arr1[i] === -1) arr1[i] = arrMergeIn[mergeIndex++];
    var j = i;
    while (j > 0 && arr1[j - 1] > arr1[j]) {
      var tmp = arr1[j - 1];
      arr1[j - 1] = arr1[j];
      arr1[j] = tmp;
      j--
    }
  }
  return arr1;
}

// one liner console outputfunctionshowArray(arr) {
console.log(arr.join(','));
}


showArray(mergeAndSort([3, 6, -1, 11, 15, -1, 23, 34, -1, 42], [7, 19, 38]));

showArray(mergeAndSort([3, 36, -1, 1, 10, -1, 9, 34, -1, 42], [17, 9, 38]));

showArray(mergeAndSort([3, 36, -1, 1, 10, -1, 9, 34, -1, 42], [17, 9, 1]));

showArray(mergeAndSort([-1, 36, -1, 1, 10, -1, 9, 34, -1, 42], [17, 9, 100, 1]));

showArray(mergeAndSort([-1, -1, 1, 100, -1, 9, 34, -1], [17, 9, 9, 1]));

Or, you can use another strategy: replace the "-1" elements with the elements from that another array and perform an efficient algorithm on that. Although in worst-case scenario's, the "-1"s are at the end of the array, which means that there is an ~N operation + additional average complexity of a sorting algorithm (the efficient ones are of ~N*log(N))

javascript html php