MediumNo. 2166
Design Bitset — LeetCode 2166 Python Solution
- Pattern
- Hash Map
- Topics
- Design, Array, Hash Table, String
- Reading time
- 8 min
- Source
- leetcode.com
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
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
- Time
- O(n)
- Space · auxiliary
- O(n)
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
| No. | Problem | Difficulty |
|---|---|---|
| 0745 | Prefix and Suffix Search | Hard |
| 2227 | Encrypt and Decrypt Strings | Hard |
| 2353 | Design a Food Rating System | Medium |
| 0049 | Group Anagrams | Medium |
| 0139 | Word Break | Medium |
| 0140 | Word Break II | Hard |
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.