LeetCode 2166 - Design Bitset

LeetCode Problem 2166

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Design

Solution

Problem Understanding

This problem asks us to design a custom Bitset data structure that supports several operations efficiently. A bitset is simply a sequence of binary values, where each position stores either 0 or 1.

We are given a fixed size during initialization, and initially every bit is set to 0. After that, the class must support operations that modify or query the bitset.

The operations are:

• fix(idx) sets the bit at index idx to 1
• unfix(idx) sets the bit at index idx to 0
• flip() inverts every bit in the structure
• all() checks whether every bit is 1
• one() checks whether at least one bit is 1
• count() returns how many bits are currently 1
• toString() returns the full bitset as a string

The important part of the problem is not just correctness, but efficiency. The constraints allow up to 10^5 operations, which means a naive implementation can easily become too slow.

A particularly dangerous operation is flip(). If we physically invert every bit each time flip() is called, then each flip costs O(n). Since there may be many flips, this could lead to O(n * operations) complexity, which is too expensive for the constraints.

The problem also guarantees that toString() is called at most 5 times. This is extremely important because generating the entire string representation naturally costs O(n), and the problem intentionally limits how often this expensive operation occurs.

Several edge cases are important:

• Calling fix() on a bit that is already 1
• Calling unfix() on a bit that is already 0
• Multiple consecutive flip() operations
• A bitset of size 1
• Cases where all bits become 1 or all bits become 0
• Ensuring the count of ones remains correct after flips

The key challenge is designing the data structure so that all frequent operations run in constant time.

Approaches

Brute Force Approach

The most direct solution is to store the bitset as an array of characters or integers and perform each operation literally.

For example:

• fix(idx) directly sets the value at idx to 1
• unfix(idx) directly sets it to 0
• flip() iterates through the entire array and toggles every bit
• all() scans the entire array looking for a 0
• one() scans for a 1
• count() counts all ones every time it is called
• toString() joins the array into a string

This approach is straightforward and obviously correct because every operation directly manipulates the actual state of the bitset.

However, the performance is poor. Operations like flip(), all(), one(), and count() may all require traversing the entire array. With up to 10^5 operations, this becomes too slow.

Key Insight for the Optimal Solution

The crucial observation is that we do not actually need to physically flip every bit when flip() is called.

Instead, we can maintain:

• The original stored bits
• A boolean flag indicating whether the bitset is logically flipped
• A running count of how many bits are currently 1

This lazy flipping strategy allows flip() to become an O(1) operation.

For example:

• Suppose the stored array is "01010"
• If flipped = false, the logical bitset is "01010"
• If flipped = true, the logical bitset becomes "10101"

We never physically modify every element during flip. We only toggle the flag.

Whenever we access a bit, we interpret it according to the flip flag.

This idea dramatically improves performance because:

• flip() becomes constant time
• all(), one(), and count() become constant time using the maintained count
• Only toString() requires traversing the entire array

Since toString() is called at most 5 times, this is completely acceptable.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per operation in worst case	O(n)	Physically flips and scans entire array frequently
Optimal	O(1) for most operations, O(n) for toString()	O(n)	Uses lazy flipping and maintains count of ones

Algorithm Walkthrough

1. Initialize the bitset using an array of bits, all set to 0.

We store the bits in a list or slice. We also maintain:

• flipped, a boolean indicating whether the logical state is inverted
• ones, the current number of logical 1 bits
• size, the total number of bits

2. When fix(idx) is called, determine the current logical value at idx.

The stored bit may not match the logical bit because of flips. If:

• flipped == false, the stored bit is the actual bit
• flipped == true, the logical bit is inverted

If the logical bit is already 1, do nothing.

Otherwise, modify the stored value so the logical bit becomes 1, and increment ones. 3. When unfix(idx) is called, again determine the logical value.

If the logical bit is already 0, do nothing.

Otherwise, modify the stored value so the logical bit becomes 0, and decrement ones. 4. When flip() is called, do not iterate through the array.

Instead:

• Toggle the flipped flag
• Update ones to size - ones

This works because every 1 becomes 0, and every 0 becomes 1. 5. For all(), simply check whether ones == size.

Since we always maintain the correct count, no scanning is necessary. 6. For one(), check whether ones > 0. 7. For count(), return ones. 8. For toString(), build the logical representation of every bit.

Traverse the stored array and interpret each value according to the flipped flag.

Why it works

