LeetCode 3191. Minimum Operations to Make Binary Array Elements Equal to One I

This question has not been asked by a lot of organisations, but tests your conceptual thinking and algorithmic knowledge of sliding window algorithm.

The only hint you need is that to convert the first 0 to 1, you’ll need to flip all 3 numbers. And then you need to check if the next number is zero, if it is then you’ll need to again flip the 3 digits. At the end of this you’ll then check if the sum of the array is equal to its length. If that’s the case, then you’ve your answer. Otherwise you can’t make all elements equal to 1 and you should return -1.

For example.

[0,1,1,1,0,0] -> [1,0,0,1,0,0] -> [1,1,1,0,0,0] -> [1,1,1,1,1,1]

In the above example we needed 3 operations to make the array elements equal to one.

[0,1,1,1] -> [1,0,0,1] -> [1,1,1,0]

In this example you can see that we can’t flip the last 0 only, if we do so then the 1s before it will become zero. So if we traverse the list, we can never get all the elements of the array to become 1. In this example we will return -1.

Below is the solution to the problem.

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        i = 0
        num_op = 0
        for i in range(2,len(nums)):
            if nums[i-2] == 0:
                num_op+=1
                nums[i-2] = nums[i-2]^1
                nums[i-1] = nums[i-1]^1
                nums[i] = nums[i]^1

        if sum(nums) == len(nums):
            return num_op
        else:
            return -1

The time complexity is O(n) as we do traverse through the entire array. The space complexity is O(1) as we only store variables like i and num_op which take constant space.