As a part of LeetCode's 30 Days 30 Challenges.
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1 -
Input: [2,2,1] Output: 1
Input: [4,1,2,1,2] Output: 4
Possible Approaches for solving the given problem
- Iterate over the given array. Add the element in the dictionary. Keep a check if the key already exists in the dictionary. Keep count of the element as the value. Then return the element(key) whose value(count) is 1.
Problem with this approach
- It'll iterate the complete list.
- Once the dictionary gets created. To return the element with count 1 again value corresponding to every element will have to be checked.
- Making the time complexity - O(n^2)
- This would also lead to runtime error.
- As the elements in the list are repeated. Convert the list into a set. A set consists of only unique elements.
- Instead of iterating over a complete list which would be complexity O(n). Iterate over the set i.e unique elements only.
- Iterate over the set and check the count of that element in the list. If count is 1. Return the element.
Reasons this is better approach
- We are not iterating over the complete array of duplicate elements unnecessarily hence making the solution efficient.
- Time Complexity - O(n). The complexity of the earlier solution was O(n^2).
class Solution: def singleNumber(self, nums: List[int]) -> int: unique_nums = set(nums) for element in unique_nums: count = nums.count(element) if count == 1: return element
- Time complexity of set is O(1).
- Time complexity of list count is 0(n).
- Set consists of unique elements.