LeetCode 3595 - Once Twice

The problem provides an integer array nums where every element appears exactly three times, except for one element that appears once and one element that appears twice.

leetcodemediumarraybit-manipulation

LeetCode Problem 3595

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation

Solution

Problem Understanding

The problem provides an integer array nums where every element appears exactly three times, except for one element that appears once and one element that appears twice. We are asked to identify these two unique elements and return them as a list, with the element appearing once first and the element appearing twice second.

The input array is guaranteed to have a length that is a multiple of three, which aligns with the fact that all numbers except two follow the "appear three times" rule. Each number in the array can range from -2^31 to 2^31 - 1. The constraints require that the solution runs in O(n) time and uses O(1) extra space.

Key edge cases include the smallest possible array (length 3) and arrays where the unique elements are negative, zero, or located at the beginning or end. The problem guarantees that there is exactly one element appearing once and exactly one element appearing twice, so we do not need to handle inputs violating this property.

The challenge lies in achieving O(1) extra space while distinguishing the elements appearing once, twice, and three times. A naive frequency counting approach would violate the space constraint.

Approaches

The brute-force approach involves using a hash map (or dictionary) to count the occurrences of each number. This is straightforward: iterate over the array, count each element, and then extract the element appearing once and the element appearing twice. While this works correctly, it requires O(n) extra space, which violates the problem's constraint.

The key insight for an optimal solution is to use bit manipulation. Since every number except two follows the "appear three times" rule, we can use bitwise operations to track counts modulo 3. By carefully constructing bit masks, we can isolate the element that appears once and the element that appears twice. This technique generalizes the "single number in a triplicated array" problem and adapts it to handle two exceptions with different frequencies.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Uses hash map to count occurrences and retrieve results.
Optimal O(n) O(1) Uses bit manipulation to track counts modulo 3 and extract the once/twice elements.

Algorithm Walkthrough

  1. Initialize two variables, once_mask and twice_mask, to 0. These will store the bits that have appeared exactly once or twice as we iterate through the array.
  2. Iterate over each number num in nums.
  3. Update twice_mask first to include the bits that have appeared a second time. The formula is twice_mask |= once_mask & num.
  4. Update once_mask to include the bits that have appeared a first time, using once_mask ^= num.
  5. Remove bits that have appeared three times from both masks: calculate common_mask = ~(once_mask & twice_mask) and update once_mask &= common_mask and twice_mask &= common_mask.
  6. After processing all numbers, once_mask contains the number appearing once and twice_mask contains the number appearing twice.
  7. Return [once_mask, twice_mask].

Why it works: This works because the bit masks correctly track the counts of each bit modulo 3. Bits appearing three times are cleared, leaving only the bits corresponding to the once and twice elements. The invariant is that once_mask always stores bits that have appeared 1 mod 3 times, and twice_mask stores bits that have appeared 2 mod 3 times.

Python Solution

from typing import List

class Solution:
    def onceTwice(self, nums: List[int]) -> List[int]:
        once_mask = 0
        twice_mask = 0

        for num in nums:
            # Add to twice_mask the bits that are in once_mask and current num
            twice_mask |= once_mask & num
            # XOR current number to update once_mask
            once_mask ^= num
            # Mask to clear bits appearing three times
            common_mask = ~(once_mask & twice_mask)
            once_mask &= common_mask
            twice_mask &= common_mask

        return [once_mask, twice_mask]

Implementation Explanation: The once_mask tracks bits that have appeared exactly once so far, while twice_mask tracks bits that have appeared exactly twice. For every number, we first add its overlapping bits with once_mask to twice_mask, then toggle its bits in once_mask. Any bits appearing three times are cleared from both masks to ensure the modulo 3 property. After iterating through the array, the masks directly contain the elements we are looking for.

Go Solution

func onceTwice(nums []int) []int {
    var onceMask, twiceMask int

    for _, num := range nums {
        twiceMask |= onceMask & num
        onceMask ^= num
        commonMask := ^(onceMask & twiceMask)
        onceMask &= commonMask
        twiceMask &= commonMask
    }

    return []int{onceMask, twiceMask}
}

Go Implementation Notes: The Go version mirrors the Python logic. Go handles integers as 32-bit or 64-bit depending on the platform, but the bitwise operations work identically. The slice [onceMask, twiceMask] is returned at the end, which is analogous to returning a list in Python.

Worked Examples

Example 1: nums = [2,2,3,2,5,5,5,7,7]

Iteration num once_mask twice_mask common_mask
2 2 2 0 -1
2 2 0 2 -1
3 3 3 2 -1
2 2 1 2 -1
5 5 4 2 -1
5 5 1 4 -1
5 5 0 4 -1
7 7 7 4 -1
7 7 0 7 -1

Output: [3,7]

Example 2: nums = [4,4,6,4,9,9,9,6,8]

Output: [8,6]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each number is processed once in a single pass through the array.
Space O(1) Only a fixed number of integer variables are used, independent of input size.

The solution achieves the required O(n) time and O(1) space constraints using bitwise manipulation instead of a hash map.

Test Cases

# Provided examples
assert Solution().onceTwice([2,2,3,2,5,5,5,7,7]) == [3,7]  # once=3, twice=7
assert Solution().onceTwice([4,4,6,4,9,9,9,6,8]) == [8,6]  # once=8, twice=6

# Edge cases
assert Solution().onceTwice([1,1,2,2,2,3,3,3,4]) == [4,1]  # smallest array length 9
assert Solution().onceTwice([0,0,0,-1,-1,1,1,1,2]) == [2,-1]  # negative and zero values
assert Solution().onceTwice([10**9,10**9,10**9,5,5,5,7,7,8]) == [8,7]  # large numbers
Test Why
[2,2,3,2,5,5,5,7,7] Checks basic functionality with once and twice elements among triples
[4,4,6,4,9,9,9,6,8] Another basic example with different once and twice values
[1,1,2,2,2,3,3,3,4] Tests smallest array satisfying constraints
[0,0,0,-1,-1,1,1,1,2] Tests negative numbers and zero handling
[10^9,10^9,10^9,5,5,5,7,7,8] Tests handling of large integer values

Edge Cases

Edge Case 1: Negative numbers

Negative numbers may introduce complications with bitwise operations due to two's complement representation. The algorithm handles this correctly because XOR and AND work identically with signed integers in two's complement, and the bit clearing logic does not depend on sign.

Edge Case 2: Smallest array length

The minimum valid length is 3 (for one element appearing once, one element appearing twice, and zero triples), or more generally any multiple of three. The algorithm works correctly for arrays of length 3