How to find the optimal solution for — Single Number — LeetCode Problem?

Photo by Scott Graham on Unsplash

Problem Specification

https://leetcode.com/problems/single-number

Solution

Approaches

Brute Force:

The most obvious solution is to start with a Brute Force approach. In this approach, you can compare each number with the rest of the numbers in the array. In case you find a duplicate proceed to the next number and in case you don’t find a duplicate you return the current number as a Single Number. Below is the Java code for the same.

Solution 1— java code to solve single number problem using brute force approach.

Sorting

To improve on the brute force approach you can apply sorting first to avoid going back and forth in the array while comparing each number with the rest of the numbers in the array. After sorting you would just need a single pass on the array of numbers to find a single number. Sorting can be done in O(NlogN) time, this approach is faster than the above one. Also, we don’t need additional space so the space complexity would be O(1). Please find the Java code of the solution for this approach below.

Solution 2— java code to solve single number problem using sorting.

Hash Map

In order to reduce the time complexity further, you can instead use a HashMap. This way you don’t need to sort the array. This approach improves a space/time tradeoff to improved performance. This has a time complexity of O(N) whereas its space complexity is also O(N). Below is the Java code for this approach.

Solution 3 — java code to solve single number problem using the hash map.

Optimal Solution

The most optimal solution does not use any additional space and has linear time complexity. The idea is to start with 0 and apply use logical eXclusive OR (XOR) operator on the entire array. The final result would be the desired single number to be returned. Please find the Java code for this approach below.

Solution 4 (Optimal) — java code to solve single number problem using bit-manipulation.