# 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

## 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 index `x-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

## 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```
##### Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### 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