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

NeetCodeIO · Intermediate ·⚡ Algorithms & Data Structures ·1y ago

Key Takeaways

The video demonstrates solving the Leetcode 3191 problem, Minimum Operations to Make Binary Array Elements Equal to One I, using a greedy algorithm and a sliding window approach in Python.

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve the problem minimum operations to make binary array elements equal to one I guess that's the first variation of this problem but anyways idea is pretty simple we're given an array that consists of zeros and ones so it's a binary array the first example looks like this and we want to transform this into an array that is all ones so that would look like this we're only allowed to do that by changing three contiguous elements at a time so we could change these three or we could change these three or we could change these three or we could change these three you're probably thinking I'm going kind of slow so far and I guess to be honest I'm kind of deliberately slowing myself down because as soon as I saw this problem and as soon as I finished reading the description it became pretty uh clear to me how to solve this problem because first of all that three consecutive element thing I mean it just looks like a sliding window so maybe they're trying to trip us up but I went for it anyway I went for the bait that they gave us it seems like a sliding window problem let me just see if maybe there's a sliding window solution well it seems though that maybe it would involve backtracking right maybe some of you thought that this could be a backtracking problem I thought that's definitely possible if I can't find a sliding window Solution that's going to be the next thing I probably consider but then I asked myself because with backtracking like if I flip this window that might not be the correct decision maybe we're not supposed to flip this window maybe we're supposed to flip the next window like this how do you know it seems like we have no way of knowing right well then the idea came to my mind there's probably a trick behind it that made me think along the lines of greedy and then I saw it immediately do you see it because I see it take a look at this if I want to flip this bit well I probably wouldn't want to flip it it's already a one but if I did want to flip it well I could do this window or I could do this window over here that also includes the guy or I could do this window over there all three Windows include this middle element if I wanted to flip it I could choose three different Windows my God this seems pretty complicated right no I promise you it's not complicated because greedy is going to help us because consider this what about the guy over here how many different Windows does he get to choose from only a single one so now you tell me is there actually three choices or maybe there's actually just two choices or actually maybe there's just one choice and that's what I'm here to tell you there's really only one choice and the idea is this if this is a zero there's only one way to flip it into a one I only have one choice I have to do this window I have no other choice now of course you might be thinking well if I end up turning this into a one that kind of sucks because then I have to turn these or or these two into zeros and you're right it does suck but it was necessary and it's okay because now we can flip the next window as well because we're going to assume that everything before our current pointer is already one don't touch any of that because it's already good and we had to flip that bit so now everything before this line is good I mean we could if we wanted to we could go back for some reason and do another flip but I mean why would we do that why would we want to unset some of these bits why would we want to basically undo the work that we already did we wouldn't so we don't touch anything before that line and now we have a sub problem this is the rest of the array how many flips is it going to take to make this thing zero well once again just go greedy just look at the current element only if this is zero well nothing else matters it has to be flipped we have to do this this specific window it has to be because we're not going to touch anything before and we don't want to do this window that doesn't include this guy so we have to include this window we flip it we don't care about what happens to these two well we do care but it's not going to change the result then we might have to flip those we might not so now we look at this window we flip it as well we end up uh getting a one here and a one here and then a zero here and then our ey pointer will be over here now we'll look at the next window well specifically only this element it's one so we're good go to the next iteration now our ey pointer is going to be over here we look at this window this guy is a zero so once again we are done we do the flip this is one and this is one and this is one and we would stop once there's not at least three elements remaining in the array but this is where you might get ripped up a little bit how do we know if there was actually a valid answer because they tell us if it's not possible we should return1 well think about this for a second if I had an array that looked like this I have four ones and then a couple zeros and the window we have is of size three I mean it's literally not possible to do this I mean I guess we could flip this window but we'd basically just be turning this into a zero and then these into ones so this is a solution I'm to go ahead and code up this is the sliding window solution I think it's the most optimal one it is linear time and constant space I don't think we can do much better than that but now that I think of it I'm starting to realize there might be an alternative solution I feel like if there was ever a case where I don't know if I'm going to continue with this but if there was ever a case where we had less than three consecutive ones or greater than three that wasn't like a multiple of three it just wouldn't work but I guess I'm not 100% sure I think they're actually probably as some counter examples to that like maybe like three Zer two ones three more zeros and then another one something like that but anyways just some random thought that I had let's code this up now so what I'm going to do is have my result that's going to count the number of operations that's what we're going to return and I don't know why my code syntax highlighting isn't working okay just needed to refresh but then we're going to go through every index in the input and I'm going to do it like this take the length of the array and subtract two from it and then I'm going to check if the current number at index I is equal to zero well then we perform a flip and we're going to have to increment our result off the top of my head I feel like a helper function might be useful for the flip so I'm going to do something like this passing in the nums array which we probably don't have to do but definitely should pass in the index that we want to flip and then I can just update nums at index I and flip it with a turn are operator so zero if the number is non zero otherwise it will be set to one and so then here I can just call flip on nums passing in I passing in I + 1 and passing in I + 2 and then after all of that well now I just kind of realized that I forgot to mention how we know if it's invalid um so since we're doing all the ones up front we know that it's invalid because we will stop two elements before the end so we want to look at the last two elements it's possible that they're both zero CU we didn't flip them we didn't even look at them if they're both zero then obviously we return ne1 if one of them is zero but the other one isn't zero still we return ne1 because we're never going to be able to flip this guy alone or two of these alone we have to do three at a time but if they're both one then we are good so that's the idea here so we'll say if not nums at1 in Python that gives us the last element or not nums at -2 in Python that gives us the second to last element in this case we return ne1 and we're guaranteed that at least two elements are going to exist in the nums array so we don't need to check the length or anything like that and this is the whole code of course I don't even know how I did that but I made it a plural for some reason flips should be flip and you can see here that it works and I promise you that it's pretty efficient this was the other time that I ran it guess the memory kind of varies a bit maybe I think the extra function call probably added a little bit of overhead but anyways if you found this helpful check out n code. for a lot more thanks for watching and I'll see you soon

