0

I was trying to solve a problem:

Problem:

Given an array of Positive repetitive numbers. Output should give an array with odds sorted on the right and evens on the left (no particular order)

Input : [4,1,2,3,4]

Output: [4,2,3,1]

Solve it In-place and without using extra space and O(N) runtime.

Code:

/*
 * Algorithm is simple, have two pointers one on the left and another on the right.
 * Note: We are sorting all evens on the left and odds on the right
 * If you see even on left, move on else swap.
 */

function groupNumbers(intArr) {
    
    if(intArr.length == 0 || intArr.length == 1){
        return intArr;
    }

    for(let i=0, j =intArr.length-1; i<intArr.length; i++){
        if(j>=i){ //elements should not overlap
            let start = intArr[i];
            let end = intArr[j];
            
        
            if(start%2 == 0){ //Even
                i++;
            } else {
                [start, end] = [end, start]; //swap
            }
            
            
            if(end%2 == 1){
                j--;
            } else {
                [start, end] = [end, start]; //swap
            }

        } //if-ends
            
    }//for-ends
    
    return intArr;
}

I'm not sure where I'm going wrong. I'm missing something. I'm getting the same sorted array as output.

Condition: **SOLVE it INPLACE and without using extra space ** (Preferably in ONE iteration)

Improve this question
8
  • 1
    While this is a totally legit question, this kind of thing should just about never be done in JavaScript. Array.prototype.sort is implemented in C++ and will almost certainly be faster, even with a custom sorting function passed in, than anything you will write. Commented Aug 13, 2017 at 0:28
  • can you please explain.. why? When I'm not sorting anything instead just using two pointers to swap stuff. @JaredSmith please enlighten me in this case. I want to learn more Commented Aug 13, 2017 at 3:05
  • There are lots of languages called "scripting" languages, but JavaScript really is one: it's meant to script a host environment. As such there's a lot of overhead involved in running JavaScript, even if it looks like C: there are bounds checks, primitive boxing/unboxing, interfacing to the runtime, etc. And mutating the array directly may in some cases be slower than making a new one because it can change the "shape" repeatedly causing a bunch of memory allocations rather than potentially just one to hold the new array. Then you get into size issues: for arrays of length n you... Commented Aug 13, 2017 at 21:13
  • should mutate, and for arrays with length > n you should make a new one, and the value of n is different for every browser. Well you know who knows all of that and the details of each particular implementation of the runtime? The vendor does. So they give you a highly optimized sort method, written in C++ and compiled to native code, that does the correct thing if the array is small, large, sparse, etc. Use it. Commented Aug 13, 2017 at 21:16
  • If you re-create the array O(N) for every element (N). The time complexity is O(N^2). If I manipulate the array, that wil be much better operation than re-creating the array everytime (Slice/Splice). Please refer to "Thomas" solution on the bottom. All I was doing was swapping stuff (Isn't it how quicksort is done in ANY language?) Commented Aug 14, 2017 at 14:58

2 Answers 2

Reset to default
1

I'm not sure where I'm going wrong. I'm missing something. I'm getting the same sorted array as output.

several things:

let start = intArr[i];
let end = intArr[j];
...
[start, end] = [end, start];

this does indeed swap the values in the variables start and end, but not the indices in the Array.

Then you have two i++ in the same loop that increment the left pointer.

if(start%2 == 0){ //Even
    i++;
} else {
    [start, end] = [end, start]; //swap
}

here you swap the items when the left pointer points to an odd value, but there's no check that the right pointer also points to an even value. you might as well just swap two odd values here. Same for the right pointer.

const isEven = v => (v&1) === 0;
const isOdd = v => (v&1) === 1;

function groupNumbers(arr){
  var left = 0, right = arr.length-1;
  while(left < right){
    //move the left pointer to find the next odd value on the left
    while(left < right && isEven(arr[left])) ++left;

    //move the right pointer to find the next even value on the right
    while(left < right && isOdd(arr[right])) --right; 

    //checking that the two pointer didn't pass each other
    if(left < right) {
      console.log("swapping %i and %i", arr[left], arr[right]);
      //at this point I know for sure that I have an odd value at the left pointer 
      //and an even value at the right pointer

      //swap the items
      var tmp = arr[left];
      arr[left] = arr[right];
      arr[right] = tmp;
    }
  }
  return arr;
}


[
  [1,2,3,4],
  [1,2,3,4,5,6,7,8,9,0],
  [1,3,5,7],
  [2,4,1,3],
  [5,4,3,2,1],
].forEach(sequence => {
  console.log("\ninput: " + sequence);
  console.log("output: " + groupNumbers(sequence));
});
.as-console-wrapper{top:0;max-height:100%!important}

as suggested by @JaredSmith, the same thing just using a sort-function :)

function sortEvenLeftOddRight(a,b){
  return (a&1) - (b&1);
  //return (a&1) - (b&1) || a-b;  //to additionally sort by value
}

[
  [1,2,3,4],
  [1,2,3,4,5,6,7,8,9,0],
  [1,3,5,7],
  [2,4,1,3],
  [5,4,3,2,1],
].forEach(sequence => {
  console.log("\ninput: " + sequence);
  sequence.sort(sortEvenLeftOddRight);
  console.log("output: " + sequence);
});
.as-console-wrapper{top:0;max-height:100%!important}

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Thank you so much! This is amazing!
can you explain what you meant by this? this does indeed swap the values in the variables start and end, but not the indices in the Array Isn;t [a,b] = [b,a] as good as the swap code you have written? What do you mean by swap the indices? Sorry I'm not super clear here.
@TechnoCorner a = arr[i], b = arr[j] "copies" the values from the Array into two variables. If you now do [a,b] = [b,a] it switches the values in these variables, but NOT in the Array. And since you never do something to store these changes back to the Array, like arr[i] = a, arr[j] = b, the swapping is pointless.
Well, this is incorrect @Thomas. Please check this link: https://repl.it/KJuX if you use ES6 [] operator, it actually swaps the value (even in an array) so it's kinda redundant to write those 3 LOC when you can make it one :-D
@TechnoCorner the point is not wether you can or can't use destructuring to swap values in an Array. the point is that you are swapping two variables that reference the values from the Array, and expect the values in the Array to be swapped too. [start, end] = [end, start] doesn't do [intArr[i], intArr[j]]= [intArr[j], intArr[i]]. And I use these three lines instead of the one because performance. Array destructuring has an overhead and I don't want to use it in a loop that may potentially run hundreds or thousands of times per function call. Not if I get so little out of using it.
0

A very concise method to solve this would be to use reduce:

const out = arr.reduce((p, c) => {

  // if the value is divisible by 2 add it
  // to the start of the array, otherwise push it to the end
  c % 2 === 0 ? p.unshift(c) : p.push(c)
  return p;
}, []);

OUT

[4,2,4,1,3]

DEMO

Improve this answer

1 Comment

Can we solve this without extra space? I.e creating new array. Please keep this solution, I want to read and understand it but I'd prefer the solution INPLACE and without extra space.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.