Single Number - codepath/compsci_guides GitHub Wiki

• 🔗 Leetcode Link: Single Number
• 💡 Problem Difficulty: Easy
• ⏰ Time to complete: 15 mins
• 🛠️ Topics: Array, Hashset, XOR
• 🗒️ Similar Questions: Single Number II, Single Number III, Missing Number

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

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.

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

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;    
  }
}

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

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.