Java: Detect Blocks of Contiguous Zeros Then Move


  • 0
    O

    There are more succinct and efficient solutions on the discussion board but in case someone is looking for alternative means to the end, here we go...

    • Initialize two cursors, one for each end of the array.
    • While both cursors have not met.
    • Move the end cursor past zeros.
    • If the start cursor points to a zero, detect other contiguous zeros and move the block.
    • Advance the start cursor.

    One could argue that the block movement should not be amortized and it should be possible to construct corner cases that trigger bad polynomial behavior e.g a very long alternating sequence of 1,0,1,0,... But hey, the solution works here. :)

    public class Solution {
        public void moveZeroes(int[] nums) {
            if (nums.length <= 1) return;
            int start = 0, end = nums.length - 1;
            while (start < end) {
                while (nums[end] == 0) if (--end <= start) return;
                if (nums[start++] == 0) {
                    int lo = start-1, hi = lo;
                    while (nums[++hi] == 0) ;
                    if (hi <= end) end = move(nums, lo, hi, end);
                }
            }
        }
    
        private int move(int[] nums, int lo, int hi, int end) {
            System.arraycopy(nums, hi, nums, lo, end - hi + 1);
            int zeroStart = end - hi + lo + 1;
            Arrays.fill(nums, zeroStart, end + 1, 0);
            return zeroStart;
        }
    }

Log in to reply
 

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