Maximum Number of Operations to Move Ones to the End - Video Solutions
Maximum Number of Operations to Move Ones to the End | Interview Style | Leetcode 3228 | MIK
Maximum Number of Operations to Move Ones to the End - Video Solution
Watch 10 video solutions for Maximum Number of Operations to Move Ones to the End, a medium level problem involving String, Greedy, Counting. This walkthrough by codestorywithMIK has 6,513 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given a binary string s.
You can perform the following operation on the string any number of times:
- Choose any index
ifrom the string wherei + 1 < s.lengthsuch thats[i] == '1'ands[i + 1] == '0'. - Move the character
s[i]to the right until it reaches the end of the string or another'1'. For example, fors = "010010", if we choosei = 1, the resulting string will bes = "000110".
Return the maximum number of operations that you can perform.
Example 1:
Input: s = "1001101"
Output: 4
Explanation:
We can perform the following operations:
- Choose index
i = 0. The resulting string iss = "0011101". - Choose index
i = 4. The resulting string iss = "0011011". - Choose index
i = 3. The resulting string iss = "0010111". - Choose index
i = 2. The resulting string iss = "0001111".
Example 2:
Input: s = "00111"
Output: 0
Constraints:
1 <= s.length <= 105s[i]is either'0'or'1'.
Approach Overview
Problem Overview: Given a binary string s, determine the maximum number of operations required to move all 1s to the end. An operation effectively moves a 1 to the right across a 0. The goal is to count how many such moves can occur before all 1s are positioned after every 0.
Approach 1: Greedy Counting (O(n) time, O(1) space)
The key observation: every time a 1 appears before a 0, that pair will eventually require a move. This turns the problem into counting inversions of the form (1,0). Scan the string left to right while tracking how many 1s have been seen. When a 0 appears, all previously seen 1s could move past it through operations, so add that count to the result. Continue until the end of the string. This greedy scan works because each 1 can cross each 0 at most once, and counting these pairs directly gives the maximum number of operations.
This technique is common in problems involving binary ordering and swap-style operations, especially in greedy and string processing tasks. The algorithm performs a single pass and uses only a couple of counters.
Approach 2: Scan and Balance Counting (O(n) time, O(1) space)
Another way to view the problem is by balancing the number of 1s that still need to move. Iterate through the string while maintaining a running count of active 1s. Each time a 0 appears and there are pending 1s to the left, those 1s will eventually move across this position. Add the active 1 count to the total operations. Conceptually, the algorithm treats each 0 as a checkpoint that all previous 1s must cross.
This formulation highlights the counting aspect of the problem and mirrors how many swap-like transformations occur when pushing elements to the end. Implementation remains a single linear scan with constant memory.
Recommended for interviews: The greedy counting approach. It reduces the problem to counting 1-before-0 pairs in one pass, which demonstrates strong pattern recognition. Explaining the inversion-style insight shows the interviewer you can convert a simulation problem into a simple counting strategy.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Counting | O(n) | O(1) | Best general solution. Single pass counting of 1-before-0 pairs. |
| Scan and Balance Counting | O(n) | O(1) | Useful when reasoning about active 1s moving across zeros during the scan. |