The core invariant is that the stored array combined with the flipped flag always uniquely determines the logical bitset.

If flipped == false, the logical value equals the stored value.

If flipped == true, the logical value equals the inverse of the stored value.

Additionally, the ones variable always tracks the number of logical 1 bits. Every operation updates this count consistently, so query operations never need to scan the entire structure.

Because these invariants are preserved after every operation, the implementation is correct.

Python Solution

class Bitset:

    def __init__(self, size: int):
        self.bits = [0] * size
        self.size = size
        self.flipped = False
        self.ones = 0

    def fix(self, idx: int) -> None:
        current = self.bits[idx]

        logical_value = current ^ self.flipped

        if logical_value == 1:
            return

        self.bits[idx] ^= 1
        self.ones += 1

    def unfix(self, idx: int) -> None:
        current = self.bits[idx]

        logical_value = current ^ self.flipped

        if logical_value == 0:
            return

        self.bits[idx] ^= 1
        self.ones -= 1

    def flip(self) -> None:
        self.flipped = not self.flipped
        self.ones = self.size - self.ones

    def all(self) -> bool:
        return self.ones == self.size

    def one(self) -> bool:
        return self.ones > 0

    def count(self) -> int:
        return self.ones

    def toString(self) -> str:
        result = []

        for bit in self.bits:
            logical_bit = bit ^ self.flipped
            result.append(str(logical_bit))

        return "".join(result)

The implementation stores the raw bits in self.bits. These bits are not always the visible logical bits because the structure may be flipped.

The flipped boolean tracks whether the entire bitset is logically inverted. Instead of physically changing every bit during a flip, we interpret each bit dynamically using XOR.

The expression:

bit ^ self.flipped

computes the logical value:

• If flipped is False, XOR changes nothing
• If flipped is True, XOR inverts the bit

The fix() and unfix() methods first determine the current logical value. They only modify the bit if a real change is needed. This prevents incorrect updates to the ones counter.

The flip() operation is extremely efficient because it only toggles a boolean and recalculates the number of ones mathematically.

The toString() method is the only operation that traverses the full array, which is acceptable because the problem guarantees very few calls to it.

Go Solution

package main

import "strings"

type Bitset struct {
	bits     []int
	size     int
	flipped  bool
	ones     int
}

func Constructor(size int) Bitset {
	return Bitset{
		bits:    make([]int, size),
		size:    size,
		flipped: false,
		ones:    0,
	}
}

func (this *Bitset) Fix(idx int) {
	logicalValue := this.bits[idx]

	if this.flipped {
		logicalValue ^= 1
	}

	if logicalValue == 1 {
		return
	}

	this.bits[idx] ^= 1
	this.ones++
}

func (this *Bitset) Unfix(idx int) {
	logicalValue := this.bits[idx]

	if this.flipped {
		logicalValue ^= 1
	}

	if logicalValue == 0 {
		return
	}

	this.bits[idx] ^= 1
	this.ones--
}

func (this *Bitset) Flip() {
	this.flipped = !this.flipped
	this.ones = this.size - this.ones
}

func (this *Bitset) All() bool {
	return this.ones == this.size
}

func (this *Bitset) One() bool {
	return this.ones > 0
}

func (this *Bitset) Count() int {
	return this.ones
}

func (this *Bitset) ToString() string {
	var builder strings.Builder

	for _, bit := range this.bits {
		logicalBit := bit

		if this.flipped {
			logicalBit ^= 1
		}

		if logicalBit == 1 {
			builder.WriteByte('1')
		} else {
			builder.WriteByte('0')
		}
	}

	return builder.String()
}

The Go implementation follows the exact same logic as the Python version.

One notable difference is string construction. In Go, repeated string concatenation is inefficient because strings are immutable. Therefore, strings.Builder is used to efficiently build the final bitset string.

The bit storage uses []int for simplicity. Since only 0 and 1 are stored, this is perfectly sufficient.

Go also requires explicit pointer receivers for methods that modify the structure.

Worked Examples

Example 1

Input:

["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"]
[[5], [3], [1], [], [], [0], [], [], [0], [], []]

Initial state:

Step	Operation	Stored Bits	Flipped	Logical Bits	Ones
1	Initialize	00000	false	00000	0

Call fix(3):

Step	Operation	Stored Bits	Flipped	Logical Bits	Ones
2	fix(3)	00010	false	00010	1

Call fix(1):

