Single Number II

MEDIUM

Description

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,3,2]
Output: 3

Example 2:

Input: nums = [0,1,0,1,0,1,99]
Output: 99

Constraints:

1 <= nums.length <= 3 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Each element in nums appears exactly three times except for one element which appears once.

Approaches

Checkout 3 different approaches to solve Single Number II. Click on different approaches to view the approach and algorithm in detail.

Hash Map Approach

This approach uses a hash map to store the frequency of each number in the array. We iterate through the array, populating the map. Then, we iterate through the map to find the number with a frequency of 1.

Algorithm

Create a HashMap<Integer, Integer> to store the frequency of each number.
Iterate through the nums array. For each number num, increment its count in the map.
After building the frequency map, iterate through its entries.
Return the key for which the corresponding value (frequency) is 1.

The algorithm involves two main passes over the data. First, we iterate through the nums array to build a frequency map. For each number, we use it as a key and its frequency as the value. If the number is already in the map, we increment its value; otherwise, we add it with a value of 1. In the second pass, we iterate through the entries of the hash map. The entry whose value is 1 corresponds to the single number, and we return its key. This method is straightforward to implement and understand but does not meet the space complexity requirement of the problem.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        // This line should not be reached given the problem constraints
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(n)Space Complexity: O(n)

Pros and Cons

Pros:

Simple to understand and implement.
Generalizable to other frequency-based problems.

Cons:

Violates the problem's constraint of using only constant extra space.

Code Solutions

Checking out 4 solutions in different languages for Single Number II. Click on different languages to view the code.

class Solution {
public
  int singleNumber(int[] nums) {
    int a = 0, b = 0;
    for (int c : nums) {
      int aa = (~a & b & c) | (a & ~b & ~c);
      int bb = ~a & (b ^ c);
      a = aa;
      b = bb;
    }
    return b;
  }
}

Video Solution

Watch the video walkthrough for Single Number II

Patterns:

Bit Manipulation

Data Structures:

Array

Companies:

Accenture |Yahoo |