LeetCode 283. Move Zeroes

Problem

Move Zeroes - LeetCode

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Analysis

• To rearrange the array in place, we can use Quick Sort.
• Consider 0 as the pivot
  - all values other than 0 are moved to the left of the pivot
  - all values equals to 0 are moved to the right of the pivot
• So that we maintain the relative order of the non-zero elements after the rearranement.

Solution

var moveZeroes = function(nums) {
    function _swap (arr, i, j) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    
    let pivotIdx = 0;
    for (let i = 0; i < nums.length;i++) {
        if (nums[i] !== 0) {
            _swap(nums, pivotIdx, i);
            pivotIdx++;
        }    
    }
};

Quick Sort tutorial

Quick Sort — Javascript implementation