How to Find the Optimal Solution for Single Number LeetCode Problem?

Java solution for the single number problem using different approaches in Java and their analysis.

Tarun Telang

CORE ·

Aug. 13, 21 · Java Zone · Code Snippet

Like (2)

Save

7.64K Views

Problem Specification

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

Solution Approaches

1. Using 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.

    Java
   
 

   class Solution { 
    public int singleNumber(int[] numbers) {
    // ----------------------------------------------
    // Brute Force -- O(n**2),  Space Complexity O(1)
    // ----------------------------------------------
    int len = numbers.length;
    boolean isTwice = false; 
    for (int i=0; i < len; i++) { 
       isTwice = false;
       for (int j=0; j<len; j++) {
         if (isTwice) break;
         if (i != j)
            if(numbers[i] == numbers[j]) 
                isTwice = true
       }         
       if(!isTwice) return numbers[i];
     }
     return numbers[len - 1];
  }
}
  

2. Using 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.

    Java
   
 

   class Solution { 
    public int singleNumber(int[] numbers) { 
    // -----------------------------------------------------------
    // Sorting -- Time Complexity O(nlogn), Space Complexity O(1)
    // -----------------------------------------------------------
    Arrays.sort(numbers);
    int len = numbers.length;
    int result = numbers[len - 1]; 
    int i = 0;
    while (i < len - 2) {
      if (numbers[i] == numbers[i+1]) {
        i = i + 2;
      } else {
        return numbers[i];
      }
    }
    return numbers[len - 1];
  }
}
  

3. Using 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.

    Java
   
 

   class Solution { 
    public int singleNumber(int[] numbers) { 
        // -------------------------------------------------------------
        // Using Hash Map -- Time Complexity O(n), Space Complexity O(n)
        // -------------------------------------------------------------
        Map<Integer, Boolean> map = new HashMap();

        for (int number: numbers) {
           map.put(number, !map.getOrDefault(number, false));   
        }

        for (Map.Entry<Integer, Boolean> entry: map.entrySet()) {
           if (entry.getValue()) {
              return entry.getKey();
           }
        }
        return Integer.MIN_VALUE;
    }
}
  

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

    Java
   
 

   class Solution { 
  // -----------------------------------------------------
  // Using XOR Bit Manipulation -- 
  //         Time Complexity: O(n), Space Complexity: O(1)
  // -----------------------------------------------------
  public int singleNumber(int[] numbers) {
    int result = 0;
    for (int number: numbers) {
       result ^= number; // Logical XOR operator 
    }
    return result;
  }
}
  

Topics:

java, algorithm analysis, code snippets, problem solving, solutions

Published at DZone with permission of Tarun Telang. See the original article here.

Opinions expressed by DZone contributors are their own.

Comments