Single Number II - Video Solutions

Problem Overview: You are given an integer array where every element appears exactly three times except for one element that appears once. The task is to find that single element. The challenge is doing it efficiently without extra memory while scanning the array only once.

Approach 1: Use a Map to Count Frequencies (O(n) time, O(n) space)

The straightforward solution counts how many times each number appears. Iterate through the array and store frequencies in a hash map using map[num]++. After building the frequency table, iterate through the map and return the number whose count equals 1. Hash lookups and insertions run in constant time on average, so the entire pass over the array costs O(n) time.

This method is easy to implement and works for any frequency-based variant of the problem. The downside is memory usage: the map may store up to n distinct elements, giving O(n) space complexity. In interviews, this approach demonstrates that you recognize the frequency pattern but it doesn't fully exploit the bit constraints of the problem. Problems involving counting or frequency tables commonly appear in array and hash-based questions.

Approach 2: Bit Manipulation (O(n) time, O(1) space)

The optimal approach analyzes the binary representation of every number. Since all numbers except one appear exactly three times, the sum of bits at each position must be a multiple of three for those repeated numbers. The unique number contributes the remaining bits. For each bit position from 0 to 31, iterate through the array and count how many numbers have that bit set.

Compute count % 3 for each bit position. If the remainder is 1, the unique number has that bit set. Reconstruct the answer by setting those bits in the result integer. This works because triples cancel out under modulo 3 arithmetic. The algorithm scans the array for each bit position, giving O(32 * n) time which simplifies to O(n). Only a few integer variables are used, so space complexity is O(1).

This technique is a classic example of counting bits with modular arithmetic and appears frequently in bit manipulation interview questions. It avoids auxiliary data structures and works even when the input size is large.

Recommended for interviews: The bit manipulation approach is the expected optimal solution. Interviewers want to see whether you recognize the pattern that repeated numbers cancel out when counted modulo three. Starting with the hash map solution shows clear thinking, but transitioning to the constant-space bit technique demonstrates stronger algorithmic skill and familiarity with low-level operations.