Leetcode: 136. Single Number

Single Number - Solution Explanation

Code Implementation

    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            unordered_map<int, int> hash_table;

            for (int i : nums) {
                hash_table[i] = hash_table[i] + 1;
            }
            for (int i : nums) {
                if (hash_table[i] == 1) {
                    return i;
                }
            }
            return 0;
        }
    };
  

Complexity Analysis

The given solution uses an unordered map to store the count of each number in the input array. Let's analyze the complexity:

• Time Complexity: O(n) - We iterate through the input array twice, each time taking O(n) operations, where n is the size of the input array.
• Space Complexity: O(n) - The space used by the unordered map depends on the number of unique elements in the input array, which can be at most n.

Example

Let's consider an example to understand how the code works:

    Input: [2, 3, 2, 4, 4, 1, 1]
    Output: 3
  

In this example, the input array contains elements: 2, 3, 2, 4, 4, 1, 1. The single number in the array is 3, which occurs only once. The code will iterate through the array, create a hash table with counts of each element, and return the number with a count of 1.

Conclusion

In this blog post, we discussed a solution to find the single number in an array using an unordered map. We provided the code implementation, explained its complexity, and provided an example to illustrate its usage. This solution can be used to efficiently find the single number in an array of integers.