Bitmask as a Set

When the universe of values is small - 26 letters, n <= 32, a fixed alphabet - a single integer is a set. Bit x is set exactly when element x is present.

Operation	Expression	Cost
add x	mask |= 1 << x	O(1)
remove x	mask &= ~(1 << x)	O(1)
test x	mask & (1 << x)	O(1)
toggle x	mask ^= 1 << x	O(1)
union / intersection	a | b / a & b	O(1)
size	mask.bit_count()	O(1)
is complete	mask == (1 << n) - 1	O(1)

Every one of those is a single CPU instruction, with no hashing, no allocation, and no pointer chasing. A set does the same job in the same asymptotic time but hundreds of times slower in constant factor, and it cannot be compared, unioned, or used as a dictionary key for free.

The tell that a problem wants a bitmask: "contains only characters from", "collect all of 1..k", "which elements appear in both", or any subset-of-a-small-universe question.

Sets as Bitmasks

Build one mask per group, then answer the question with a single operator. Containment is word_mask & ~allowed == 0. Membership in both arrays is a & b. Completeness is a comparison against the all-ones mask. Duplicate detection is a test-then-set.

1684. Count the Number of Consistent Strings

Easy·

1684Count the Number of Consistent Strings

Allowed Set as Bitmask

O(M) timeO(1) aux

FIG. 1684 COUNT THE NUMBER OF CONSISTENT STRINGS● INTERACTIVE

visualization loads as you reach it

class Solution:

def countConsistentStrings(self, allowed: str, words: List[str]) -> int:

count = len(words)

mask = 0

for i in allowed:

mask = mask | (1 << (ord(i) - ord("a")))

 

for word in words:

for i in word:

pos = 1 << (ord(i) - ord("a"))

if pos & mask == 0:

count -= 1

break

return count

---

2032. Two Out of Three

Easy·

2032Two Out of Three

Presence Bitmask per Array

O(N + V) timeO(V) aux

class Solution:

def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:

bm1 = bm2 = bm3 = 0

for i in nums1:

bm1 |= 1 << i

for i in nums2:

bm2 |= 1 << i

for i in nums3:

bm3 |= 1 << i

 

ans = []

for i in range(1, 101):

pos = 1 << i

if sum([bm1 & pos != 0, bm2 & pos != 0, bm3 & pos != 0]) >= 2:

ans.append(i)

return ans

---

2351. First Letter to Appear Twice

Easy·

2351First Letter to Appear Twice

Seen Set as Bitmask

O(N) timeO(1) aux

FIG. 2351 FIRST LETTER TO APPEAR TWICE● INTERACTIVE

visualization loads as you reach it

class Solution:

def repeatedCharacter(self, s: str) -> str:

bitmap = 0

for i in s:

pos = 1 << (ord(i) - ord("a"))

if pos & bitmap:

return i

bitmap = bitmap | pos

---

2869. Minimum Operations to Collect Elements

Easy·

2869Minimum Operations to Collect Elements

Target Mask from the Back

O(N) timeO(1) aux

FIG. 2869 MINIMUM OPERATIONS TO COLLECT ELEMENTS● INTERACTIVE

visualization loads as you reach it

class Solution:

def minOperations(self, nums: List[int], k: int) -> int:

mask = (1 << k) - 1

mask <<= 1 # to incorporate 0th position

bitmap = 0

for i in range(len(nums) - 1, -1, -1):

bitmap = bitmap | (1 << nums[i])

if bitmap & mask == mask:

return len(nums) - i

return 0

---

2917. Find the K-or of an Array

Easy·

2917Find the K-or of an Array

Per-Position Bit Counting

O(32 N) timeO(1) aux

FIG. 2917 FIND THE K OR OF AN ARRAY● INTERACTIVE

visualization loads as you reach it

class Solution:

def findKOr(self, nums: List[int], k: int) -> int:

bitmask = 0

for pos in range(32):

bits = 0

for n in nums:

if n & (1 << pos):

bits += 1

if bits >= k:

bitmask = bitmask | (1 << pos)

return bitmask

---

3173. Bitwise OR of Adjacent Elements

Easy·

3173Bitwise OR of Adjacent Elements

Pairwise OR

O(N) timeO(1) aux

class Solution:

def orArray(self, nums: List[int]) -> List[int]:

return [a | b for a, b in itertools.pairwise(nums)]

---

2657. Find the Prefix Common Array of Two Arrays

Medium·

2657Find the Prefix Common Array of Two Arrays

Bitmask Membership

O(N²) timeO(N) aux

