Python 1529.py
class Solution:
def minFlips(self, target: str) -> int:
result = 0
use = 0
for c in target:
if int(c) != use:
result += 1
use ^= 1
return result
Difficulty
and has an acceptance rate of about 74% (90k+ submissions).
Typical patterns to solve this problem:
- Greedy
- String
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation solves the problem of determining the minimum number of prefix-flip operations required to transform an initially all-zero binary string into a given target string. The algorithm proceeds in a single left-to-right pass, maintaining a logical “parity” that reflects whether the current position has been affected by an odd or even number of flips. Whenever the observed bit in the target differs from the expected bit under the current parity, a new flip is counted and the parity toggles. The final count represents the minimal sequence of flips needed.
Core Logic
Maintaining the Expected Bit
The variable use acts as a binary flag indicating the current parity of flips applied to the prefix ending at the current index. When use is 0, the expected bit at the current position matches the original all-zero state; when use is 1, the expected bit is the inverse of the original state. The comparison
if int(c) != use:
checks whether the target character c (converted to an integer) aligns with the expected bit under the current parity. If they differ, a flip is required at this position.
Counting a Flip and Updating Parity
When a mismatch is detected, the algorithm increments the result counter and toggles the parity flag:
result += 1
use ^= 1
The XOR assignment use ^= 1 flips the value of use between 0 and 1. This succinct operation captures the effect of applying a prefix flip: all subsequent positions will now be interpreted under the opposite parity.
Iterating Over the Target
The loop
for c in target:
...
processes each character of the target string exactly once, ensuring that the algorithm’s behavior is deterministic and directly tied to the input sequence.
Edge Cases Handled
The code gracefully handles an empty target string. In that scenario, the loop body never executes, leaving result at its initial value of 0, which correctly reflects that no flips are needed.
When the target consists entirely of '0' characters, the condition int(c) != use never becomes true because use remains 0 throughout the iteration. Consequently, result stays at 0, indicating that the initial all-zero state already matches the target.
Conversely, if the target is composed solely of '1' characters, the first character triggers a flip, toggling use to 1. From that point onward, each subsequent character matches the expected bit under the new parity, so only a single flip is counted. This demonstrates that the algorithm correctly identifies the minimal single-flip solution for a uniform '1' target.
Mixed patterns such as alternating '0101...' are also correctly processed. Each time the pattern changes relative to the current parity, the condition evaluates to true, prompting a flip and parity toggle. The algorithm therefore captures the exact number of transitions needed to align the evolving expected bit with the target sequence.
Performance Optimizations
The implementation achieves optimal runtime characteristics by avoiding any auxiliary data structures. All state is stored in two integer variables (result and use), which reside in registers for typical execution environments. The use of int(c) converts a single character to its numeric representation without constructing intermediate strings or lists.
The parity toggle employs the XOR-assignment operator (^=), which is a single machine instruction on most architectures, eliminating the need for conditional branching to flip the flag. This contributes to a tight inner loop that minimizes branch misprediction penalties.
Because the algorithm processes each character exactly once and performs only constant-time operations per iteration, it scales linearly with the length of the input string while maintaining a minimal memory footprint.
Complete Function
class Solution:
def minFlips(self, target: str) -> int:
result = 0
use = 0
for c in target:
if int(c) != use:
result += 1
use ^= 1
return result ELI5 - Simplified Explanation
Imagine a long row of little light bulbs that are all turned off. A special machine wants to make these bulbs match a pattern that is written on a piece of paper. The paper shows a secret code of zeros and ones, where zero means the bulb should stay off and one means the bulb should turn on.
The code starts by looking at the first number in the pattern. If that number does not match how the light bulbs are currently acting, the machine flips the switch for all of the bulbs in that section. Every time the machine flips the switch, it counts that move. As it moves along the pattern, it keeps checking if the current state of the bulbs matches the next number in the code. If the numbers do not match, another flip is needed and the counter goes up again. By the time every number in the pattern has been checked, the final count shows how many times the switch had to be pulled to get everything exactly right.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||||
| www | AlgoMonster | Python | C++ | Java | TS | |||||
| WalkCCC | C++ | Java | ||||||||
| leetcode.ca | Python | C++ | Go | Java | Rust | TS | ||||
| Progiez | Python | C++ | Java | |||||||
| github | everthis | JS | ||||||||
| fartem | Ruby | |||||||||
| fsq | C++ | |||||||||
| JoshCrozier | JS | |||||||||
| keineahnung2345 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| suxrobGM | C# | |||||||||
| trung-hn | Python | |||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||
| WalkCCC | C++, Java | |||||||||
| leetcode.ca | C++, Go, Java, Python, Rust, TypeScript | |||||||||
| Progiez | C++, Java, Python | |||||||||
| everthis | JavaScript | |||||||||
| fartem | Ruby | |||||||||
| fsq | C++ | |||||||||
| JoshCrozier | JavaScript | |||||||||
| keineahnung2345 | C++ | |||||||||
| lkwq007 | Python | |||||||||
| suxrobGM | C# | |||||||||
| trung-hn | Python |
Videos
Similar Problems
Solved On The Same Day
- problem 885: Spiral Matrix III
- problem 1043: Partition Array for Maximum Sum
- problem 2044: Count Number of Maximum Bitwise-OR Subsets
- problem 2294: Partition Array Such That Maximum Difference Is K
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality