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


  • 0
    D

    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;
    

    }


  • 0
    S

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


  • 0
    D

    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)


Log in to reply
 

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