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.

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…