Design Bitset - Solution & Explanation

Q: Is Design Bitset easy or hard?

Design Bitset is rated Medium because the operations themselves are simple but require careful state management. Many candidates initially implement a full flip in O(n), but the intended solution optimizes this using lazy flipping and counters.

Q: Design Bitset Python/Java solution

The solution in Python or Java typically uses a list or array to store bits, an integer counter for the number of 1s, and a boolean flip flag. Methods like fix, unfix, and flip update the array logically using the flag while keeping operations O(1).

Q: How to solve Design Bitset in O(1)?

Maintain an array for the stored bits, a boolean flag indicating whether the bitset is logically flipped, and a counter for the number of 1s. Fix and unfix operations check the flip flag before updating the underlying value. Flip simply toggles the flag and recalculates the count as n minus the current count.

Q: What is the best approach for Design Bitset?

The optimal solution uses a lazy flip technique with a boolean flag and a running count of 1s. Instead of flipping every bit, the algorithm toggles a flip flag and adjusts the count using n - count. This makes fix, unfix, flip, all, one, and count operations O(1) while keeping space complexity at O(n).

Q: Is Design Bitset asked at Google/Amazon/Meta?

Bit manipulation and custom data structure design problems appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, similar tasks involving efficient state updates and lazy operations are common in system design and algorithm rounds.

Q: What data structure is used in Design Bitset?

The core structure is an array or list storing binary values. The optimized solution augments this with a boolean flip flag and a counter tracking how many bits are set to 1. This combination allows constant-time updates and queries.

Q: What is the time complexity of Design Bitset?

With the optimized lazy flip design, all update and query operations run in O(1) time. The only O(n) operation is toString(), since it must construct the entire bitset string. Space complexity remains O(n) because the structure stores the bitset array.

MediumArray Hash Table String Design19 min read

Practice this problem

Problem Statement

A Bitset is a data structure that compactly stores bits.

Implement the Bitset class:

Bitset(int size) Initializes the Bitset with size bits, all of which are 0.
void fix(int idx) Updates the value of the bit at the index idx to 1. If the value was already 1, no change occurs.
void unfix(int idx) Updates the value of the bit at the index idx to 0. If the value was already 0, no change occurs.
void flip() Flips the values of each bit in the Bitset. In other words, all bits with value 0 will now have value 1 and vice versa.
boolean all() Checks if the value of each bit in the Bitset is 1. Returns true if it satisfies the condition, false otherwise.
boolean one() Checks if there is at least one bit in the Bitset with value 1. Returns true if it satisfies the condition, false otherwise.
int count() Returns the total number of bits in the Bitset which have value 1.
String toString() Returns the current composition of the Bitset. Note that in the resultant string, the character at the i^th index should coincide with the value at the i^th bit of the Bitset.

Example 1:

Input
["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"]
[[5], [3], [1], [], [], [0], [], [], [0], [], []]
Output
[null, null, null, null, false, null, null, true, null, 2, "01010"]

Explanation
Bitset bs = new Bitset(5); // bitset = "00000".
bs.fix(3);     // the value at idx = 3 is updated to 1, so bitset = "00010".
bs.fix(1);     // the value at idx = 1 is updated to 1, so bitset = "01010". 
bs.flip();     // the value of each bit is flipped, so bitset = "10101". 
bs.all();      // return False, as not all values of the bitset are 1.
bs.unfix(0);   // the value at idx = 0 is updated to 0, so bitset = "00101".
bs.flip();     // the value of each bit is flipped, so bitset = "11010". 
bs.one();      // return True, as there is at least 1 index with value 1.
bs.unfix(0);   // the value at idx = 0 is updated to 0, so bitset = "01010".
bs.count();    // return 2, as there are 2 bits with value 1.
bs.toString(); // return "01010", which is the composition of bitset.

Constraints:

1 <= size <= 10⁵
0 <= idx <= size - 1
At most 10⁵ calls will be made in total to fix, unfix, flip, all, one, count, and toString.
At least one call will be made to all, one, count, or toString.
At most 5 calls will be made to toString.

Approach Overview

Problem Overview: Design a data structure that represents a binary bitset of size n. The structure must support operations like fix, unfix, flip, all, one, count, and toString. Each operation should update or query the bitset efficiently while maintaining correct counts of 0s and 1s.

Approach 1: Array-based Manipulation (O(1) per operation, O(n) flip)

Store the bitset directly in an array or string-like structure where each index represents a bit. Operations like fix(i) and unfix(i) simply update the value at index i and adjust a running counter of 1s. Queries like all(), one(), and count() read from this counter, so they run in constant time. The expensive operation is flip(), which requires iterating through the entire array and toggling every bit, giving O(n) time while other operations remain O(1). Space complexity is O(n) for storing the bitset. This approach is straightforward and easy to implement using basic array operations.

Approach 2: Optimized Lazy Flip with Counters (O(1) per operation)