FIG. 2657 FIND THE PREFIX COMMON ARRAY OF TWO ARRAYS● INTERACTIVE

visualization loads as you reach it

class Solution:

def hammingWeight(self, n: int) -> int:

bits = 0

while n != 0:

n = n & (n - 1) # Unset the lowest set bit

bits += 1

return bits

 

def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:

bitmap_a = bitmap_b = 0

ans = []

for i in range(len(A)):

bitmap_a = bitmap_a | (1 << A[i])

bitmap_b = bitmap_b | (1 << B[i])

ans.append(self.hammingWeight(bitmap_a & bitmap_b))

return ans

---

1371. Find the Longest Substring Containing Vowels in Even Counts

Medium·

1371Find the Longest Substring Containing Vowels in Even Counts

Parity Bitmask + First-Seen Index

O(N) timeO(1) aux

FIG. 1371 FIND THE LONGEST SUBSTRING CONTAINING VOWELS IN EVEN COUNTS● INTERACTIVE

visualization loads as you reach it

class Solution:

def findTheLongestSubstring(self, s: str) -> int:

maxi = 0

vowels = {j: i for i, j in enumerate("aeiou")}

bitmask = 0

hashmap = {}

hashmap[0] = -1

for idx, i in enumerate(s):

if i in vowels:

bitmask = bitmask ^ (1 << vowels[i])

if bitmask not in hashmap:

hashmap[bitmask] = idx

maxi = max(maxi, idx - hashmap[bitmask])

return maxi

---

2401. Longest Nice Subarray

Medium·

2401Longest Nice Subarray

2 Approaches · 2 patterns

Sum = XOR↗ Sliding Window

O(2N) timeO(1) aux

OR Mask

O(2N) timeO(1) aux

FIG. 2401 OLD● INTERACTIVE

visualization loads as you reach it

class Solution:

def longestNiceSubarray(self, nums: List[int]) -> int:

n = len(nums)

left = right = 0

current_or = maxi = 0

while right < n:

# Expansion

while right < n and current_or & nums[right] == 0:

current_or |= nums[right]

right += 1

# Logic

maxi = max(maxi, right - left)

# Shrinking

while left < right and right < n and current_or & nums[right] != 0:

current_or ^= nums[left]

left += 1

return maxi

---

41. First Missing Positive

Hard·

41First Missing Positive

Bitmask & Log2

O(N) timeO(N) aux

FIG. 41 FIRST MISSING POSITIVE● INTERACTIVE

visualization loads as you reach it

class Solution:

def firstMissingPositive(self, nums: List[int]) -> int:

def negate_bits(num: int) -> int:

bit_length = len(nums) + 2 # why + 2?

bitmask = (1 << bit_length) - 1 # binary with all 1's

return num ^ bitmask

 

bitmask = 0

for num in nums:

if num > 0 and num <= len(nums):

bitmask = bitmask | (1 << num)

 

negation = negate_bits(bitmask)

# zero is not a positive, hence unset 0 if set

negation = (negation | 1) ^ 1

# find the least significant set bit

ls_set = negation & -negation

 

return int(math.log2(ls_set))

---

448. Find All Numbers Disappeared in an Array

Easy·

448Find All Numbers Disappeared in an Array

Bitmask

O(2N) timeO(N) aux

FIG. 448 FIND ALL NUMBERS DISAPPEARED IN AN ARRAY● INTERACTIVE

visualization loads as you reach it

class Solution:

def findDisappearedNumbers(self, nums: List[int]) -> List[int]:

def negate_bits(num: int) -> int:

bit_length = len(nums) + 1

bitmask = (1 << bit_length) - 1

return num ^ bitmask

 

bitmask = 0

for number in nums:

bitmask = bitmask | (1 << number)

 

negation = negate_bits(bitmask)

 

# 0 is not part of the range, ignore by unsetting it.

negation = (negation | 1) ^ 1

 

# append all those positions where a bit is set to 1

ans = []

for pos in range(negation.bit_length()):

if negation & (1 << pos):

ans.append(pos)

return ans

---

442. Find All Duplicates in an Array

Medium·

442Find All Duplicates in an Array

Bitmask

O(N) timeO(N) aux

FIG. 442 FIND ALL DUPLICATES IN AN ARRAY● INTERACTIVE

visualization loads as you reach it

class Solution:

def findDuplicates(self, nums: List[int]) -> List[int]:

bitmask = 0

ans = []

for number in nums:

pos = 1 << number

# if the pos was already set, number has been already seen once

if bitmask & pos:

ans.append(number)

# set the position, which is number'th bit

bitmask = bitmask | pos

return ans

---