Skip to content

3936. Minimum Swaps to Move Zeros to End

Description

You are given an integer array nums.

In one operation, you can choose any two distinct indices i and j and swap nums[i] and nums[j].

Return an integer denoting the minimum number of operations required to move all 0s to the end of the array.

Β 

Example 1:

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

Output: 2

Explanation:

We perform the following swap operations:

  • Swap nums[0] and nums[3], giving nums = [3, 1, 0, 0, 12].
  • Swap nums[2] and nums[4], giving nums = [3, 1, 12, 0, 0].

Thus, the answer is 2.

Example 2:

Input: nums = [0,1,0,2]

Output: 1

Explanation:

We perform the following swap operations:

  • Swap nums[0] and nums[3], giving nums = [2, 1, 0, 0].

Thus, the answer is 1.

Example 3:

Input: nums = [1,2,0]

Output: 0

Explanation:

The array already satisfies the condition. Therefore, no swap operations are needed.

Β 

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

Solutions

Solution 1: Two Pointers

We use two pointers \(i\) and \(j\) pointing to the beginning and end of the array respectively. Each time, we move \(i\) to the right until we find a 0, and move \(j\) to the left until we find a non-zero number. If \(i < j\), we swap the two elements and increment the answer by 1. We repeat this process until \(i \geq j\).

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def minimumSwaps(self, nums: list[int]) -> int:
        ans = 0
        n = len(nums)
        i, j = 0, n - 1
        while i < j:
            while i < n and nums[i] != 0:
                i += 1
            while j and nums[j] == 0:
                j -= 1
            if i >= j:
                break
            ans += 1
            i += 1
            j -= 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minimumSwaps(int[] nums) {
        int ans = 0;
        int n = nums.length;
        for (int i = 0, j = n - 1; i < j; ++i, --j) {
            while (i < n && nums[i] != 0) {
                ++i;
            }

            while (j > 0 && nums[j] == 0) {
                --j;
            }

            if (i >= j) {
                break;
            }

            ++ans;
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minimumSwaps(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        for (int i = 0, j = n - 1; i < j; ++i, --j) {
            while (i < n && nums[i] != 0) {
                ++i;
            }

            while (j > 0 && nums[j] == 0) {
                --j;
            }

            if (i >= j) {
                break;
            }

            ++ans;
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func minimumSwaps(nums []int) int {
    ans := 0
    n := len(nums)

    for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
        for i < n && nums[i] != 0 {
            i++
        }

        for j > 0 && nums[j] == 0 {
            j--
        }

        if i >= j {
            break
        }

        ans++
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function minimumSwaps(nums: number[]): number {
    let ans = 0;
    const n = nums.length;

    let i = 0;
    let j = n - 1;

    while (i < j) {
        while (i < n && nums[i] !== 0) {
            ++i;
        }

        while (j > 0 && nums[j] === 0) {
            --j;
        }

        if (i >= j) {
            break;
        }

        ++ans;
        ++i;
        --j;
    }

    return ans;
}

Comments