Step	Operation	Stored Bits	Flipped	Logical Bits	Ones
3	fix(1)	01010	false	01010	2

Call flip():

Step	Operation	Stored Bits	Flipped	Logical Bits	Ones
4	flip()	01010	true	10101	3

Call all():

ones = 3
size = 5
3 != 5
return false

Call unfix(0):

Current logical bit at index 0 is 1.

Step	Operation	Stored Bits	Flipped	Logical Bits	Ones
5	unfix(0)	11010	true	00101	2

Call flip():

Step	Operation	Stored Bits	Flipped	Logical Bits	Ones
6	flip()	11010	false	11010	3

Call one():

ones = 3
return true

Call unfix(0):

Step	Operation	Stored Bits	Flipped	Logical Bits	Ones
7	unfix(0)	01010	false	01010	2

Call count():

return 2

Call toString():

return "01010"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) for most operations, O(n) for toString()	Lazy flipping avoids full traversal except when generating the string
Space	O(n)	The bit array stores all bits

The key optimization is that flip() does not physically modify the array. Instead, it only toggles a boolean flag. This converts what would normally be an O(n) operation into O(1).

Operations such as all(), one(), and count() are also constant time because the implementation maintains the number of logical ones incrementally.

Only toString() requires iterating over all bits, which is acceptable because the problem limits the number of calls.

Test Cases

# Example from problem statement
bs = Bitset(5)
bs.fix(3)
bs.fix(1)
bs.flip()
assert bs.all() is False          # not all bits are 1
bs.unfix(0)
bs.flip()
assert bs.one() is True           # at least one bit is 1
bs.unfix(0)
assert bs.count() == 2            # exactly two ones
assert bs.toString() == "01010"   # final string state

# Single element bitset
bs = Bitset(1)
assert bs.toString() == "0"       # initial value
bs.fix(0)
assert bs.toString() == "1"       # fixed to 1
assert bs.all() is True           # all bits are 1
bs.flip()
assert bs.toString() == "0"       # flipped back

# Multiple flips
bs = Bitset(4)
bs.flip()
assert bs.toString() == "1111"    # all bits flipped
bs.flip()
assert bs.toString() == "0000"    # flipped back

# Fix already fixed bit
bs = Bitset(3)
bs.fix(1)
bs.fix(1)
assert bs.count() == 1            # count should not increase twice

# Unfix already unfixed bit
bs = Bitset(3)
bs.unfix(2)
assert bs.count() == 0            # should remain zero

# All bits become 1
bs = Bitset(3)
bs.fix(0)
bs.fix(1)
bs.fix(2)
assert bs.all() is True           # every bit is 1

# All bits become 0 after flip
bs.flip()
assert bs.toString() == "000"     # flipped all ones to zeros
assert bs.one() is False          # no ones remain

# Stress logical flip handling
bs = Bitset(6)
bs.fix(2)
bs.fix(4)
bs.flip()
assert bs.toString() == "110101"  # verify logical inversion
assert bs.count() == 4            # four ones after flip

Test	Why
Problem statement example	Verifies overall correctness
Single element bitset	Tests smallest possible size
Multiple flips	Ensures lazy flip logic works repeatedly
Fix already fixed bit	Prevents incorrect count updates
Unfix already unfixed bit	Ensures no accidental decrement
All bits become 1	Validates all()
All bits become 0 after flip	Validates flip inversion correctness
Stress logical flip handling	Tests interaction between fix and flip

Edge Cases

One important edge case occurs when fix() is called on a bit that is already logically 1. A naive implementation might increment the count again, producing incorrect results. The solution avoids this by first computing the logical value of the bit and returning immediately if no change is necessary.

Another subtle case involves repeated flip() operations. If the implementation physically flips all bits every time, performance degrades significantly. Additionally, repeated inversions can easily introduce bugs if the count of ones is not updated correctly. The lazy flip approach handles this cleanly by toggling a single boolean and recalculating the count as size - ones.

A third important edge case is when the bitset size is 1. Small structures often expose indexing or logic errors that remain hidden in larger examples. The implementation works correctly even for a single bit because all operations rely on consistent logical interpretation rather than assumptions about size.

Another tricky scenario occurs when unfix() is called after a flip. The stored bit may appear to be 0, but logically it could represent 1 because the bitset is flipped. The implementation always computes the logical value before deciding whether a modification is necessary, ensuring correctness regardless of how many flips occurred previously.