# #8 Move Element To End

###### tags: `Array` `Medium`

## Problem
You're given an array of integers and an integer. Write a function that moves all instances of that integer in the array to the end of the array and returns the array.

The function should perform this in place (i.e., it should mutate the input array) and doesn't need to maintain the order of the other integers.

### Sample Input

array = [2, 1, 2, 2, 2, 3, 4, 2]
toMove = 2

### Sample Output

[1, 3, 4, 2, 2, 2, 2, 2] // the numbers 1, 3, and 4 could be ordered differently

<br>

:::spoiler **Optimal Space & Time Complexity**

O(n) time | O(1) space - where n is the length of the array

:::

<br>

:::spoiler Hint 1
You can solve this problem in linear time.
:::

<br>

:::spoiler Hint 2
In view of Hint #1, you can solve this problem without sorting the input array. Try setting two pointers at the start and end of the array, respectively, and progressively moving them inwards.
:::

<br>

:::spoiler Hint 3
Following Hint #2, set two pointers at the start and end of the array, respectively. Move the right pointer inwards so long as it points to the integer to move, and move the left pointer inwards so long as it doesn't point to the integer to move. When both pointers aren't moving, swap their values in place. Repeat this process until the pointers pass each other.
:::

<br>

<hr/>

## Solutions

### Official

function moveElementToEnd(array, toMove){
    let i = 0;
    let j = array.length - 1;
    while(i < j){
        while(i < j && array[j] === toMove) j--;
        if(array[i] === toMove) swap(i, j. array);
        i++;
    }
    return array
}
function swap(i, j, array){
    const temp = array[j];
    array[j] = array[i];
    array[i] = temp;
}

<br>

---

### Everyone's
#### # Create new array
:::spoiler 月

/* time: O(n)
   space: O(n)
*/
function moveElementToEnd(array,toMove){
  const result = [];
  const len = array.length;
  if(!toMove) return array;
  for(let i = len - 1; i != 0 ;i--){
    if(array[i] === toMove){
      result.push(array[i])
    }else{
      result.unshift(array[i])
    }
  }
  return result
}

:::

<br>

#### # Fast, Slow Pointer
:::spoiler 東

// Time O(n) | Space (1), n is the length of input array
function moveElementToEnd(array, toMove) {
  let slowIdx = 0
  for (let i = 0; i < array.length; i++) {
    const currNum = array[i];
    if (currNum !== toMove){
      array[i] = array[slowIdx];
      array[slowIdx] = currNum;
      slowIdx++;
    }
  }
  return array;
}

:::
<br>

:::spoiler YC

/*
time: O(n) - where n is the length of the array
space: O(1);
*/
function move(array, toMove){
  let left = 0;
  for(let i = 0; i < array.length; i++){
    if(array[i] !== toMove){
      [array[i], array[left]] = [array[left], array[i]];
      left++;
    }
  }  
  return array;
}

:::

<br>

#### # Right, Left Pointer
:::spoiler Raiy

Time O(N).  Space O(2N)? 
 function moveEle(arr , target){
  
   let left = 0;
   let right = arr.length -1; 
   
   for(let i = 0; i <arr.length; i++){
     if((right-i) < (left+i)){
       break;
     }
     if(arr[i+left] === target && arr[right-i] !== target){
      let x = arr[i+left];
      let y = arr[right-i];
      arr[i+left] = y
      arr[right-i] = x
       
     }else if(arr[i+left] === target && arr[right-i] !== target){
       right--;
     }else if(arr[i+left] === target && arr[right-i] === target){
       left--;
     }else{
       right++;
     }
   }
   return arr
 }

:::

<br>

:::spoiler Becky

//time: O(n) | space: O(1)  
function moveElementToEnd(arr, target){
  let len = arr.length;
  let left = 0;
  let right = len-1;
  while( right >= left ){
    if( arr[left] === target ){
      if(arr[right] === target){
        right--;
      }else{
        arr[left] = arr[right];
        arr[right] = target;
        left++;
      }
    }
    else{
      left++;
    }
  }
  return arr;
}

:::

<br>

:::spoiler Hao

const moveElementToEnd = (arr, toMove) => {
  /* O(n) time, O(1) space */
  let leftPointer = 0;
  let rightPointer = arr.length - 1;
  let isleftPointerAnchored = false;
  let isrightPointerAnchored = false;

  const switchArrEls = (arr, idxA, idxB) => {
    const elA = arr[idxA];
    arr[idxA] = arr[idxB];
    arr[idxB] = elA;
    return arr;
  };
  let counter = 0;
  while (rightPointer > leftPointer) {
    if (isleftPointerAnchored && isrightPointerAnchored) {
      switchArrEls(arr, leftPointer, rightPointer);
      isleftPointerAnchored = false;
      leftPointer += 1;
      isrightPointerAnchored = false;
      rightPointer -= 1;
    };
    while (!isleftPointerAnchored) {
      if (arr[leftPointer] === toMove) isleftPointerAnchored = true;
      else leftPointer += 1;
    }
    while (!isrightPointerAnchored) {
      if (arr[rightPointer] !== toMove) isrightPointerAnchored = true;
      else rightPointer -= 1;
    }
  };
  return arr;
};

:::

<br>
:::spoiler SOL

const moveElementToEnd = (array, toMove) => {
  // O(n) time | O(1) space
  let rightIdx = array.length - 1;
  let leftIdx = 0;
  while (rightIdx > leftIdx) {
    if (array[rightIdx] === toMove) {
      rightIdx--;
    } else if (array[leftIdx] !== toMove) {
      leftIdx++;
    } else {
      array[leftIdx] = array[rightIdx];
      array[rightIdx] = toMove;
    }
  }
  return array;
};

:::

---

## Supplement / Discussion

// Reduce if/else use
while(i < j && array[j] === toMove) j--;

// No need for additional variables to access value
[array[i], array[left]] = [array[left], array[i]]