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.

Description Hints 2 Solution Video 17:42

3228. Maximum Number of Operations to Move Ones to the End

Medium67.2% acceptance4 companies

You are given a binary string s.

You can perform the following operation on the string any number of times:

Choose any index i from the string where i + 1 < s.length such that s[i] == '1' and s[i + 1] == '0'.
Move the character s[i] to the right until it reaches the end of the string or another '1'. For example, for s = "010010", if we choose i = 1, the resulting string will be s = "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 is s = "0011101".
Choose index i = 4. The resulting string is s = "0011011".
Choose index i = 3. The resulting string is s = "0010111".
Choose index i = 2. The resulting string is s = "0001111".

Example 2:

Input: s = "00111"

Output: 0

Constraints:

1 <= s.length <= 10⁵
s[i] is either '0' or '1'.

Asked at 4 companies

Google Amazon Meta Bloomberg

Topics

Hints open one at a time

Hint 1

It is optimal to perform the operation on the lowest index possible each time.

Hint 2

Traverse the string from left to right and perform the operation every time it is possible.

17:42

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxOperations(self, s: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"1001101"

Input

"00111"

Your code is saved on this device.Solution