You are 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.

Overview

Naive Solution

Thinking about this, what could we do? We can sort the array, but there isn’t a clear path on how to solve this. Even if we were to solve it with sorting, the time complexity would be O(nlog(n)).

We know we are going to iterate through the array, it feels like we can solve it in linear time, O(n).

Optimal Solution

Flow Diagram

Using sort or any other data structure doesnt seem to help. In place swapping of the array and iterating through it with two indexes is the way to go.

Time Complexity

As we are traversing the whole array once, the time complexity is O(n). The swapping is a straightforward operation in constant time.

Space Complexity

All swaps are done in place and no extra memory is requiered for this algorithm, this leads us to a constant space of O(1), sweet.

Java Source Code

    public int[] move(int[] array, int toMove) {
        var i=0;
        var j = array.length-1;

        while(i < j) {
            while(i<j && array[j] == toMove) {
                j--;
            }

            if(i<j && array[i] == toMove) {
                AlgoUtils.swap(i,j,array);
            }

            i++;
        }
        return array;
    }

Conclusion

Don’t swap horses midstream.

Abraham Lincoln