Design Bitset — LeetCode 2166 Python Solution

MediumDesignArrayHash TableString
Problem
#2166
Pattern
Hash Map
Reading time
8 min

The problem

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.

Example

Input
["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"]
Output
[null, null, null, null, false, null, null, true, null, 2, "01010"]
Explanation
Bitset bs = new Bitset(5); // bitset = "00000".

Python solution

Python
class Bitset:
    def __init__(self, size: int):
        self.a = ['0'] * size
        self.b = ['1'] * size
        self.cnt = 0

    def fix(self, idx: int) -> None:
        if self.a[idx] == '0':
            self.a[idx] = '1'
            self.cnt += 1
        self.b[idx] = '0'

    def unfix(self, idx: int) -> None:
        if self.a[idx] == '1':
            self.a[idx] = '0'
            self.cnt -= 1
        self.b[idx] = '1'

    def flip(self) -> None:
        self.a, self.b = self.b, self.a
        self.cnt = len(self.a) - self.cnt

    def all(self) -> bool:
        return self.cnt == len(self.a)

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

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

    def toString(self) -> str:
        return ''.join(self.a)


# Your Bitset object will be instantiated and called as such:
# obj = Bitset(size)
# obj.fix(idx)
# obj.unfix(idx)
# obj.flip()
# param_4 = obj.all()
# param_5 = obj.one()
# param_6 = obj.count()
# param_7 = obj.toString()

Complexity

MeasureComplexity
TimeO(n)
SpaceO(n) auxiliary

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 2166. Design Bitset is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 2166. Design Bitset?
LeetCode 2166. Design Bitset is rated Medium on LeetCode.
What is the time complexity of LeetCode 2166. Design Bitset?
The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 2166. Design Bitset?
The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2166. Design Bitset cover?
LeetCode 2166. Design Bitset is tagged Design, Array, Hash Table and String on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity — invisible to screen sharing.

Get Stealth Interview