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.

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.