package algoexpert.medium;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

/*

PROBLEM:

Given array and elem, move all instances of elem to end without using extra space.

EXAMPLE:

[2,1,2,2,2,3,4,2] -> [1,3,4,2,2,2,2,2] (1,3 & 4 can be in any order)

SOLUTION:

1. using pointers -> time : O(n) | space : O(1)

*/

public class MoveToEnd

{

public static void test()

{

ArrayList<Integer> array = new ArrayList<> (Arrays.asList(2,1,2,2,2,3,4,2));

System.out.println(moveElementToEnd(array, 2));

}

// time : O(n) | space : O(1)

public static List<Integer> moveElementToEnd(List<Integer> array, int toMove)

{

int lastNonElem = array.size() - 1;

int front = 0;

while (front < lastNonElem)

{

while(lastNonElem > front && array.get(lastNonElem) == toMove) { lastNonElem -= 1; }

if (array.get(front) == toMove)

{

array.set(front, array.get(lastNonElem));

array.set(lastNonElem, toMove);

}

front += 1;

}

return array;

}

}