Katkat
Back

Minimum Movement Cost to Segregate Binary Digits

Akuna CapitalSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests greedy algorithm design and sequence optimization by calculating the cumulative distance required to shift all '1's to the end of a binary string.

Problem Statement

Given a binary string s consisting of '0's and '1's, you want to reorganize the string such that all '0's appear before all '1's. The only allowed operation is to swap a '1' with an adjacent '0'. Each swap has a cost of 1. Calculate the minimum total cost required to reach a state where all '0's precede all '1's.

Function Signature

def min_swap_cost(s: str) -> int:

Constraints

  • 1 <= len(s) <= 10^6
  • The string contains only '0' and '1'.

Examples

Example 1: Input: s = "1010" Output: 3 Explanation:

  1. Swap index 0 and 1: "0110" (cost 1)
  2. Swap index 2 and 3: "0101" (cost 2)
  3. Swap index 1 and 2: "0011" (cost 3)

Example 2: Input: s = "000" Output: 0 Explanation: Already sorted.

Edge Cases

  • Empty strings or strings with no '1's.
  • Strings already in the form "00...11...".
  • Strings with all '1's.

Hints

Hint 1

Instead of simulating the swaps, consider how many positions each '1' must move to reach its final sorted position.

Hint 2

The target position for the i-th '1' (from the left) is index `(len(s) - num_ones + i)`.

Hint 3

You can solve this in a single pass by keeping track of the count of '1's encountered so far and adding the distance to the target for each '1' found.

Follow-up questions

  • How would the logic change if swapping a '1' with a '0' had a variable cost depending on the index?
  • Can you optimize the solution to use O(1) extra space?
  • What if you were asked to move all '0's to the end instead? Would the complexity change?