Skip to main content

Two Pointer

Separate Black and White Balls

Problem Description

There are n balls on a table, each ball has a color black or white.
You are given a 0-indexed binary string s of length n, where 1 and 0 represent black and white balls, respectively.
In each step, you can choose two adjacent balls and swap them.
Return the minimum number of steps to group all the black balls to the right and all the white balls to the left.

Examples

Input: s = “101”
Output: 1
Explanation: We can group all the black balls to the right in the following way:
- Swap s[0] and s[1],  s = "011".
Initially, 1s are not grouped together, requiring at least 1 step to group them to the right.

Input: s = “100”
Output: 2
Explanation: We can group all the black balls to the right in the following way:
- Swap s[0] and s[1], s = "010".
- Swap s[1] and s[2], s = "001".
It can be proven that the minimum number of steps needed is 2.

Input: s = “0111”
Output: 0
Explanation: All the black balls are already grouped to the right.

Constraints

  • 1 <= n == s.length <= 10⁵
  • s[i] is either ‘0’ or ‘1’
Now that we understand the problem, let's identify the key points that can guide us in building a brute-force solution. Once we have a clear understanding of the brute force approach, we can explore ways to optimize it and create a more efficient solution.

Brute Force Approach

Intuition

The main challenge is to minimize the number of swaps required to rearrange the balls so that all 0s (white balls) are on the left and all 1s (black balls) are on the right.

To solve this, observe that any string where some 0s are not on the left (and consequently, some 1s are not on the right) will require swaps. The swaps are needed to correct out-of-order adjacent pairs.

Now, let’s define what contributes to a swap:

  • An adjacent pair is "out of order" if a black ball (1) is to the left of a white ball (0).
  • For example, in "101", the first two characters (1 and 0) form an out-of-order pair and need to be swapped to get "011".

Thus, the problem reduces to finding all adjacent out-of-order pairs (1 followed by 0) and repeatedly swapping them until no such pairs remain. Each swap contributes to the total count of swaps needed to fully group the balls. Let’s understand it step by step.

How can we fix the out-of-order Pairs?

To fix the arrangement, we need to simply:

  1. Look at each pair of adjacent balls (side by side) in the row.
  2. If the left ball is black ('1') and the right ball is white ('0'), swap them. This fixes the "local problem" for this pair and with the swap, we increment the count of swaps.
  3. After the swap, move to the next pair and repeat the process.

This process is like pushing black balls (1) toward the right and white balls (0) toward the left, one step at a time.

When Do We Stop?

Think of it this way: every time you scan the row of balls, you are looking for out-of-order pairs where a 1 (black ball) is to the left of a 0 (white ball).

  • If you find such pairs, you swap them to move the balls closer to their correct positions.
  • But at some point, after enough swaps, the balls will be fully grouped (all 0s on the left and all 1s on the right).

How do you know when you’ve reached this point?

  • It’s simple! If you scan through the entire row and don’t find a single out-of-order pair, it means the balls are already in the correct order.

Here’s an example:

  1. Imagine the row is "10101".
    • You’ll find out-of-order pairs (10), swap them, and get "01101".
  2. Next, you scan "01101" again.
    • You find another out-of-order pair (10), swap, and get "00111".
  3. Now, you scan "00111".
    • There are no more out-of-order pairs (every 0 is to the left of every 1).

At this point, you stop swapping because the balls are fully grouped!

💡
Try it Yourself!

Why Does This Work?

This approach works because:

  • Each swap fixes a single out-of-order pair, reducing the disorder in the row.
  • By repeatedly fixing out-of-order pairs, the row gradually becomes more organized until it’s fully grouped.

Think of it like sorting a messy row, step by step, where each step reduces the mess.

Dry - run

Input: s = “10110”
Output: 4
Explanation: We can group all the black balls to the right in the following way:
- Swap s[0] and s[1], s = "01110".
- Swap s[3] and s[4], s = "01101".
- Swap s[2] and s[3], s = "01011".
- Swap s[1] and s[2], s = "00111".
Hence, minimum number of steps required = 4.

Initial Setup:

  • n = 5 (size of the string)
  • minSwaps = 0 (tracks total swaps)

Pass 1:

  1. Initial string: "10110"
  2. swapCount = 0

