DDSA Solutions

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

MediumView on LeetCode
ArrayBit ManipulationGreedyQueue
Time: O(n)
Space: O(1)

Problem Overview

Minimum operations to make binary array all ones: each op flips 3 consecutive elements.

Intuition

Minimum operations to make binary array all ones: each op flips 3 consecutive elements. Greedy left-to-right.

Algorithm

  1. 1Scan left to right. When nums[i]==0: flip nums[i], nums[i+1], nums[i+2]. Count flips.
  2. 2If i+2 >= n when flip needed: return -1.

Common Pitfalls

  • •Greedy: flip at leftmost 0. If cannot flip (near end): impossible. O(n) solution.
3191.cs
C#
// Approach: Greedy sliding window of size 3; flip starting at each 0.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MinOperations(int[] nums)
    {
        int n = nums.Length, ans = 0;

        for (int i = 0; i < n - 2; i++)
        {
            if (nums[i] == 1)
                continue;

            for (int j = i; j <= i + 2; j++)
                nums[j] = nums[j] ^ 1;

            ans++;
        }

        if (nums[n - 1] == 0 || nums[n - 2] == 0)
            return -1;

        return ans;
    }
}
Was this solution helpful?

Related Problems