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

1

Allowed Set as Bitmask

O(M)

O(1)

Explanation

Encode the allowed characters as a 26-bit mask - bit ord(c) - ord('a') is set for each allowed letter. A word is consistent only if every one of its characters is in that mask.

Start assuming all words are consistent (count = len(words)). For each word, the moment a character's bit is not in the mask (pos & mask == 0), the word is inconsistent: decrement and break.

Analysis

Time

O(M)

• M is the total number of characters across all words.

Space

O(1)

• A single integer mask of fixed width.

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

1

Presence Bitmask per Array

O(N + V)

O(V)

Explanation

Build one bitmask per array, setting bit v for every value v present. Since values are in [1, 100], a single integer per array is enough.

Then for each candidate value i, count in how many of the three masks bit i is set. If at least two of them contain it, i qualifies for the answer.

Analysis

Time

O(N + V)

• N is the total elements across the three arrays, scanned once each to build the masks; V is the value range scanned afterward (here 100) to test each candidate.

Space

O(V)

• bm1, bm2, and bm3 each need V bits to represent values up to 100, and ans can hold up to V qualifying values.

FIG. 2032 TWO OUT OF THREE● INTERACTIVE

visualization loads as you reach it

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

1

Seen Set as Bitmask

O(n)

O(1)

Explanation

Track which letters have been seen using a 26-bit mask, where bit ord(c) - ord('a') marks a letter. Walk the string left to right.

For each character, if its bit is already set in bitmap (pos & bitmap), this is the first repeat - return it immediately. Otherwise set the bit and continue.

Analysis

Time

O(n)

• n = len(s). The for i in s loop visits each character once, stopping as soon as pos & bitmap finds a repeat.

Space

O(1)

• Only the single fixed-width bitmap integer is stored; nothing scales with n.

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

1

Target Mask from the Back

O(n)

O(1)

Explanation

Each operation removes the last element of nums, so collecting 1..k means consuming a suffix. We want the shortest suffix that contains all of 1..k.

Build a target mask with bits 1..k set: (1 << k) - 1 gives bits 0..k-1, then a left shift by one aligns them to positions 1..k. Scan from the back, ORing each value's bit into bitmap. The first time bitmap & mask == mask, every required element has appeared - return how many elements were consumed.

Analysis

Time

O(n)

• The for i in range(len(nums) - 1, -1, -1) loop walks backward through nums at most once, doing O(1) bitmask work per element, so total is O(n), where n = len(nums).

Space

O(1)

• Two fixed-width integer masks.

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

1

Per-Position Bit Counting

O(32 N)

O(1)

Explanation

The K-or sets bit pos in the result if at least k of the array elements have that bit set. So handle each bit position independently.

For each position pos (0 to 31), count how many numbers have n & (1 << pos) set. If that tally reaches k, OR bit pos into the answer mask.

Analysis

Time

O(32 N)

• For each of 32 bit positions, scan all N numbers.

Space

O(1)

• A single accumulating mask.

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

1

Pairwise OR

O(n)

O(n)

Explanation

The result has one fewer element than the input: index i is nums[i] | nums[i + 1]. itertools.pairwise walks consecutive pairs directly, so the whole answer is a single comprehension over those pairs.

Analysis

Time

O(n)

• One pass over the n - 1 adjacent pairs.

Space

O(n)

• The output list holds n - 1 values.

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

1

Bitmask Membership

O(N²)

O(N)

Explanation

Track which values have appeared so far in each array as a bitmask: set bit A[i] in bitmap_a and bit B[i] in bitmap_b. The values present in both prefixes are exactly the bits set in bitmap_a & bitmap_b, so counting those set bits gives each prefix's common count in one shot.

Analysis

Time

O(N²)

• The outer loop runs N times (N = len(A)), each iteration doing O(1) bit-shift ORs to update bitmap_a/bitmap_b.
• hammingWeight unsets one bit per iteration (n & (n - 1)), so its cost equals the number of set bits in bitmap_a & bitmap_b. After i insertions that mask can have up to i set bits, so the i-th call costs O(i) in the worst case - summed over all N iterations that's O(1 + 2 + ... + N) = O(N²).

Space

O(N)

• ans holds N entries, and bitmap_a/bitmap_b each grow to O(N) bits wide as values up to N get OR'd in.

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

1

Parity Bitmask + First-Seen Index

O(N)

O(1)

Explanation

Only the parity of each vowel's count matters, so track it as a 5-bit mask - bit vowels[c] flips every time character c is seen. A substring has all-even vowel counts exactly when its prefix masks at both ends are equal, since the XOR of equal masks is zero.