The key observation is that physically flipping every bit is unnecessary. Instead, maintain a boolean flipped flag that represents whether the logical bitset is inverted. When the flag is true, the stored bit value means the opposite of what it normally represents. The fix and unfix operations interpret the current value using this flag and update the underlying array accordingly. Maintain a running count of 1s so count(), all(), and one() remain constant time. The flip() operation simply toggles the flag and recalculates the number of 1s as n - count, avoiding any iteration. Every operation runs in O(1) time with O(n) space. This technique is common in design problems where you defer expensive work until necessary.

The toString() method constructs the output by iterating through the stored array and applying the flip logic if needed. This step takes O(n) time, which is unavoidable since the full string must be produced. Implementation typically uses arrays or mutable strings, and the logic resembles techniques used in string manipulation tasks.

Recommended for interviews: Interviewers expect the lazy flip design. The naive array approach shows you understand the required operations, but the optimized version demonstrates strong system design thinking. Avoiding repeated O(n) flips and maintaining counters for constant-time queries shows the ability to optimize state-heavy data structures.

Approach 1: Array-based Manipulation

In this approach, we use a simple array to track the state of each bit in the Bitset. Operations like fix and unfix directly update this array, while flipping involves inverting each bit in the array. The overhead for each operation is straightforward but may require full traversal for some methods like flip.

This solution uses a straightforward approach of maintaining an array representing the bitset. Each bit's state can be modified using simple index operations. To implement flip, each bit is iterated and inverted. The operations of fix, unfix, and flip all work in O(n) time, while count and toString iterate over the array to compile results or construct strings from the array.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time complexity: O(n) for operations like flip and toString;
Space complexity: O(n) for storing the bits array.

Try this approach in the editor →

Approach 2: Optimized Lazy Flip with Counters

This approach optimizes the flip operation by using a lazy strategy. We maintain a 'flipped' boolean alongside the bitset to track the flip state. Instead of flipping bits immediately, we interpret bit values conditioned on the flip state. Additional counters track the number of 1s and handle state adjustments efficiently.

This optimized approach maintains a flipped state and conditionally adjusts each operation to reflect this state. By tracking 'flipped', operations like flip become O(1), as the actual bit inversion calculation is deferred. A counter, onesCount, tracks the number of 1s, aiding direct implementation of all, one, and count methods.

Code

C++Java Python JavaScript

C++

Java

Python

JavaScript

Complexity

Time complexity: O(1) for most operations, O(n) for toString due to construction;
Space complexity: O(n) for storing bit representations.

Try this approach in the editor →

Approach 3: Default Approach

Code

Python Java C++Go

Python

Java

C++

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Array-based Manipulation	Time complexity: O(n) for operations like flip and toString; Space complexity: O(n) for storing the bits array.
Optimized Lazy Flip with Counters	Time complexity: O(1) for most operations, O(n) for toString due to construction; Space complexity: O(n) for storing bit representations.
Default Approach	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Array-based Manipulation	O(1) operations, O(n) flip	O(n)	Simple implementation when performance of flip is not critical
Lazy Flip with Counters	O(1) per operation	O(n)	Preferred for interviews and large inputs where repeated flips would be expensive

Video Solution

花花酱 LeetCode 2166. Design Bitset - 刷题找工作 EP399 • Hua Hua • 1,504 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Design Bitset easy or hard?

Design Bitset is rated Medium because the operations themselves are simple but require careful state management. Many candidates initially implement a full flip in O(n), but the intended solution optimizes this using lazy flipping and counters.

Design Bitset Python/Java solution

The solution in Python or Java typically uses a list or array to store bits, an integer counter for the number of 1s, and a boolean flip flag. Methods like fix, unfix, and flip update the array logically using the flag while keeping operations O(1).

How to solve Design Bitset in O(1)?

Maintain an array for the stored bits, a boolean flag indicating whether the bitset is logically flipped, and a counter for the number of 1s. Fix and unfix operations check the flip flag before updating the underlying value. Flip simply toggles the flag and recalculates the count as n minus the current count.

What is the best approach for Design Bitset?

The optimal solution uses a lazy flip technique with a boolean flag and a running count of 1s. Instead of flipping every bit, the algorithm toggles a flip flag and adjusts the count using n - count. This makes fix, unfix, flip, all, one, and count operations O(1) while keeping space complexity at O(n).

Is Design Bitset asked at Google/Amazon/Meta?

Bit manipulation and custom data structure design problems appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, similar tasks involving efficient state updates and lazy operations are common in system design and algorithm rounds.

What data structure is used in Design Bitset?

The core structure is an array or list storing binary values. The optimized solution augments this with a boolean flip flag and a counter tracking how many bits are set to 1. This combination allows constant-time updates and queries.

What is the time complexity of Design Bitset?

With the optimized lazy flip design, all update and query operations run in O(1) time. The only O(n) operation is toString(), since it must construct the entire bitset string. Space complexity remains O(n) because the structure stores the bitset array.

Ready to solve this problem?

Practice Design Bitset with our built-in code editor and test cases.

Practice on FleetCode

Design Underground System

Problem Info

DifficultyMedium

Acceptance32.7%

Approaches3

Reading time19 min

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Array-based Manipulation

Code

Complexity

Approach 2: Optimized Lazy Flip with Counters

Code

Complexity

Approach 3: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents