I am trying to reverse an array in JS in-place (without using extra array). I am using split-merge recursively (I first split the array into two halves and then rearrange each half separately and after that combine the results of the two arrangements). the problem seems to arise if the array length is an odd number, in which case there will exist an array that have a single item and another array that have two items.

example :

reverseArrayInPlace([1, 5, 0, 4, 6]) should work like this :

1- reverseArrayInPlace([1,5,0]) -> returns the below calls

• reverseArrayInPlace([1, 5]) -> returns [5, 1]
• reverseArrayInPlace([0]) -> returns [0]

now the two arrays of the first call should be merged and swapped. The result should be [0,5,1]

2- reverseArrayInPlace([4, 6]) -> returns [6,4]

Now, the result of the call (1) and call (2) must be merged and swapped (using concat also); which will make the result as : [6,4,0,5,1].

I know there are other easier ways, but I want to know why my code is not returning the correct value .

let reverseArrayInPlace = ar => {

    let splitArray = arr => {
        if( arr.length === 1){
            console.log('length = 1', arr);
            return arr;
        }
        else if(arr.length === 2){
            console.log('length = 2', arr);
            let temp = arr[0]; arr[0] = arr[1]; arr[1] = temp;
            return arr;
        }
        else{
            reverseArrayInPlace(arr);
            //reverseArrayInPlace (ar2);
        }
    }
    let mergeArray = (arr1, arr2) => {
        console.log("Swapping : ", arr1, arr2);
        console.log('Concated : ',arr2.concat(arr1));

        if(arr1 === undefined)
            return arr2;
        else if(arr2 === undefined)
            return arr1;
        else
            return arr2.concat(arr1);
    }
    let half = Math.ceil(ar.length / 2);
    //console.log('half = ', half);

    ar1 = splitArray(ar.slice(0, half));
    ar2 = splitArray(ar.slice(half));
    //console.log(arr1, arr2);
    return mergeArray(ar1, ar2);
    
}
let ar = [1, 5, 0, 4, 6];
console.log(reverseArrayInPlace(ar));

CodePudding user response：

In your split array function, you miss a return:

 let splitArray = arr => {
        if( arr.length === 1){
            console.log('length = 1', arr);
            return arr;
        }
        else if(arr.length === 2){
            console.log('length = 2', arr);
            let temp = arr[0]; arr[0] = arr[1]; arr[1] = temp;
            return arr;
        }
        else{
            ***RETURN*** reverseArrayInPlace(arr);
            //reverseArrayInPlace (ar2);
        }
    }

I used debugger in chrome navigateur to go step by step and noticed that ar1 was null on your step 1- reverseArrayInPlace([1,5,0]) -> returns the below calls So the result contains only the second part: the reversed second array [6,4]

CodePudding user response：

The missing return statement is the initial problem, but more broadly speaking, this is not a true inplace algorithm, because it still reserves O(n) auxiliary memory by creating new arrays.

For an algorithm to be inplace, there should be no O(n) auxiliary memory usage. Instead make also the splitArray and mergeArray inplace functions, so that at all times there is only one array that is being mutated.

For that to happen, you would need to pass the start/end indices of the subarray that is going to be subject of the split/merge operation.

It is also safer to include the empty-array case in the first base case of splitArray: so use <= 1 instead of === 1.

Here is your code altered with that idea:

let reverseArrayInPlace = (arr, start=0, end=ar.length) => {

    let splitArray = (start, end) => {
        if (end - start <= 1) return;
        if (end - start === 2) {
            let temp = arr[start]; arr[start] = arr[start 1]; arr[start 1] = temp;
        }
        else{
            reverseArrayInPlace(arr, start, end);
        }
    }
 
    let mergeArray = (start, mid, end) => {
        arr.splice(start, 0, ...arr.splice(mid, end - mid));
    }

    let half = (start   end) >> 1;
    splitArray(start, half);
    splitArray(half, end);
    mergeArray(start, half, end);
    return arr;
}

let ar = [1, 5, 0, 4, 6];
console.log(reverseArrayInPlace(ar));

You also don't really need to deal with the second base case separately. The operation will work fine if you deal with that case as a recursive case.

Here is your code altered with that idea:

let reverseArrayInPlace = (arr, start=0, end=ar.length) => {

    let splitArray = (start, end) => {
        if (end - start > 1) reverseArrayInPlace(arr, start, end);
    }
  
    let mergeArray = (start, mid, end) => {
        arr.splice(start, 0, ...arr.splice(mid, end - mid));
    }
  
    let half = (start   end) >> 1;
    splitArray(start, half);
    splitArray(half, end);
    mergeArray(start, half, end);
    return arr;
}

let ar = [1, 5, 0, 4, 6];
console.log(reverseArrayInPlace(ar));