Minimum Operations to Make Binary Array Elements Equal to One I - Leetcode 3191 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
6:11 - Coding Explanation

leetcode 3191

#neetcode #leetcode #python

[saarthak]

We can use XOR to flip the numbers instead of using a ternary operator, we can simply XOR the existing value with 1, meaning -> ( 0 ^ 1 = 1), ( 1 ^ 1 = 0)

[rickliang]

Also it's technically unncessary to flip nums[i].

[emilturbo]

I mean, the sliding window approach also works and is pretty efficient. We just iterate through the array within the algorithm, starting at index 2, because we need to flip specific triplets from 0 to 1 and from 1 to 0. What we do here is check throughout each iteration if the first element of a given triplet between i - 2 and i has a bit value of 0, where we then flip the bits within the triplet until we have gotten to the end of the array. Then we iterate through the modified array again to check if the sum of the bit values equal to the length of the array, returning the number of operations as count variable, otherwise returning - 1.

TL;DR, yes, Sliding Window also works when you understand how to work with the XOR operations

[Balachiang]

I just recently got really into coding and I am on your 1 year membership. Let's see how good I get after 1 year of solid training with your resources. Cheers 🥂

[animeboomer]

class Solution:
def minOperations(self, nums: List[int]) -> int:
n=len(nums)
operations=0
for i in range(n-2):
if nums[i]==0:
nums[i]^=1
nums[i+1]^=1
nums[i+2]^=1
operations+=1
if nums[-1]==0 or nums[-2]==0:
print(nums[-1])
return -1
return operations how this would run using xor operator

[prajwals]

I was thinking of some convoluted counting, math, bit-manipulation solution until I saw your video's duration....
Then I just went and did the greedy thing, and my life is so much better now

[ronbuchanan]

Hey NeetCode,
Thanks for the explanation but I feel it was somewhat handwaving.
I feel like you've based yourself as a leading YouTube channel for LeetCode interview questions. I think your next leap should be creating a little bit more of added value to the viewers. For example, I'd be so much happy if you gave a semi-formal proof of why greedy works here (and maybe viewers that don't care about it can skip to the code).

[vinayaksai_akula]

class Solution(object):
def minOperations(self, nums):
res=0
for i in range(len(nums)-2):
if nums[i]==0:
nums[i]^=1
nums[i+1]^=1
nums[i+2]^=1
res+=1
return res if len(nums)==sum(nums) else -1--> hey neetcode i coded better today because of you and your explantion but in adiffernt approch a small think and relating to the next problem😝😝😝 feeling happy

[Mafematic]

Thank you for your great videos, they are helping me a lot. Maybe one addition here that is interesting. You are not returning anything from inside your flip function, still you are altering the original list. In case anyone wonders how?!, this is called pass by reference, very common in C++, but not as obvious in Python. So you are altering the original datastructure here, which is the original nums list, because it is mutable. This wouldn't work for integers or strings e.g., cool to see that you used it. :)

[anirudhkashyap]

As soon as i saw the first hint, it was pretty clear that you start from the first element and you have one choice
Do you think its fine to look at the hint after being stuck for like 5-10 mins?

[alifrahman]

thats crazy i litearlly went through the exact same thought process

[shahukor]

Same approach but without using any helper function, and some slight changes :
class Solution:
def minOperations(self, nums: List[int]) -> int:
count = 0
for i in range(len(nums)):
if nums[i]==0:
if i+2>=len(nums):
return -1
nums[i] = 1
nums[i+1] = 1 - nums[i+1]
nums[i+2] = 1 - nums[i+2]
count+=1
return count

[baifriend]

It is a solution, but how do you know it's the minimum flips?

[rimshakhan]

How about just doing
nums[i+1] = 1 - nums[i+1]
nums[i+2] = 1 - nums[i+2]
instead of making a new function for flipping

[cjw]

Using ^ operator to flip will have better performance

[Oliver-ntpw]

I kind of miss some explanation on how to prove that greedy works. I come up with the greedy idea immediately, but then i felt like there must be something that i am missing :(

[CodeRapPlay]

i have implemented the same thing what;s the issue
class Solution {
public void flip(int[] nums, int i) {
nums[i] = (nums[i] == 0) ? 1 : 0;
}

public int minOperations(int[] nums) {
int res = 0;
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] == 0) {
flip(nums, i);
flip(nums, i + 1);
flip(nums, i + 2);
res++;
}
}


if(nums[nums.length - 2] != 0 || nums[nums.length - 1] != 0) {
return -1;
}
return res;
}

}

[gustavgille]

I did a two pointer method, slower but similar logic

[olegkot]

Where is a proof that this is minimal amount of operations?

[ankit]

1st ever question In leetcode that i solved it my own😅