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

    Leave a Reply

    Your email address will not be published. Required fields are marked *