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

Thinking

\(n\le 100\), so simulating swaps of a zero with a later nonzero is fine. The goal is to send every zero to the suffix; order among zeros or among nonzeros does not matter.

Two pointers from the ends: the left seeks a \(0\), the right seeks a nonzero, and a crossing pair is one swap. Each index is chosen at most once.

The swap count is the number of such zero–nonzero pairs, obtained in one scan.

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)\).

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

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
}

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;
}

3936. Minimum Swaps to Move Zeros to End

Description

Solutions

Solution 1: Two Pointers

Comments