Inner For Loop:

  • Iteration 1 (j = 1):
    • s[j] = '0', s[j-1] = '1' → Condition satisfied.
    • Swap s[1] and s[0]: "10110" → "01110"
    • swapCount++ → swapCount = 1
  • Iteration 2 (j = 2):
    • s[j] = '1', s[j-1] = '1' → No swap.
  • Iteration 3 (j = 3):
    • s[j] = '1', s[j-1] = '1' → No swap.
  • Iteration 4 (j = 4):
    • s[j] = '0', s[j-1] = '1' → Condition satisfied.
    • Swap s[4] and s[3]: "01110" → "01101"
    • swapCount++ → swapCount = 2

End of Pass 1:

  • swapCount = 2 → Add to minSwaps: minSwaps += swapCount = 0 + 2 = 2
  • String after Pass 1: "01101"

Pass 2:

  1. Initial string: "01101"
  2. swapCount = 0

Inner For Loop:

  • Iteration 1 (j = 1):
    • s[j] = '1', s[j-1] = '0' → No swap.
  • Iteration 2 (j = 2):
    • s[j] = '1', s[j-1] = '1' → No swap.
  • Iteration 3 (j = 3):
    • s[j] = '0', s[j-1] = '1' → Condition satisfied.
    • Swap s[3] and s[2]: "01101" → "01011"
    • swapCount++ → swapCount = 1
  • Iteration 4 (j = 4):
    • s[j] = '1', s[j-1] = '0' → No swap.

End of Pass 2:

  • swapCount = 1 → Add to minSwaps: minSwaps += swapCount = 2 + 1 = 3
  • String after Pass 2: "01011"

Pass 3:

  1. Initial string: "01011"
  2. swapCount = 0

Inner For Loop:

  • Iteration 1 (j = 1):
    • s[j] = '1', s[j-1] = '0' → No swap.
  • Iteration 2 (j = 2):
    • s[j] = '0', s[j-1] = '1' → Condition satisfied.
    • Swap s[2] and s[1]: "01011" → "00111"
    • swapCount++ → swapCount = 1
  • Iteration 3 (j = 3):
    • s[j] = '1', s[j-1] = '0' → No swap.
  • Iteration 4 (j = 4):
    • s[j] = '1', s[j-1] = '1' → No swap.

End of Pass 3:

  • swapCount = 1 → Add to minSwaps: minSwaps += swapCount = 3 + 1 = 4
  • String after Pass 3: "00111"

Pass 4:

  1. Initial string: "00111"
  2. swapCount = 0

Inner For Loop:

  • Iteration 1 (j = 1):
    • s[j] = '0', s[j-1] = '0' → No swap.
  • Iteration 2 (j = 2):
    • s[j] = '1', s[j-1] = '0' → No swap.
  • Iteration 3 (j = 3):
    • s[j] = '1', s[j-1] = '1' → No swap.
  • Iteration 4 (j = 4):
    • s[j] = '1', s[j-1] = '1' → No swap.

End of Pass 4:

  • swapCount = 0 → Terminate the loop as no swaps are required.

Result:

  • minSwaps = 4
  • Final sorted string: "00111"

Steps to write code

Step 1: Initialize Variables

  • Create a variable n to store the size of the string (s.size() in C++).
  • Initialize a variable minSwaps to 0 to track the total number of swaps made.

Step 2: Use a Loop to Simulate the Swapping Process

  • Create an infinite loop (e.g., while (true) in C++) to keep processing the string until no more swaps are required.
  • Within the loop, initialize a variable swapCount to 0 to count the number of swaps performed in the current pass.

Step 3: Traverse the String to Find Swappable Pairs

  • Use a for loop to traverse the string starting from index 1 (to compare each character with its previous one).
  • Check if the current character is '0' and the previous character is '1'. This indicates a swappable pair.
  • If the condition is met:
    1. Swap the two characters.
    2. Increment swapCount by 1.

Step 4: Check if Any Swaps Were Made

  • After finishing the inner loop, check if swapCount is 0.
    • If swapCount is 0, it means the string is fully sorted, and no more swaps are needed. Return minSwaps.
    • Otherwise, add swapCount to minSwaps.

Step 5: Repeat Until grouped

  • The process continues until no swaps are made, ensuring the string is completely sorted.
