Skip to content

Single Number

Jump to bottom
Sar Champagne Bielert edited this page Apr 8, 2024 · 4 revisions

Problem Highlights

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Could there be an array with all duplicates?
    • No, it is guaranteed that every element appears twice except for one. Find that single one.
  • What is the time and space complexity?
    • You must implement a solution with a linear runtime complexity and use linear space.
      • As a bonus, you can implement a solution with a linear runtime complexity and constant space.
HAPPY CASE
Input: nums = [2,2,1]
Output: 1

Input
Input: nums = [4,1,2,1,2]
Output: 4

EDGE CASE (Multiple Spaces)
Input: nums = [1]
Output: 1

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Array/Strings, common solution patterns include:

  • Sort
    • Does sorting help us achieve our time complexity?
  • Two pointer solutions (left and right pointer variables)
    • Does Two pointers help us find duplicates?
  • Storing the elements of the array in a HashMap or a Set
    • A hashset can be used to count numbers, but we need constant space
  • Traversing the array with a sliding window
    • Will viewing pieces of the input at a time help us?
  • XOR
    • By using the XOR principle of Exclusive Or, any duplicates will result in zero. This leaves us with the single non-duplicate number.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Create a hashset and count each number. Remove numbers seen a second time. There should be a single number left in hashset.

1) Create hashset
2) Count each item
3) Remove numbers seen a second time
4) Return number with a single count

General Idea: Use XOR(Exclusive or) and the same number will return zero. All numbers except for one is a duplicate and we isolate the non-duplicate number according to the binary code.

1) Create total variable
2) XOR each number
3) Return remaining number

⚠️ Common Mistakes

  • Remember to use hashset uses linear space

4: I-mplement

Implement the code to solve the algorithm.

General Idea: Create a hashset and count each number. Remove numbers seen a second time. There should be a single number left in hashset.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # Create hashset
        hashset = set()
        
        # Count each item
        for num in nums:
            # Remove numbers seen a second time
            if num in hashset:
                hashset.remove(num)
            else:
                hashset.add(num)
        
        # Return number with a single count
        return list(hashset)[0]
class Solution {
  public int singleNumber(int[] nums) {
    // Create hashset
    HashSet<Integer> set = new HashSet<Integer>();

    // Count each item
    for(int i : nums) {
      // Remove numbers seen a second time
      if(set.contains(i)) {
	  set.remove(i);
      } else{
	  set.add(i);
      }
    }

    // Return number with a single count
    for(int i:set) {
	return i;
    }
    return -1;
  }
}

General Idea: Use XOR(Exclusive or) and the same number will return zero. All numbers except for one is a duplicate and we isolate the non-duplicate number according to the binary code.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # Create total variable
        ans = 0

        # XOR each number
        for num in nums:
            ans ^= num
        
        # Return remaining number
        return ans
class Solution {
  public int singleNumber(int[] nums) {
    // Create total variable
    int ans = 0;

    // XOR each number
    for(int i=0; i<nums.length; i++){
        ans ^= nums[i];  
    }

    // Return remaining number
    return ans;    
  }
}

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Trace through your code with an input to check for the expected output
  • Catch possible edge cases and off-by-one errors

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the number of items in array

General Idea: Create a hashset and count each number. Remove numbers seen a second time. There should be a single number left in hashset.

  • Time Complexity: O(N) we need to view each item in the array
  • Space Complexity: O(N) Hashset uses O(N) because the hashset may store up to O(N/2) numbers before removing them upon seeing the numbers a second time.

General Idea: Use XOR(Exclusive or) and the same number will return zero. All numbers except for one is a duplicate and we isolate the non-duplicate number according to the binary code.

  • Time Complexity: O(N) we need to view each item in the array
  • Space Complexity: O(1) using the XOR operator we only needed space for the total variable.
Clone this wiki locally