Practice Maximum Number of Operations to Move Ones to the End
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
In the binary string s, choose a 1 immediately followed by 0. Slide that 1 rightward across the entire consecutive block of zeros, stopping just before the next 1 or at the string's end. This whole slide counts as one operation, regardless of the distance moved. Return the greatest number of legal operations possible. Approach: Scan left to right, counting the ones seen so far. At the start of each zero block, add that count to the answer. Each earlier one can cross that block once, and moving earlier blocks first achieves all these crossings. Do not count each zero separately. The scan takes O(s.length) time and O(1) extra space. Count whole slides, not individual adjacent swaps. Worked example: "10100" permits three moves: "10100" -> "01100" -> "01001" -> "00011". For "1100", each of the two ones crosses the single zero block once, giving two operations.
Source: Maximum Number of Operations to Move Ones to the End on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
s = "10100"
3
# Example 2
s = "1100"
2
Constraints
How to solve Maximum Number of Operations to Move Ones to the End
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
Each one can cross each zero block to its right at most once, and only while the blocks stay distinct, so the maximum is the sum over every maximal zero block of the number of ones to its left. Moving the leftmost movable one first keeps every block separate and attains that bound.
Why brute force is not enough
Simulating slides on the string costs O(n) per operation over up to O(n^2) operations, far too slow for n = 10^5, and choosing the wrong one to move also undercounts.
Approach
- Scan left to right while counting ones seen so far.
- Detect a zero block start: a 0 whose predecessor is a 1. A 0 at the beginning or after another 0 does not start a block.
- At each block start, add the current count of ones; the answer then equals the total available (one, block) crossings in the prefix processed so far.
- Justify optimality by exchange: moving any one other than the leftmost movable one lands it beside the next one and fuses two zero blocks, destroying a crossing, while moving the leftmost first preserves all blocks.
Walkthrough of Example 1
s = "10100" → 3
- Scan 10100: index 0 is 1, ones = 1.
- Index 1 is a 0 after a 1, a block start; add 1, total 1.
- Index 2 is 1, ones = 2.
- Index 3 is a 0 after a 1, a second block; add 2, total 3.
- Index 4 continues the block and adds nothing. The answer is 3, realized by 10100 to 01100 to 01001 to 00011.
Time and space
Time O(n) · Space O(1). A single pass over the n characters with two integer counters.
Interview pitfalls
- Adding the count of ones at every zero instead of once per block, which counts single-step swaps rather than whole slides.
- Simulating by always moving the rightmost movable one, which merges blocks; on 10100 that yields 2 instead of 3.
- Using a 32-bit counter where the answer can reach about n^2 / 4, roughly 2.5 * 10^9 for n = 10^5.
- Forgetting the trailing zero block, which every preceding one can still cross.
Follow-up questions interviewers ask
- How would you count operations if a slide crossed only a single zero rather than a whole block?
- What if ones could also move left, and does a symmetric argument give the maximum?
- Can you output the actual sequence of operations in O(n) time plus output size?
Further reading on the technique: Greedy algorithm
Related LeetCode Problems
Practice more problems similar to Maximum Number of Operations to Move Ones to the End.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.