Brute Force in All Languages
C++ 
class Solution {
public:
    long long minimumSteps(string s) {
        // Get the size of the input string
        int n = s.size();

        // Initialize a variable to track the total number of swaps
        long long minSwaps = 0;

        // Start an infinite loop to repeatedly check for required swaps
        while (true) {
            // Initialize a variable to track the number of swaps in the current pass
            int swapCount = 0;

            // Iterate through the string from the second character to the last
            for (int j = 1; j < n; j++) {
                // Check if the current character is '0' and the previous character is '1'
                if (s[j] == '0' && s[j - 1] == '1') {
                    // Swap the characters
                    swap(s[j], s[j - 1]);

                    // Increment the swap count for the current pass
                    swapCount++;
                }
            }

            // If no swaps were made in this pass, the string is fully sorted
            if (swapCount == 0) {
                // Return the total number of swaps performed
                return minSwaps;
            }

            // Add the number of swaps in this pass to the total swaps
            minSwaps += swapCount;
        }
    }
};

Java 
class Solution {
    public long minimumSteps(String s) {
        // Get the size of the input string
        int n = s.length();

        // Initialize a variable to track the total number of swaps
        long minSwaps = 0;

        // Start an infinite loop to repeatedly check for required swaps
        while (true) {
            // Initialize a variable to track the number of swaps in the current pass
            int swapCount = 0;

            // Iterate through the string from the second character to the last
            for (int j = 1; j < n; j++) {
                // Check if the current character is '0' and the previous character is '1'
                if (s.charAt(j) == '0' && s.charAt(j - 1) == '1') {
                    // Convert the string to a character array to perform the swap
                    char[] chars = s.toCharArray();
                    char temp = chars[j];
                    chars[j] = chars[j - 1];
                    chars[j - 1] = temp;

                    // Convert the character array back to a string
                    s = new String(chars);

                    // Increment the swap count for the current pass
                    swapCount++;
                }
            }

            // If no swaps were made in this pass, the string is fully sorted
            if (swapCount == 0) {
                // Return the total number of swaps performed
                return minSwaps;
            }

            // Add the number of swaps in this pass to the total swaps
            minSwaps += swapCount;
        }
    }
}

Python 
class Solution:
    def minimumSteps(self, s: str) -> int:
        # Get the size of the input string
        n = len(s)

        # Initialize a variable to track the total number of swaps
        min_swaps = 0

        # Start an infinite loop to repeatedly check for required swaps
        while True:
            # Initialize a variable to track the number of swaps in the current pass
            swap_count = 0

            # Iterate through the string from the second character to the last
            for j in range(1, n):
                # Check if the current character is '0' and the previous character is '1'
                if s[j] == '0' and s[j - 1] == '1':
                    # Swap the characters by converting the string to a list
                    s = list(s)
                    s[j], s[j - 1] = s[j - 1], s[j]
                    s = ''.join(s)

                    # Increment the swap count for the current pass
                    swap_count += 1

            # If no swaps were made in this pass, the string is fully sorted
            if swap_count == 0:
                # Return the total number of swaps performed
                return min_swaps

            # Add the number of swaps in this pass to the total swaps
            min_swaps += swap_count

Javascript 
/**
 * @param {string} s
 * @return {number}
 */
class Solution {
    minimumSteps(s) {
        // Get the size of the input string
        const n = s.length;

        // Initialize a variable to track the total number of swaps
        let minSwaps = 0;

        // Start an infinite loop to repeatedly check for required swaps
        while (true) {
            // Initialize a variable to track the number of swaps in the current pass
            let swapCount = 0;

            // Iterate through the string from the second character to the last
            for (let j = 1; j < n; j++) {
                // Check if the current character is '0' and the previous character is '1'
                if (s[j] === '0' && s[j - 1] === '1') {
                    // Convert the string to an array to perform the swap
                    s = s.split('');
                    [s[j], s[j - 1]] = [s[j - 1], s[j]];
                    s = s.join('');

                    // Increment the swap count for the current pass
                    swapCount++;
                }
            }

            // If no swaps were made in this pass, the string is fully sorted
            if (swapCount === 0) {
                // Return the total number of swaps performed
                return minSwaps;
            }

            // Add the number of swaps in this pass to the total swaps
            minSwaps += swapCount;
        }
    }
}

Time Complexity: O(n²)

1. Outer Loop (While Loop)

The while (true) loop runs until no swaps are made in a single pass, i.e., the string becomes fully sorted.The key observation is:

  • Each swap moves a '1' one position closer to the right.
  • The maximum number of iterations of the while loop is limited by the number of '1's and '0's and their relative disorder.