Original Description

🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews 🧑‍💼 LinkedIn: https://www.linkedin.com/in/navdeep-singh-3aaa14161/ 🐦 Twitter: https://twitter.com/neetcode1 ⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf Problem Link: https://leetcode.com/problems/minimum-operations-to-make-binary-array-elements-equal-to-one-i/description 0:00 - Read the problem 0:30 - Drawing Explanation 6:11 - Coding Explanation leetcode 3191 #neetcode #leetcode #python
Watch on YouTube ↗ (saves to browser)
Sign in to unlock AI tutor explanation · ⚡30

Playlist

Uploads from NeetCodeIO · NeetCodeIO · 0 of 60

← Previous Next →
1 Leetcode 149 - Maximum Points on a Line - Python
Leetcode 149 - Maximum Points on a Line - Python
NeetCodeIO
 2 Design Linked List - Leetcode 707 - Python
Design Linked List - Leetcode 707 - Python
NeetCodeIO
 3 Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
NeetCodeIO
 4 Design Browser History - Leetcode 1472 - Python
Design Browser History - Leetcode 1472 - Python
NeetCodeIO
 5 Number of Good Paths - Leetcode 2421 - Python
Number of Good Paths - Leetcode 2421 - Python
NeetCodeIO
 6 Flip String to Monotone Increasing - Leetcode 926 - Python
Flip String to Monotone Increasing - Leetcode 926 - Python
NeetCodeIO
 7 Maximum Sum Circular Subarray - Leetcode 918 - Python
Maximum Sum Circular Subarray - Leetcode 918 - Python
NeetCodeIO
 8 Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
NeetCodeIO
 9 Concatenated Words - Leetcode 472 - Python
Concatenated Words - Leetcode 472 - Python
NeetCodeIO
 10 Data Stream as Disjoint Intervals - Leetcode 352 - Python
Data Stream as Disjoint Intervals - Leetcode 352 - Python
NeetCodeIO
 11 LFU Cache - Leetcode 460 - Python
LFU Cache - Leetcode 460 - Python
NeetCodeIO
 12 N-th Tribonacci Number - Leetcode 1137
N-th Tribonacci Number - Leetcode 1137
NeetCodeIO
 13 Best Team with no Conflicts - Leetcode 1626 - Python
Best Team with no Conflicts - Leetcode 1626 - Python
NeetCodeIO
 14 Greatest Common Divisor of Strings - Leetcode 1071 - Python
Greatest Common Divisor of Strings - Leetcode 1071 - Python
NeetCodeIO
 15 Shortest Path in a Binary Matrix - Leetcode 1091 - Python
Shortest Path in a Binary Matrix - Leetcode 1091 - Python
NeetCodeIO
 16 Insert into a Binary Search Tree - Leetcode 701 - Python
Insert into a Binary Search Tree - Leetcode 701 - Python
NeetCodeIO
 17 Delete Node in a BST - Leetcode 450 - Python
Delete Node in a BST - Leetcode 450 - Python
NeetCodeIO
 18 Shuffle the Array (Constant Space) - Leetcode 1470 - Python
Shuffle the Array (Constant Space) - Leetcode 1470 - Python
NeetCodeIO
 19 Fruits into Basket - Leetcode 904 - Python
Fruits into Basket - Leetcode 904 - Python
NeetCodeIO
 20 Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
NeetCodeIO
 21 Naming a Company - Leetcode 2306 - Python
Naming a Company - Leetcode 2306 - Python
NeetCodeIO
 22 As Far from Land as Possible - Leetcode 1162 - Python
As Far from Land as Possible - Leetcode 1162 - Python
NeetCodeIO
 23 Shortest Path with Alternating Colors - Leetcode 1129 - Python
Shortest Path with Alternating Colors - Leetcode 1129 - Python
NeetCodeIO
 24 Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
NeetCodeIO
 25 Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
NeetCodeIO
 26 Contains Duplicate II - Leetcode 219 - Python
Contains Duplicate II - Leetcode 219 - Python
NeetCodeIO
 27 Path with Maximum Probability - Leetcode 1514 - Python
