O(n) solution using QuickSort partition (1 ms)

• This is my O(n) solution, it is similar to QuickSort partition.
Checking all elements in the array, if a zero is found, swap it with the next non-zero element and save the index of the element so next time when we need to find a non-zero we can continue from there.

``````public void moveZeroes(int[] nums) {
int indexOfNextNonZero = 0;
for (int i = 0 ; i < nums.length; i++)
{
if (i == indexOfNextNonZero)
indexOfNextNonZero++;
if (nums[i] == 0)
{
indexOfNextNonZero = findNextNonZero(nums,indexOfNextNonZero);
if (indexOfNextNonZero != -1)
swap(nums,i,indexOfNextNonZero);
else break;
}

}
}
private static int findNextNonZero(int[] nums, int i)
{
while (i < nums.length)
{
if (nums[i] != 0) return i;
i++;
}
return -1;
}
private static void swap(int[] nums, int i, int j)
{
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
``````

}

• This is not O(n), but O(n^2)!!!

• You got 2 pointers that go through the array once, indexOfNextNonZero isn't going back at all, it continues from the last place it has stopped -> O(n)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.