Maximum Number of Operations to Move Ones to the End solution and explanation
Google
9 more videos on this problem
Maximum Number of Operations to Move Ones to the End | Interview Style | Leetcode 3228 | MIKcodestorywithMIK · 17:42 · 6K views
Maximum Number of Operations to Move Ones to the End - Leetcode 3228 - PythonNeetCodeIO · 12:20 · 4K views
3228. Maximum Number of Operations to Move Ones to the End | Greedy | Two PointersAryan Mittal · 10:47 · 3K views
Maximum Number of Operations to Move Ones to the End | LeetCode 3228 | Beginner FriendlySanyam IIT Guwahati · 9:25 · 688 views
3228. Maximum Number of Operations to Move Ones to the End (Leetcode Medium)Programming Live with Larry · 9:09 · 412 views
Daily Leetcode #2053: Nov 13, 2025 - 3228. Maximum Number of Operations to Move Ones to the EndProgramming Live with Larry · 15:05 · 397 views
3228. Maximum Number of Operations to Move Ones to the End | Leetcode Daily - PythonLeetcode Daily · 7:41 · 309 views
Leetcode 3228 🔥 Maximum Number of Operations to Move Ones to the End | DCC | Optimal Java Solution Study Placement · 7:36 · 215 views
LeetCode Daily 3228 | Maximum Number of Operations to Move Ones to the End | Medium | SolutionDaily Dose Of LeetCode · 14:17 · 84 views
Leetcode 3228 | Maximum Number of Operations to Move Ones to the End | Weekly Contest 407Road To FAANG · 8:29 · 78 views
The problem
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.
Approach 1: Greedy Approach
In this approach, we will iterate through the string and count the number of operations we can perform. Each valid operation will involve swapping a pair of '10' to '01' by tracking the zeros followed by ones.
def maximum_operations(s: str) -> int:
count = 0
operations = 0
for c in s:
if c == '0':
count += 1
elif c == '1' and count > 0:
operations += count
return operations
s = "1001101"
print(maximum_operations(s)) # Output: 4public class MaximumOperations {
public static int maximumOperations(String s) {
int count = 0, operations = 0;
for (char c : s.toCharArray()) {
if (c == '0') {
count++;
} else if (c == '1' && count > 0) {
operations += count;
}
}
return operations;
}
public static void main(String[] args) {
String s = "1001101";
System.out.println(maximumOperations(s)); // Output: 4
}
}#include <iostream>
#include <string>
int maximumOperations(const std::string &s) {
int count = 0, operations = 0;
for (char c : s) {
if (c == '0') {
count++;
} else if (c == '1' && count > 0) {
operations += count;
}
}
return operations;
}
int main() {
std::string s = "1001101";
std::cout << maximumOperations(s) << std::endl; // Output: 4
return 0;
}function maximumOperations(s) {
let count = 0, operations = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === '0') {
count++;
} else if (s[i] === '1' && count > 0) {
operations += count;
}
}
return operations;
}
console.log(maximumOperations("1001101")); // Output: 4;#include <stdio.h>
#include <string.h>
int maximumOperations(char *s) {
int count = 0, operations = 0, len = strlen(s);
for (int i = 0; i < len; i++) {
if (s[i] == '0') {
count++;
} else if (s[i] == '1' && count > 0) {
operations += count;
}
}
return operations;
}
int main() {
char s[] = "1001101";
printf("%d\n", maximumOperations(s)); // Output: 4
return 0;
}using System;
public class MaximumOperations {
public int MaximumOperations(string s) {
int count = 0, operations = 0;
foreach (char c in s) {
if (c == '0') {
count++;
} else if (c == '1' && count > 0) {
operations += count;
}
}
return operations;
}
public static void Main() {
MaximumOperations ops = new MaximumOperations();
string s = "1001101";
Console.WriteLine(ops.MaximumOperations(s)); // Output: 4
}
}Utilizing Python's simplicity, the function concisely tracks zeroes with count and increments operation counts whenever a '1' follows these zeros, without needing any additional data structures.
Time Complexity: O(n), a single pass is made through s.
Space Complexity: O(1), only uses numerical variables.
Approach 2: Scan and Balance Counting
In this approach, we track the imbalance between '1's and '0's to calculate possible operations. The idea is to find how many '1's can become "stuck" behind '0's and count how many operations it would take to move each '1' to the end of the '0s'.
def maximum_operations(s: str) -> int:
ops = 0
imbalance = 0
for c in s:
if c == '1':
imbalance += 1
elif imbalance > 0:
ops += imbalance
return ops
s = "1001101"
print(maximum_operations(s)) # Output: 4public class MaximumOperations {
public static int maximumOperations(String s) {
int ops = 0, imbalance = 0;
for (char c : s.toCharArray()) {
if (c == '1') {
imbalance++;
} else if (imbalance > 0) {
ops += imbalance;
}
}
return ops;
}
public static void main(String[] args) {
String s = "1001101";
System.out.println(maximumOperations(s)); // Output: 4
}
}#include <iostream>
#include <string>
int maximumOperations(const std::string &s) {
int ops = 0, imbalance = 0;
for (char c : s) {
if (c == '1') {
imbalance++;
} else if (imbalance > 0) {
ops += imbalance;
}
}
return ops;
}
int main() {
std::string s = "1001101";
std::cout << maximumOperations(s) << std::endl; // Output: 4
return 0;
}function maximumOperations(s) {
let ops = 0, imbalance = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === '1') {
imbalance++;
} else if (imbalance > 0) {
ops += imbalance;
}
}
return ops;
}
console.log(maximumOperations("1001101")); // Output: 4;#include <stdio.h>
#include <string.h>
int maximumOperations(char *s) {
int ops = 0, imbalance = 0, n = strlen(s);
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
imbalance++;
} else if (imbalance > 0) {
ops += imbalance;
}
}
return ops;
}
int main() {
char s[] = "1001101";
printf("%d\n", maximumOperations(s)); // Output: 4
return 0;
}using System;
public class MaximumOperations {
public int MaximumOperations(string s) {
int ops = 0, imbalance = 0;
foreach (char c in s) {
if (c == '1') {
imbalance++;
} else if (imbalance > 0) {
ops += imbalance;
}
}
return ops;
}
public static void Main() {
MaximumOperations ops = new MaximumOperations();
string s = "1001101";
Console.WriteLine(ops.MaximumOperations(s)); // Output: 4
}
}The Python solution leverages simple counting logic: imbalance increases with '1's and allows for incremental adds to the operations counter with any encountering '0s. This results in a tally of how many such valid operations could be sequentially made.
Time Complexity: O(n), linear scanning of the input.
Space Complexity: O(1), employing only a few integer variables.
Approach 3: Greedy
We use a variable ans to record the answer and another variable cnt to count the current number of 1s.
Then, we iterate through the string s. If the current character is 1, then we increment cnt. Otherwise, if there is a previous character and the previous character is 1, then the previous cnt number of 1s can be moved backward, and we add cnt to the answer.
Finally, we return the answer.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
function maxOperations(s: string): number {
let [ans, cnt] = [0, 0];
const n = s.length;
for (let i = 0; i < n; ++i) {
if (s[i] === '1') {
++cnt;
} else if (i && s[i - 1] === '1') {
ans += cnt;
}
}
return ans;
}func maxOperations(s string) (ans int) {
cnt := 0
for i, c := range s {
if c == '1' {
cnt++
} else if i > 0 && s[i-1] == '1' {
ans += cnt
}
}
return
}impl Solution {
pub fn max_operations(s: String) -> i32 {
let mut ans = 0;
let mut cnt = 0;
let n = s.len();
let bytes = s.as_bytes();
for i in 0..n {
if bytes[i] == b'1' {
cnt += 1;
} else if i > 0 && bytes[i - 1] == b'1' {
ans += cnt;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), a single pass is made through |
| Scan and Balance Counting | Time Complexity: O(n), linear scanning of the input. |
| Greedy | – |
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. |
Frequently asked questions
Is Maximum Number of Operations to Move Ones to the End easy or hard?
This problem is generally classified as Medium difficulty. The implementation is short, but the key insight is recognizing that the number of operations equals the count of 1-before-0 pairs in the string. Once that observation is made, the solution becomes a straightforward linear scan.
Maximum Number of Operations to Move Ones to the End Python/Java solution
The implementation in Python or Java follows the same logic: iterate through the string, maintain a running count of 1s, and add that count to the answer whenever a 0 is encountered. Both implementations run in O(n) time and require constant additional space.
How to solve Maximum Number of Operations to Move Ones to the End in O(n)?
Iterate through the string from left to right. Maintain a counter for how many 1s have appeared so far. When encountering a 0, add the number of seen 1s to the result because those 1s will eventually move past that 0. Continue scanning until the end to compute the total operations.
What is the best approach for Maximum Number of Operations to Move Ones to the End?
The greedy counting approach is the most efficient and easiest to reason about. Scan the string once while counting how many 1s have appeared so far. Each time a 0 appears, add the current number of 1s to the total operations. This directly counts all (1,0) pairs in O(n) time and O(1) space.
Is Maximum Number of Operations to Move Ones to the End asked at Google/Amazon/Meta?
Problems involving inversion counting, greedy scans, and binary string manipulation are common in interviews at companies like Google, Amazon, and Meta. This specific pattern—counting 1-before-0 pairs using a linear scan—appears frequently in medium-level coding interviews.
What data structure is used in Maximum Number of Operations to Move Ones to the End?
No complex data structures are required. The optimal solution uses simple integer counters while scanning a string. The technique falls under greedy algorithms and counting patterns rather than relying on stacks, heaps, or hash maps.
What is the time complexity of Maximum Number of Operations to Move Ones to the End?
The optimal solution runs in O(n) time where n is the length of the binary string. The algorithm performs a single pass through the string while maintaining a counter for previously seen 1s. Space complexity remains O(1) because only a few integer variables are required.