Minimum Operations to Equalize Binary String solution and explanation
Infosys
Google
9 more videos on this problem
Minimum Operations to Equalize Binary String | Brute Force | Optimal | Intuition | Leetcode 3666codestorywithMIK · 1:13:04 · 12K views
Minimum Operations to Equalize Binary String | LeetCode 3666 | BFSSanyam IIT Guwahati · 29:04 · 1K views
3666. Minimum Operations to Equalize Binary String | Leetcode Daily - PythonLeetcode Daily · 7:34 · 1K views
leetcode 3666 | Minimum Operations to Equalize Binary String | BFS | Binary Search| Leetcode POTDCode With Vick · 39:05 · 1K views
Minimum Operations to Equalize Binary String | LeetCode 3666 - Pythonimpoldev · 12:27 · 1K views
Leetcode 3666 | Minimum Operations to Equalize Binary String | Biweekly contest 164CodeWithMeGuys · 18:48 · 979 views
Daily Leetcode #2159: Feb 27, 2026 - 3666. Minimum Operations to Equalize Binary StringProgramming Live with Larry · 55:35 · 713 views
3666. Minimum Operations to Equalize Binary String (Leetcode Hard)Programming Live with Larry · 3:21:23 · 483 views
Minimum Operations to Equalize Binary String | Q4 of Biweekly Contest 164 | Leetcode 3666ExpertFunda · 8:04 · 413 views
Minimum Operations to Equalize Binary String - Leetcode 3666 - PythonTim Huang · 6:59 · 257 views
The problem
You are given a binary string s, and an integer k.
In one operation, you must choose exactly k different indices and flip each '0' to '1' and each '1' to '0'.
Return the minimum number of operations required to make all characters in the string equal to '1'. If it is not possible, return -1.
Example 1:
Input: s = "110", k = 1
Output: 1
Explanation:
- There is one
'0'ins. - Since
k = 1, we can flip it directly in one operation.
Example 2:
Input: s = "0101", k = 3
Output: 2
Explanation:
One optimal set of operations choosing k = 3 indices in each operation is:
- Operation 1: Flip indices
[0, 1, 3].schanges from"0101"to"1000". - Operation 2: Flip indices
[1, 2, 3].schanges from"1000"to"1111".
Thus, the minimum number of operations is 2.
Example 3:
Input: s = "101", k = 2
Output: -1
Explanation:
Since k = 2 and s has only one '0', it is impossible to flip exactly k indices to make all '1'. Hence, the answer is -1.
Constraints:
1 <= s.length <= 105s[i]is either'0'or'1'.1 <= k <= s.length
Approach overview
Problem Overview: You are given a binary string and must compute the minimum number of operations required to transform it so all positions satisfy the equality condition defined in the problem. Each operation modifies positions in the string, and the challenge is finding the smallest sequence of transformations that leads to a valid equalized state.
Approach 1: Brute Force State Exploration (Exponential Time, O(2^n) time, O(2^n) space)
The most direct strategy treats every possible binary configuration as a state and explores transformations until an equalized string appears. A breadth-first search can generate neighboring states by applying every valid operation. Because the number of binary strings grows exponentially, this approach quickly becomes infeasible for large inputs. It is mainly useful for reasoning about correctness and validating small examples.
Approach 2: Component Grouping with Union Find (O(n α(n)) time, O(n) space)
Many constraints in binary string transformation problems effectively tie multiple indices together. If operations force certain positions to always change together, those indices can be merged into the same component using Union Find. After grouping indices, count how many 0s and 1s appear inside each component and compute the minimum flips required to make the component consistent. This dramatically reduces the state space because decisions are made per component instead of per index.
Approach 3: BFS with Ordered Set (O(n log n) time, O(n) space)
The optimized approach models the problem as a shortest-path search over indices that still violate the equality condition. Use Breadth-First Search to process positions whose value mismatches the required target. An ordered set keeps remaining unresolved indices sorted so you can quickly locate the next reachable positions affected by an operation. Each BFS expansion applies an operation, removes resolved indices from the set, and pushes newly affected positions into the queue. Because every index is inserted and removed at most once and ordered set operations cost O(log n), the total complexity becomes O(n log n).
Recommended for interviews: Interviewers expect the BFS + ordered set formulation. Brute force shows you understand the state-space model, while the optimized solution demonstrates the ability to prune transitions and manage active indices efficiently. The key insight is representing unresolved positions as a searchable structure and expanding them with BFS to guarantee the minimum number of operations.
Solution
We denote the length of string s as n, and the current number of '0's in the string as cur. In each operation, we select k indices to flip, where x indices flip from '0' to '1', and k-x indices flip from '1' to '0'. Then the number of '0's in the string after flipping is cur + k - 2x.
The value of x needs to satisfy the following conditions:
- At most
min(cur, k)'0's can be taken, because we cannot flip more thancur'0's, so0 leq x leq min(cur, k). - At most
n - cur'1's can be taken, because we cannot flip more thann - cur'1's, sok - x leq n - cur, i.e.,x geq k - n + cur.
Therefore, the range of x is [max(k - n + cur, 0), min(cur, k)], and the range of the number of '0's in the string after flipping is [cur + k - 2 cdot min(cur, k), cur + k - 2 cdot max(k - n + cur, 0)].
We notice that the parity of the number of '0's in the string after flipping is the same as the parity of the number of '0's in the string before flipping. Therefore, we can use two ordered sets to store states where the number of '0's is even and odd, respectively.
We use BFS to search the state transition graph, where the initial state is the number of '0's in the string, and the target state is 0. Each time we dequeue a state cur, we calculate the range [l, r] of the number of '0's in the string after flipping, find all states in the range [l, r] in the ordered set, add them to the queue, and remove them from the ordered set.
If we visit state 0 during the BFS process, we return the current number of operations; if state 0 is not visited after BFS ends, we return -1.
The time complexity is O(n log n), and the space complexity is O(n), where O(n) is the number of states that may be visited during the BFS process, and O(log n) is the time complexity of inserting and deleting elements in the ordered set.
class Solution:
def minOperations(self, s: str, k: int) -> int:
n = len(s)
ts = [SortedSet() for _ in range(2)]
for i in range(n + 1):
ts[i % 2].add(i)
cnt0 = s.count('0')
ts[cnt0 % 2].remove(cnt0)
q = deque([cnt0])
ans = 0
while q:
for _ in range(len(q)):
cur = q.popleft()
if cur == 0:
return ans
l = cur + k - 2 * min(cur, k)
r = cur + k - 2 * max(k - n + cur, 0)
t = ts[l % 2]
j = t.bisect_left(l)
while j < len(t) and t[j] <= r:
q.append(t[j])
t.remove(t[j])
ans += 1
return -1class Solution {
public int minOperations(String s, int k) {
int n = s.length();
TreeSet<Integer>[] ts = new TreeSet[2];
Arrays.setAll(ts, i -> new TreeSet<>());
for (int i = 0; i <= n; i++) {
ts[i % 2].add(i);
}
int cnt0 = 0;
for (char c : s.toCharArray()) {
if (c == '0') {
cnt0++;
}
}
ts[cnt0 % 2].remove(cnt0);
Deque<Integer> q = new ArrayDeque<>();
q.offer(cnt0);
int ans = 0;
while (!q.isEmpty()) {
for (int size = q.size(); size > 0; --size) {
int cur = q.poll();
if (cur == 0) {
return ans;
}
int l = cur + k - 2 * Math.min(cur, k);
int r = cur + k - 2 * Math.max(k - n + cur, 0);
TreeSet<Integer> t = ts[l % 2];
Integer next = t.ceiling(l);
while (next != null && next <= r) {
q.offer(next);
t.remove(next);
next = t.ceiling(l);
}
}
ans++;
}
return -1;
}
}class Solution {
public:
int minOperations(string s, int k) {
int n = s.size();
set<int> ts[2];
for (int i = 0; i <= n; i++) {
ts[i % 2].insert(i);
}
int cnt0 = count(s.begin(), s.end(), '0');
ts[cnt0 % 2].erase(cnt0);
queue<int> q;
q.push(cnt0);
int ans = 0;
while (!q.empty()) {
for (int size = q.size(); size > 0; --size) {
int cur = q.front();
q.pop();
if (cur == 0) {
return ans;
}
int l = cur + k - 2 * min(cur, k);
int r = cur + k - 2 * max(k - n + cur, 0);
auto& t = ts[l % 2];
auto it = t.lower_bound(l);
while (it != t.end() && *it <= r) {
q.push(*it);
it = t.erase(it);
}
}
ans++;
}
return -1;
}
};import { AvlTree } from '@datastructures-js/binary-search-tree';
function minOperations(s: string, k: number): number {
const n: number = s.length;
const ts = [new AvlTree<number>(), new AvlTree<number>()];
for (let i = 0; i <= n; i++) {
ts[i % 2].insert(i);
}
let cnt0 = 0;
for (const c of s) {
if (c === '0') cnt0++;
}
ts[cnt0 % 2].remove(cnt0);
let q: number[] = [cnt0];
let ans = 0;
while (q.length > 0) {
const nq: number[] = [];
for (const cur of q) {
if (cur === 0) {
return ans;
}
const l = cur + k - 2 * Math.min(cur, k);
const r = cur + k - 2 * Math.max(k - n + cur, 0);
const t = ts[l % 2];
let node = t.upperBound(l, true);
while (node && node.getValue() <= r) {
const val = node.getValue();
nq.push(val);
t.remove(val);
node = t.upperBound(l, false);
}
}
q = nq;
ans++;
}
return -1;
}public class Solution {
public int MinOperations(string s, int k) {
int n = s.Length;
var ts = new SortedSet<int>[2];
ts[0] = new SortedSet<int>();
ts[1] = new SortedSet<int>();
for (int i = 0; i <= n; i++) {
ts[i % 2].Add(i);
}
int cnt0 = 0;
foreach (char c in s) {
if (c == '0') {
cnt0++;
}
}
ts[cnt0 % 2].Remove(cnt0);
var q = new Queue<int>();
q.Enqueue(cnt0);
int ans = 0;
while (q.Count > 0) {
int size = q.Count;
for (int i = 0; i < size; i++) {
int cur = q.Dequeue();
if (cur == 0) {
return ans;
}
int l = cur + k - 2 * Math.Min(cur, k);
int r = cur + k - 2 * Math.Max(k - n + cur, 0);
var t = ts[l % 2];
var toRemove = new List<int>();
foreach (int next in t.GetViewBetween(l, r)) {
q.Enqueue(next);
toRemove.Add(next);
}
foreach (int next in toRemove) {
t.Remove(next);
}
}
ans++;
}
return -1;
}
}func minOperations(s string, k int) int {
n := len(s)
ts := [2]*redblacktree.Tree{
redblacktree.NewWithIntComparator(),
redblacktree.NewWithIntComparator(),
}
for i := 0; i <= n; i++ {
ts[i%2].Put(i, struct{}{})
}
cnt0 := strings.Count(s, "0")
ts[cnt0%2].Remove(cnt0)
q := []int{cnt0}
ans := 0
for len(q) > 0 {
nq := []int{}
for _, cur := range q {
if cur == 0 {
return ans
}
l := cur + k - 2*min(cur, k)
r := cur + k - 2*max(k-n+cur, 0)
t := ts[l%2]
node, found := t.Ceiling(l)
for found && node.Key.(int) <= r {
val := node.Key.(int)
nq = append(nq, val)
t.Remove(val)
node, found = t.Ceiling(l)
}
}
q = nq
ans++
}
return -1
}use std::collections::{BTreeSet, VecDeque};
impl Solution {
pub fn min_operations(s: String, k: i32) -> i32 {
let n: i32 = s.len() as i32;
let k: i32 = k;
let mut ts: [BTreeSet<i32>; 2] = [BTreeSet::new(), BTreeSet::new()];
for i in 0..=n {
ts[(i % 2) as usize].insert(i);
}
let cnt0: i32 = s.bytes().filter(|&c| c == b'0').count() as i32;
ts[(cnt0 % 2) as usize].remove(&cnt0);
let mut q: VecDeque<i32> = VecDeque::new();
q.push_back(cnt0);
let mut ans: i32 = 0;
while !q.is_empty() {
let size = q.len();
for _ in 0..size {
let cur = q.pop_front().unwrap();
if cur == 0 {
return ans;
}
let l = cur + k - 2 * cur.min(k);
let r = cur + k - 2 * (k - n + cur).max(0);
let parity = (l % 2) as usize;
let vals: Vec<i32> = ts[parity]
.range(l..=r)
.cloned()
.collect();
for v in vals {
q.push_back(v);
ts[parity].remove(&v);
}
}
ans += 1;
}
-1
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force State Exploration | O(2^n) | O(2^n) | Only for reasoning about small inputs or verifying correctness |
| Union Find Component Grouping | O(n α(n)) | O(n) | When operations link indices into forced groups |
| BFS + Ordered Set | O(n log n) | O(n) | General optimal solution for large strings with dynamic index updates |
Frequently asked questions
Is Minimum Operations to Equalize Binary String easy or hard?
Minimum Operations to Equalize Binary String is categorized as a Hard problem. It combines string processing with graph traversal and advanced data structures such as ordered sets or union find. The difficulty comes from modeling the operations efficiently and avoiding exponential state exploration.
Minimum Operations to Equalize Binary String Python/Java solution
Python implementations commonly use collections.deque for BFS and sorted containers or tree-like structures to simulate an ordered set. Java solutions typically rely on TreeSet for ordered index management along with a queue for BFS traversal. Both achieve O(n log n) time complexity.
How to solve Minimum Operations to Equalize Binary String in O(n)?
Pure O(n) solutions are difficult because efficient index lookup and removal are required during state expansion. Most optimal implementations rely on ordered sets or balanced trees, leading to O(n log n) complexity. BFS ensures minimal operations while the ordered structure maintains the next unresolved indices efficiently.
What is the best approach for Minimum Operations to Equalize Binary String?
The most efficient approach uses Breadth-First Search combined with an ordered set to track unresolved indices. BFS guarantees the minimum number of operations, while the ordered set allows fast insertion, deletion, and neighbor lookup. This combination processes each index once and results in O(n log n) time complexity with O(n) space.
Is Minimum Operations to Equalize Binary String asked at Google/Amazon/Meta?
Hard string and graph-style transformation problems similar to this appear frequently in Google, Amazon, and Meta interview rounds. They test your ability to model a problem as a graph, apply BFS for shortest operations, and optimize index tracking with advanced data structures.
What data structure is used in Minimum Operations to Equalize Binary String?
The optimized solution typically uses a BFS queue plus an ordered set or balanced tree structure. The queue handles level-by-level exploration of operations, while the ordered set stores unresolved indices and supports fast range queries and deletions in O(log n).
What is the time complexity of Minimum Operations to Equalize Binary String?
The optimal solution runs in O(n log n) time using BFS with an ordered set. Each index is inserted and removed from the ordered structure at most once, and each such operation costs O(log n). The overall space complexity is O(n) for the queue and index tracking structures.