As a part of LeetCode's 30 Days 30 Challenges.
Problem Statement
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
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
Approach 1
- 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.
Approach 2
- 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
Learnings
- Time complexity of set is O(1).
- Time complexity of list count is 0(n).
- Set consists of unique elements.
Reference Links
https://leetcode.com/explore/other/card/30-day-leetcoding-challenge/528/week-1/3283/
Top comments (1)
You could also xor all the digits. The second occurrence cancels out the first.
No extra memory beyond a single int used.