283. Move Zeroes

Type: Easy
Liked by 15.2K
Disliked by 380.

Companies that asked this question
Companies: No of times asked
Yandex 8
Apple 3
Amazon 3
Facebook 11
Bloomberg 6
Google 4
Adobe 3
Microsoft 2
Uber 2
Oracle 2
Splunk 2
Tesla 2
tcs 6
Expedia 4
VMware 3
Goldman Sachs 3
ByteDance 3
JPMorgan 3
TikTok 3
LinkedIn 2
Yahoo 2
IBM 2
Morgan Stanley 2
ServiceNow 2
Salesforce 2
Zoho 2
Infosys 2
Nvidia 2
Samsung 2
Wix 1

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.

Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:
Input: nums = [0]
Output: [0]

Constraints:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

Intuition

We want to move all the zeros to the end of the array while keeping the non-zero elements in their relative order.

Approach

We maintain two pointers: i to iterate through the array and nonZeroIndex to keep track of the position where we should insert non-zero elements. When we encounter a non-zero element, we swap it with the element at nonZeroIndex and then increment nonZeroIndex.

Complexity

Time complexity:
The code iterates through the array once, so the time complexity is O(n), where n is the length of the array.

Space complexity:
The code uses a constant amount of extra space, so the space complexity is O(1).

Code

class Solution {
    public void moveZeroes(int[] nums) {
        int nonZeroIndex = 0; 
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int temp = nums[i];
                nums[i] = nums[nonZeroIndex];
                nums[nonZeroIndex] = temp;
                nonZeroIndex++; 
            }
        }
    }
}

Happy coding,
shiva