O(n) time O(1) space Java solution using a pivot to partition


  • 5
    Z

    Idea is to partition the array into two around a pivot such that all zeros are on right and everything else are on left side of the partition.

    public class Solution {
        private void swap(int[] nums, int i, int j){
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
        }
        public void moveZeroes(int[] nums) {
            int left = -1, i = 0, n = nums.length;
            
            while(i < n){
                if(nums[i] != 0){
                    if(left != -1){
                        swap(nums, i, left);
                        left++;
                    }
                }
                else if(left == -1){
                        left = i;
                }
                
                i++;
            }
        }
    }

Log in to reply
 

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