hashmap remembers the first index where each mask value occurred (hashmap[0] = -1 seeds the empty prefix). Whenever the current mask repeats, everything between the two occurrences has balanced vowels, and idx - hashmap[bitmask] is a candidate length.

Analysis

Time

O(N)

• One pass over s, constant work per character.

Space

O(1)

• bitmask only has 32 possible values, so hashmap never holds more than 32 entries.

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

---

41. First Missing Positive

Hard·

41First Missing Positive

1

Bitmask & Log2

O(N)

O(1)

Explanation

The smallest missing positive integer must lie in the range [1, len(nums) + 1], so anything outside that range can be ignored. Instead of marking presence in the array itself, this solution packs presence into a single integer bitmask - bit num is set when num appears.

Steps:

1. Bitmask creation - iterate through nums, setting bit num for each positive integer that is at most len(nums).
2. Negation - flip all bits of the bitmask. The chosen bit_length is len(nums) + 2.
3. Unset the 0th bit - 0 is not a positive number, so clear bit 0 with (negation | 1) ^ 1.
4. Isolate the least significant set bit - negation & -negation keeps only the rightmost 1-bit, whose position is the smallest missing positive. log2(ls_set) recovers that position.

Why + 2 in bit_length? If the input is [1], the bitmask is 0b10. To negate correctly we need 0b101 and not 0b01, which only happens when bit_length = 3, that is +2 of len([1]).

Worked examples:

• [1, 2, 0] - bitmask 0b110, negation 0b11001, after unsetting bit 0 0b11000, isolated 0b1000, log2 = 3.
• [3, 4, -1, 1] - bitmask 0b11010, negation 0b100101, after unsetting 0b100100, isolated 0b100, log2 = 2.
• [7, 8, 9, 11, 12] - bitmask 0b0, negation 0b1111111, after unsetting 0b1111110, isolated 0b10, log2 = 1.
• [1] - bitmask 0b10, negation 0b101, after unsetting 0b100, isolated 0b100, log2 = 2.

Analysis

Time

O(N)

• A single pass builds the bitmask, and the bit isolation is constant time.

Space

O(1)

• Only a fixed set of integer variables is used (the bitmask width is bounded by the array length).

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

1

Bitmask

O(2n)

O(1)

Explanation

Closely related to 41. First Missing Positive. Every value in nums lies in [1, n], so presence is recorded as a bit in a single integer; the bits that remain unset after the scan are exactly the missing numbers.

Steps:

1. Bitmask creation - iterate through nums, setting bit number for each value seen.
2. Negation - flip all bits using bit_length = len(nums) + 1, so set bits now mark absent values.
3. Unset the 0th bit - 0 is outside the range, so clear it with (negation | 1) ^ 1.
4. Collect missing numbers - walk the negated bitmask and append every position whose bit is still set.

Worked examples:

• [4, 3, 2, 7, 8, 2, 3, 1] - bitmask 0b110011110, negation 0b1100001, after unsetting bit 0 0b1100000, answer [5, 6].
• [1, 1] - bitmask 0b10, negation 0b101, after unsetting 0b100, answer [2].
• [1, 1, 1] - bitmask 0b10, negation 0b1101, after unsetting 0b1100, answer [2, 3].

Analysis

Time

O(2n)

• Two separate linear passes: the for number in nums loop builds bitmask, and the for pos in range(negation.bit_length()) loop collects the missing numbers - both bounded by n = len(nums), giving 2n.

Space

O(1)

• Only a fixed-size bitmask and a few auxiliary variables are used (the output list is not counted).

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

1

Bitmask

O(n)

O(n)

Explanation

Every value lies in [1, n], so a single integer bitmask can record which values have already been seen. For each number, bit number acts as a "seen" flag - if that bit is already set, the value is a duplicate; otherwise we set it.

This avoids any extra hash set: the bitmask holds the entire seen-state in one integer.

Walkthrough on [4, 3, 2, 7, 8, 2, 3, 1]:

• 4, 3, 2, 7, 8 are all first-time - their bits get set.
• The second 2 finds bit 2 already set, so 2 is recorded as a duplicate.
• The second 3 finds bit 3 already set, so 3 is recorded.
• 1 is first-time. Final answer: [2, 3].

Analysis

Time

O(n)

• n is the length of nums - the for number in nums loop makes a single pass, with constant-time bit operations per element.

Space

O(n)

• bitmask needs one bit per possible value in [1, n] - since Python integers grow with their bit width, holding a value that wide costs O(n) bits, not O(1) (the output list is not counted).

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

---