Watch 9 video solutions for Design Bitset, a medium level problem involving Array, Hash Table, String. This walkthrough by Hua Hua has 1,498 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 ith index should coincide with the value at the ith 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 <= 1050 <= idx <= size - 1105 calls will be made in total to fix, unfix, flip, all, one, count, and toString.all, one, count, or toString.5 calls will be made to toString.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 | 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 |