For a string of size n, in the worst-case scenario is (e.g., "111...000"):

  • Each '1' needs to "move" through all the '0's to reach its correct position.
  • If there are k '1's and n−k '0's, the total number of swaps in the worst case is O(k×(n−k)).

2. Inner Loop (For Loop)

The inner loop (for (int j = 1; j < n; j++)) always iterates n−1 times in each pass, regardless of the number of swaps performed.

Combining the Two Loops

Let us now combine the contributions of both loops:

  1. Maximum Number of Outer Loop Iterations: The worst-case number of iterations is when k=1 which is the case in a string like “100000…”. Here. O(k×(n-k)) = O(n-1) → O(n).
  2. Inner Loop Contribution: In each iteration of the while loop, the for loop runs O(n) times.
    • And now we know that the outer while loop runs at max O(n) times.
    • Thus, if the while loop runs O(n) times (total passes needed to sort the string), the total work done by the inner loop is O(n×n) = O(n²).

Hence total time complexity is O(n²).

Space Complexity O(1)

Auxiliary Space Complexity

Auxiliary space complexity refers to the extra space used by the algorithm, excluding the space for the input. In this case:

  • The function only uses a few integer variables (n, minSwaps, swapCount, j), which are all of constant size.
  • No additional data structures (like arrays or lists) are created during the execution of the function.

Since the auxiliary space only depends on a few integer variables, it is constant space, or O(1).

Total Space Complexity

The total space complexity considers all memory used by the program, including the space for the input, auxiliary variables, and any other data structures used.

Input Storage:

  • The input string s is passed to the function. This is an array of characters with size n. So, the space used for input is O(n).

Auxiliary Space Complexity is O(1)

The code does not use any additional data structures like arrays, hash maps, or stacks. It works directly on the input string and modifies it in place, meaning no additional space is allocated for processing.

Hence total space complexity is O(n)

Is the brute force approach effective in this scenario?

The current solution has a time complexity of O(n²), which is not feasible for n ≤ 10⁵. This indicates that for each test case with an array size up to 10⁵, the solution may not be completed within the given time constraints.

With O(n²), we end up with a maximum of 10¹⁰ operations when n = 10⁵. This level of complexity is impractical for larger test cases. In most competitive programming environments, the problem constraints typically allow for up to 10⁶ operations per test case. Therefore, for n ≤ 10⁵, a solution requiring 10¹⁰ operations is inefficient and unlikely to perform adequately.

By analyzing the brute force approach, we can identify key insights and recognize areas where unnecessary work is being done, allowing us to optimize the solution.

Optimal Approach

Intuition

The goal is to minimize the number of swaps required to rearrange the balls so that all 0s (white balls) are on the left and all 1s (black balls) are on the right.

In the brute force method, we repeatedly identified and swapped out-of-order pairs (a 1 followed by a 0) until the balls were grouped. While this works, it’s not the most efficient way because we’re manually swapping balls repeatedly.

Can we figure out the total minimum number of swaps directly, without actually performing them? Yes! Here’s how.

Key Observation:

Every 0 (white ball) that has 1s (black balls) to its left contributes to the total number of swaps needed to arrange the balls.

How Does This Work?

When we encounter a 0 in the string:

  • The number of 1s already seen before this 0 determines how far this 0 needs to "move" to reach its correct position (i.e., to the left side).
  • Each 1 to the left of a 0 contributes one swap.
  • So, why manually swap a 0 through all the ones to its left if we can directly count the number of ones to the left of a 0.

For example, Let’s analyze the string s = "01110":

The goal is to rearrange the string so that all 0s (white balls) are on the left and all 1s (black balls) are on the right. To achieve this, every 0 that has 1s to its left needs to "move" past those 1s. For example, in the string 01110, the first 0 is already in its correct position because there are no 1s to its left. However, the last 0 needs to "move" past all the 1s to its left.

In the brute force method, we manually swap the balls step by step until all 0s are on the left and all 1s are on the right. For the example string 01110, this would look like:

  • Step 1: 01110 → 01101 (swap the last 0 with the 1 before it).
  • Step 2: 01101 → 01011 (swap the 0 again with the next 1 before it).
  • Step 3: 01011 → 00111 (final swap).

