Leetcode – Single Number Solution in Python

Spread the love

In this extensive article, we will discuss the Single Number problem, analyze different approaches to solve it, and implement these solutions in Python.

Problem Statement

The Single Number problem is listed as problem number 136 on LeetCode. Here’s the problem statement:

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:
Input: [2,2,1]
Output: 1

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

Understanding the Problem

Before we dive into solving the problem, let’s take a moment to understand it. The problem gives us a list of integers where every integer appears exactly twice, except for one integer, which appears only once. We need to find this single integer. The problem constraints also mention that we should aim for linear time complexity and constant space complexity.

Brute Force Approach

The most naive approach would be to check each element and count how many times it appears in the array. If an element appears only once, we return it.

def singleNumber(nums):
    for num in nums:
        if nums.count(num) == 1:
            return num

However, this approach has a time complexity of O(n^2) because for each element, we are scanning the entire array to count its occurrences. This is not efficient for large arrays.

Using a Hash Map

We can use a hash map to keep track of the number of times each element appears in the array. After we have processed all the elements, we can scan the hash map to find the element that appears only once.

def singleNumber(nums):
    # Create a hash map to store the count of each number
    hash_map = {}
    
    # Count the occurrences of each number
    for num in nums:
        if num in hash_map:
            hash_map[num] += 1
        else:
            hash_map[num] = 1
    
    # Find the number that appears once
    for num, count in hash_map.items():
        if count == 1:
            return num

This approach has a time complexity of O(n) and a space complexity of O(n) as well, since in the worst case, the hash map will store n/2 elements.

Using Bit Manipulation

One of the most elegant and efficient solutions to this problem uses bit manipulation. If we take the XOR of two same numbers, it will be 0 (e.g. a XOR a = 0). Also, XOR operation is associative and commutative, which means that a XOR b XOR a is equal to a XOR a XOR b and is equal to 0 XOR b, which is equal to b. We can XOR all the numbers in the array, and the result will be the number that appears only once.

def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

This approach also has a time complexity of O(n), but it has a constant space complexity, O(1), as it does not use any additional memory based on the input size. This satisfies the problem constraints completely.

Analysis and Conclusion

We explored three different approaches to solve the Single Number problem on LeetCode using Python. The brute force approach is not efficient for large arrays due to its O(n^2) time complexity. The hash map approach improves the time complexity to O(n), but uses additional space. The bit manipulation approach, using XOR, is the most efficient solution with O(n) time complexity and O(1) space complexity.

It’s important to recognize that the efficiency of the solution not only depends on optimizing the algorithm but also understanding the underlying mathematical properties and logical operations that can be exploited, as showcased in the bit manipulation approach.

In coding interviews, it’s also good practice to first solve the problem, even with a less efficient approach, and then iterate to optimize it. Being able to derive and discuss the optimized solution, particularly with the bit manipulation in this case, demonstrates a strong understanding of computer science fundamentals and problem-solving skills.

Leave a Reply