Find All Duplicates in an Array | LeetCode | Solution Explained
442. Find All Duplicates in an Array is a medium problem on LeetCode, and is one of those for which you have to have seen the approach beforehand to understand the solution. I explain the solution in detail. Problem link.
Contents hide
Key Points
- We have to get a solution for O(N) time O(1) space
- We have multiple solutions that take either more time or more space
- But there’s one method which can get us the answer
Logic
- observe the range of elements
[1, n]
this means we can do operations inside the array - we need a way to mark and say if an element has been visited or not
- we need a consisitent way to always land up at the same index, for the same element
- what we can do is:
- for the element
x
- visit the index
x-1
(since elements are 1 indexed) - and change the value
y
at the indexx-1
to-y
- while iterating, if some element
z
‘s pointed element (nums[z-1]
) is -ve - then the value
z
has been repeated twice - once to set
y
to-y
and once right now
- for the element
Code
class Solution: def findDuplicates(self, nums: List[int]) -> List[int]: ans = [] n = len(nums) for i in range(n): x = nums[i] if nums[abs(x)-1] < 0: ans.append(abs(x)) else: nums[abs(x)-1] *= -1 return ans
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Majority Element | InterviewBit | Solution Explained
June 13, 2022
Seats | InterviewBit | Solution Explained
June 13, 2022