In total, the last 0 needed to make 3 swaps to cross all the 1s to its left. The total number of swaps is 3.

Instead of manually performing each swap, we can take a more efficient route by directly counting how many 1s are to the left of each 0. This avoids the repetitive swapping and lets us compute the total swaps in one pass through the string.

For the first 0 in the string:

  • There are no 1s before it.
  • Contribution to swaps = 0.

For the last 0 in the string:

  • There are 3 1s before it in the string.
  • Contribution to swaps = 3.
💡
Try it Youself!

How Can We Achieve the Total Number of 1s Before a 0?

To efficiently track the number of 1s we've seen so far:

  • We can use a pointer/variable to count how many 1s we’ve encountered while iterating through the string.
  • As we move from left to right through the string:
    • If the current character is a 1, increment the pointer/variable because we’ve found another 1.
    • If the current character is a 0, we already know the total number of 1s before it — this is the value of the pointer/variable at that moment. Add this value to our answer.

Why Does This Work?

  • Every 1 you see contributes to the total number of swaps for the next 0 you encounter.
  • By keeping a running count of 1s, we don’t need to go back and recount them for each 0. Instead, we simply "remember" how many 1s we’ve seen so far.

Why Is This More Efficient?

The optimized approach focuses on directly counting the number of 1s to the left of each 0 instead of performing the swaps step by step, as in the brute force method. Let's break this down in detail:

In the brute force approach:

  • You physically swap the positions of out-of-order pairs (10) until all the 0s are on the left and all the 1s are on the right.
  • This requires multiple iterations through the string, and each swap involves moving elements and checking their neighbours repeatedly.

In the optimal approach:

  • Instead of manually swapping, you keep a running count of how many 1s you have seen so far.
  • When you encounter a 0, the number of 1s already seen tells you how many swaps would be needed to move that 0 to its correct position — without actually performing the swaps.

Dry run

Input: s = “10110”
Output: 4
Explanation: We can group all the black balls to the right in the following way:
- Swap s[0] and s[1], s = "01110".
- Swap s[3] and s[4], s = "01101".
- Swap s[2] and s[3], s = "01011".
- Swap s[1] and s[2], s = "00111".
Hence, minimum number of steps required = 4.

Initialization:

  • n = 5 (length of the string)
  • minSwaps = 0 (to count the total number of swaps needed)
  • ones = 0 (to count the number of '1's encountered so far)

Step-by-Step Execution:

Iteration 1:

  • i = 0, s[i] = '1'
    • Since s[i] == '1', increment ones by 1.
    • ones = 1
    • minSwaps remains 0 because no '0' is encountered.
  • Current State:
    • minSwaps = 0, ones = 1

Iteration 2:

  • i = 1, s[i] = '0'
    • Since s[i] == '0', add ones to minSwaps.
    • minSwaps = 0 + 1 = 1
    • ones remain unchanged.
  • Current State:
    • minSwaps = 1, ones = 1

Iteration 3:

  • i = 2, s[i] = '1'
    • Since s[i] == '1', increment ones by 1.
    • ones = 2
    • minSwaps remain unchanged.
  • Current State:
    • minSwaps = 1, ones = 2

Iteration 4:

  • i = 3, s[i] = '1'
    • Since s[i] == '1', increment ones by 1.
    • ones = 3
    • minSwaps remain unchanged.
  • Current State:
    • minSwaps = 1, ones = 3

Iteration 5:

  • i = 4, s[i] = '0'
    • Since s[i] == '0', add ones to minSwaps.
    • minSwaps = 1 + 3 = 4
    • ones remain unchanged.
  • Current State:
    • minSwaps = 4, ones = 3

Final Output:

  • After completing the loop, minSwaps = 4.

Steps to write code

Step 1: Initialize the Variables:

  • n: Length of the string s.
  • minSwaps: Set to 0, to store the total swaps required.
  • ones: Set to 0, to count the number of 1s encountered so far.

Step 2: Run a for Loop to Traverse the String:

  • Use a for loop to iterate through the string s from index 0 to n-1.
  • For each character s[i] in the string:

Step 3: Check If the Character is 0:

  • If s[i] is 0, it means this 0 needs to be moved past all the preceding 1s.
  • Add the current count of ones to minSwaps.

Step 4: Check If the Character is 1:

  • If s[i] is 1, increment the count of ones since this 1 might need to be moved later.

