Skip to main content

Single Number II

Problem 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.

Examples​

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∗1041 \leq nums.length \leq 3 * 10^4
  • −3×104≤nums[i]≤3×104-3 \times 10^4 \leq nums[i] \leq 3 \times 10^4
  • Each element in the array appears three times except for one element which appears only once.

Solution for Single Number ii Problem​

Intuition​

The problem states that every element in the array appears exactly three times, except for one element that appears exactly once. To identify this unique element efficiently, we can leverage a hash map to count the occurrences of each element. The key observation here is that the unique element will have a count of one in the hash map, while all other elements will have a count of three.

Approach​

First declare an empty hashmap then we store the each element and it's frequencies in hashmap after that we iterate to the keys of map if the value of particular key is 1 then we return the key.

Code in Different Languages​

Written by @ImmidiSivani
class Solution:
def singleNumber(self, nums: List[int]) -> int:
mp = {}
for num in nums:
if num in mp:
mp[num] += 1
else:
mp[num] = 1

for num, c in mp.items():
if c == 1:
return num

Complexity Analysis​

  • Time complexity: O(n)O(n), as we're iterating over the array only once.
  • Space complexity: O(n)O(n), because here we are using Hashmap to count occurences of elements.

References​