Path with Maximum Probability - Leetcode 1514 - Python
NeetCodeIO
 28 Add to Array-Form of Integer - Leetcode 989 - Python
Add to Array-Form of Integer - Leetcode 989 - Python
NeetCodeIO
 29 Unique Paths II - Leetcode 63 - Python
Unique Paths II - Leetcode 63 - Python
NeetCodeIO
 30 Minimum Distance between BST Nodes - Leetcode 783 - Python
Minimum Distance between BST Nodes - Leetcode 783 - Python
NeetCodeIO
 31 Design Hashmap - Leetcode 706 - Python
Design Hashmap - Leetcode 706 - Python
NeetCodeIO
 32 Range Sum Query Immutable - Leetcode 303 - Python
Range Sum Query Immutable - Leetcode 303 - Python
NeetCodeIO
 33 Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
NeetCodeIO
 34 Middle of the Linked List - Leetcode 876 - Python
Middle of the Linked List - Leetcode 876 - Python
NeetCodeIO
 35 Course Schedule IV - Leetcode 1462 - Python
Course Schedule IV - Leetcode 1462 - Python
NeetCodeIO
 36 Single Element in a Sorted Array - Leetcode 540 - Python
Single Element in a Sorted Array - Leetcode 540 - Python
NeetCodeIO
 37 Capacity to Ship Packages - Leetcode 1011 - Python
Capacity to Ship Packages - Leetcode 1011 - Python
NeetCodeIO
 38 IPO - Leetcode 502 - Python
IPO - Leetcode 502 - Python
NeetCodeIO
 39 Minimize Deviation in Array - Leetcode 1675 - Python
Minimize Deviation in Array - Leetcode 1675 - Python
NeetCodeIO
 40 Longest Turbulent Array - Leetcode 978 - Python
Longest Turbulent Array - Leetcode 978 - Python
NeetCodeIO
 41 Last Stone Weight II - Leetcode 1049 - Python
Last Stone Weight II - Leetcode 1049 - Python
NeetCodeIO
 42 Construct Quad Tree - Leetcode 427 - Python
Construct Quad Tree - Leetcode 427 - Python
NeetCodeIO
 43 Find Duplicate Subtrees - Leetcode 652 - Python
Find Duplicate Subtrees - Leetcode 652 - Python
NeetCodeIO
 44 Sort an Array - Leetcode 912 - Python
Sort an Array - Leetcode 912 - Python
NeetCodeIO
 45 Ones and Zeroes - Leetcode 474 - Python
Ones and Zeroes - Leetcode 474 - Python
NeetCodeIO
 46 Remove Duplicates from Sorted Array II - Leetcode 80 - Python
Remove Duplicates from Sorted Array II - Leetcode 80 - Python
NeetCodeIO
 47 Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
NeetCodeIO
 48 Concatenation of Array - Leetcode 1929 - Python
Concatenation of Array - Leetcode 1929 - Python
NeetCodeIO
 49 Symmetric Tree - Leetcode 101 - Python
Symmetric Tree - Leetcode 101 - Python
NeetCodeIO
 50 Check Completeness of a Binary Tree - Leetcode 958 - Python
Check Completeness of a Binary Tree - Leetcode 958 - Python
NeetCodeIO
 51 Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
NeetCodeIO
 52 Find Peak Element - Leetcode 162 - Python
Find Peak Element - Leetcode 162 - Python
NeetCodeIO
 53 Accounts Merge - Leetcode 721 - Python
Accounts Merge - Leetcode 721 - Python
NeetCodeIO
 54 Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
NeetCodeIO
 55 Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
NeetCodeIO
 56 Number of Zero-Filled Subarrays - Leetcode 2348 - Python
Number of Zero-Filled Subarrays - Leetcode 2348 - Python
NeetCodeIO
 57 Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
NeetCodeIO
 58 Sqrt(x) - Leetcode 69 - Python
Sqrt(x) - Leetcode 69 - Python
NeetCodeIO
 59 Successful Pairs of Spells and Potions - Leetcode 2300 - Python
Successful Pairs of Spells and Potions - Leetcode 2300 - Python
NeetCodeIO
 60 Optimal Partition of String - Leetcode 2405 - Python
Optimal Partition of String - Leetcode 2405 - Python
NeetCodeIO

This video teaches how to solve the Leetcode 3191 problem using a greedy algorithm and a sliding window approach in Python. It covers the concepts of binary array transformation and minimum operations, and provides a practical solution to the problem.

Key Takeaways
  1. Use a greedy algorithm to solve the problem
  2. Assume everything before the current pointer is already one
  3. Flip the current window if the current element is zero
  4. Solve the sub-problem to make the rest of the array zero using the same greedy approach
  5. Iterate through the array and check each element
  6. Flip elements in a window of size 3 to ensure that there are at least three consecutive ones
  7. Check the last two elements to determine if the solution is valid
💡 The greedy algorithm and sliding window approach can be used to solve the Minimum Operations to Make Binary Array Elements Equal to One I problem efficiently.

Related Reads

Chapters (3)

Read the problem
0:30 Drawing Explanation
6:11 Coding Explanation
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →