30% off Lifetime Premium Access expires December 2nd!

30% off Lifetime Premium Access expires Dec 2nd!

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Get Premium

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

Given a binary string s, you may repeatedly pick any adjacent "10" and slide that '1' rightward over all following zeros until it hits another '1' or the string end; compute the maximum number of such operations you can perform. The core challenge is to reason about the optimal order of moves and count movable ones efficiently (greedy/inversion-style scan over the string).

DESCRIPTION

Input:


s = "10100"

Output:

Explanation: First '1' at index 0 can slide over 1 zero (1 move). Second '1' at index 2 can slide over 2 zeros (2 moves). Total: 3 operations.

Constraints:

1 <= s.length <= 10^5
s consists only of '0' and '1' characters
Each operation slides a '1' over consecutive zeros until blocked

Understanding the Problem

Let's understand what we're being asked to do. We have a binary string like '10100' and can perform a specific operation: find any '10' substring and slide the '1' rightward over all following zeros until it hits another '1' or the end.

Tracing through '10100': We could pick the first '10' (positions 0-1) and slide the '1' right, transforming it to '01100'. Or we could pick the '10' at positions 2-3 and slide that '1' right to get '10010'. Each valid slide counts as one operation.

Important constraint: We can only slide a '1' that is immediately followed by a '0' (forming '10'). The '1' slides over consecutive zeros until blocked.

Edge cases to consider: What if the string has no '10' patterns? (no moves possible, return 0). What if all '1's are already at the right? What if we have '111000' (multiple ones can each slide)?

Brute Force Approach

The straightforward approach is to simulate the process: repeatedly scan the string for any '10' pattern, perform the slide operation (move the '1' rightward over zeros), increment the operation counter, and repeat until no more '10' patterns exist. This approach directly models the problem description but requires multiple passes through the string and string manipulation for each operation, making it inefficient for large inputs.

def max_slide_operations(s):
    """
    Brute force: repeatedly find '10' patterns and slide the '1' rightward
    over all zeros until it hits another '1' or the end.
    Count total operations until no more '10' patterns exist.
    """
    # Convert string to list for mutability
    chars = list(s)
    operations = 0
    
    # Keep scanning until no more '10' patterns exist
    while True:
        found = False
        
        # Scan for any '10' pattern
        for i in range(len(chars) - 1):
            if chars[i] == '1' and chars[i + 1] == '0':
                found = True
                
                # Slide the '1' rightward over all consecutive zeros
                j = i + 1
                while j < len(chars) and chars[j] == '0':
                    j += 1
                
                # Move the '1' to position j-1 (just before next '1' or end)
                chars[i] = '0'
                chars[j - 1] = '1'
                
                # Increment operation count
                operations += 1
                break
        
        # If no '10' pattern found, we're done
        if not found:
            break
    
    return operations

Start: Convert string to character array for manipulation

0 / 37

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n²) In the worst case (like '111...000...'), we perform O(n) operations, and each operation requires scanning and modifying the string which takes O(n) time, resulting in O(n²) total time

Space Complexity: O(n) We need O(n) space to store and manipulate the string during each operation

Building Intuition

Each '1' in the string can potentially slide rightward over zeros. The key insight is that a '1' at position i can slide over all zeros to its right until it hits another '1' or the end.

The order in which we perform slides matters! If we have '1010', sliding the first '1' blocks the second '1' from sliding as far.

By thinking about each '1' independently and counting how many positions it can slide, we can compute the total number of operations.

The crucial realization: processing '1's from right to left (or tracking how many zeros are available) lets us count moves without simulating each step. Each '1' can slide over all zeros to its right that aren't already "claimed" by '1's further right.

Imagine cars (ones) on a highway with empty spaces (zeros) ahead. Each car wants to move forward into empty spaces.

If we process cars from back to front, each car can count exactly how many empty spaces it can claim. The first car (rightmost '1') claims all zeros to its right. The second car claims zeros between it and the first car, and so on.

This is like counting inversions - how many zeros does each '1' need to "jump over" to reach its final position?

Common Mistakes

Trying to simulate each operation explicitly instead of counting - this leads to O(n²) time complexity and unnecessary string manipulation

Scanning left-to-right instead of right-to-left - this makes it difficult to correctly count how many zeros each '1' can slide over without complex tracking

Forgetting to increment the zero count after processing each '1' - the '1' itself becomes a 'space' for '1's further left after it slides

Not handling edge cases: strings with no '1's (return 0), strings with no '0's (return 0), or strings where all '1's are already rightmost

Confusing the problem with sorting or other string transformation problems - the specific '10' pattern and rightward sliding rule is unique to this problem

Optimal Solution

The optimal approach scans the string from right to left, tracking how many zeros we've seen so far. Each time we encounter a '1', it can slide over all the zeros to its right (the count we've been tracking), and we add this count to our total operations. After counting a '1''s contribution, we increment the zero count (because this '1' will act as a zero-space for '1's further left after it slides). This greedy single-pass approach counts all possible operations without simulation.

def max_slide_operations(s):
    """
    Count maximum number of '10' -> '01' slide operations.
    Scan right-to-left, tracking zeros; each '1' can slide over all zeros to its right.
    """
    total_operations = 0
    zero_count = 0
    
    # Scan from right to left
    for i in range(len(s) - 1, -1, -1):
        if s[i] == '0':
            # Count zeros for '1's to the left
            zero_count += 1
        else:
            # This '1' can slide over all zeros to its right
            total_operations += zero_count
            # After sliding, this '1' acts as a zero-space for '1's further left
            zero_count += 1
    
    return total_operations

Start: Count maximum slide operations for binary string

0 / 19

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We make a single pass through the string, examining each character once, resulting in linear time complexity

Space Complexity: O(1) We only need a constant amount of extra space to track the count of zeros and total operations

What We've Learned

Greedy right-to-left scanning: When elements need to move to the end based on relative positions, scan from right to left to count how many positions each element can move - this naturally accumulates the total operations because later '1's block earlier ones, making a single pass sufficient.
Inversion counting pattern: This problem is fundamentally about counting inversions (how many '0's each '1' must pass over) - recognize that 'moving elements to the end' problems often reduce to counting how many obstacles each element encounters, summed across all movable elements.
Cumulative zero tracking: Maintain a running count of zeros encountered so far (scanning right-to-left) - when you hit a '1', add the zero count to your result because that '1' can slide over all those zeros, then increment the zero count to account for this '1' becoming an obstacle for future '1's.
Order independence insight: The key realization is that the total number of operations is independent of the order you perform them - each '1' will eventually move past all '0's to its right, so you can simply count all possible moves rather than simulating the actual movement sequence.
Single-pass O(n) optimization: Avoid simulating the actual string modifications (which would be O(n²) or worse) - instead, recognize that you can compute the answer analytically by counting relationships between '1's and '0's in one linear scan, trading simulation for mathematical reasoning.
Relative positioning problems: Apply this counting approach to any problem where elements move based on relative order constraints (bubble sort operations, minimum swaps, array rearrangement) - often the total operations needed equals the sum of 'distances' each element must travel past blocking elements.

Test Your Understanding

Why is array the right data structure for this problem?

array provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

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

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact