283. Move Zeroes

Description

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 <= 10⁴
• -2³¹ <= nums[i] <= 2³¹ - 1

Follow up: Could you minimize the total number of operations done?

💡 Hint 1:
In-place means we should not be allocating any space for extra array. But we are allowed to modify the existing array. However, as a first step, try coming up with a solution that makes use of additional space. For this problem as well, first apply the idea discussed using an additional array and the in-place solution will pop up eventually.
💡 Hint 2:
A two-pointer approach could be helpful here. The idea would be to have one pointer for iterating the array and another pointer that just works on the non-zero elements of the array.

Submitted Code

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        zero = 0                    # 0인 값의 인덱스 저장

        for i in range(len(nums)):  # i로 리스트 순회
            if nums[i] != 0 and nums[zero] == 0:  # i 위치 값이 0이 아니고 zero 위치 값이 0일 경우에만
                nums[zero], nums[i] = nums[i], nums[zero]     # 두 값의 위치 변경
            
            if nums[zero] != 0:     # zero 위치의 값이 0이 아니면 다음 0을 찾기 위해 이동
                zero += 1

Runtime: 3 ms | Beats 90.11%
Memory: 13.70 MB | Beats 34.74%

nums = [0, 1, 0, 3, 12]

i    zero    nums[i]    nums[zero]  →  nums               zero
0    0        0         0              [0, 1, 0, 3, 12]   
1    0        1         0              [1, 0, 0, 3, 12]   +1
2    1        0         0
3    1        3         0              [1, 3, 0, 0, 12]   +1
4    2       12         0              [1, 3, 12, 0, 0]   +1

nums = [1, 3, 12, 0, 0]

Other Solutions

1st

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        left = 0

        for right in range(len(nums)):
            if nums[right] != 0:
                nums[right], nums[left] = nums[left], nums[right]
                left += 1
        
        return nums

time complexity: 𝑂(𝑛)
space complexity: 𝑂(1)

right의 값이 0이 아니면 자기 자신과 스왑하기 때문에 조금 더 불필요한 과정이 있게 된다.