Single Number II
MedPrompt
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: 3Example 2:
Input: nums = [0,1,0,1,0,1,99]
Output: 99
Constraints:
1 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1- Each element in
numsappears exactly three times except for one element which appears once.
Approaches
3 approaches with complexity analysis and trade-offs.
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
numsarray. For each numbernum, 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.
Walkthrough
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
Time
O(n)
Space
O(n)
Trade-offs
Pros
Simple to understand and implement.
Generalizable to other frequency-based problems.
Cons
Violates the problem's constraint of using only constant extra space.
Solutions
Solution
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 walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.