Step 5: Return the Total Swaps:

  • After the loop finishes, return the value of minSwaps as the result.
Optimal Approach in All Languages
C++ 
class Solution {
public:
    long long minimumSteps(string s) {
        // Get the size of the input string
        int n = s.size();

        // Initialize variable to store total swaps required
        long long minSwaps = 0;

        // Initialize variable to count the number of '1's encountered
        long long ones = 0;

        // Iterate through each character in the string
        for (int i = 0; i < n; ++i) {
            // If the current character is '0', add the count of '1's to minSwaps
            if (s[i] == '0') 
                minSwaps += ones;
            // Otherwise, increment the count of '1's
            else 
                ones++;
        }

        // Return the total minimum swaps required
        return minSwaps;
    }
};

Java 
class Solution {
    public long minimumSteps(String s) {
        // Get the size of the input string
        int n = s.length();

        // Initialize variable to store total swaps required
        long minSwaps = 0;

        // Initialize variable to count the number of '1's encountered
        long ones = 0;

        // Iterate through each character in the string
        for (int i = 0; i < n; ++i) {
            // If the current character is '0', add the count of '1's to minSwaps
            if (s.charAt(i) == '0') 
                minSwaps += ones;
            // Otherwise, increment the count of '1's
            else 
                ones++;
        }

        // Return the total minimum swaps required
        return minSwaps;
    }
}

Python 
class Solution:
    def minimumSteps(self, s: str) -> int:
        # Get the size of the input string
        n = len(s)

        # Initialize variable to store total swaps required
        min_swaps = 0

        # Initialize variable to count the number of '1's encountered
        ones = 0

        # Iterate through each character in the string
        for i in range(n):
            # If the current character is '0', add the count of '1's to min_swaps
            if s[i] == '0':
                min_swaps += ones
            # Otherwise, increment the count of '1's
            else:
                ones += 1

        # Return the total minimum swaps required
        return min_swaps

Javascript 
/**
 * @param {string} s
 * @return {number}
 */
class Solution {
    minimumSteps(s) {
        // Get the size of the input string
        const n = s.length;

        // Initialize variable to store total swaps required
        let minSwaps = 0;

        // Initialize variable to count the number of '1's encountered
        let ones = 0;

        // Iterate through each character in the string
        for (let i = 0; i < n; ++i) {
            // If the current character is '0', add the count of '1's to minSwaps
            if (s[i] === '0') 
                minSwaps += ones;
            // Otherwise, increment the count of '1's
            else 
                ones++;
        }

        // Return the total minimum swaps required
        return minSwaps;
    }
}

Time Complexity O(n)

Initialization:

  • The variables n, minSwaps, and ones are initialized in constant time:Time Complexity: O(1).

Traversing the String:

  • A for loop is used to traverse the string s of length n.
  • In each iteration:
    • We check whether the current character is 0 or 1 → O(1).
    • If the character is 0, we update minSwaps by adding the current count of ones → O(1).
    • If the character is 1, we increment the value of ones → O(1).
  • The loop iterates exactly n times since it goes through all characters in the string.
  • Time Complexity: O(n).

Returning the Result:

  • After the loop, the function returns the value of minSwaps, which is a constant time operation.Time Complexity: O(1).

Overall Time Complexity

  • Adding up the complexities of the individual steps: O(1)+O(n)+O(1)=O(n)

Thus, the total time complexity of the optimized approach is O(n).

Space Complexity O(1)

Auxiliary Space Complexity

Auxiliary space refers to the extra space used by the algorithm excluding the input. Here's the breakdown:

  1. Variables:
  • Three variables are initialized: n, minSwaps, and ones. These are all integers and occupy O(1) space each.
  • The variables require a constant amount of space irrespective of the input size.
  1. Operations within the Loop:
  • No additional data structures are used within the loop. Only the values of the variables minSwaps and ones are updated during the traversal of the string.

Auxiliary Space Complexity: O(1)

Total Space Complexity

  1. Input Storage
  • The input string s is provided as an argument to the function. This is not considered auxiliary space because it is provided externally and is not created by the algorithm.
  • The input occupies O(n) space, where n is the length of the string.

The total space complexity is the sum of:

  • Auxiliary space O(1).
  • Space for input storage O(n).

Thus, the total space complexity is: O(1)+O(n)=O(n)

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems:-

1. Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the colors red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

2. Move Zeroes

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.