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


  • 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


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
Avatar for Tanishq Chaudhary

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


    1. If we use the method suggested with 2,2,3,3,0,0 we will also get 010 as an answer, yet it’s not the majority element

    Leave a Reply

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

    This site uses Akismet to reduce spam. Learn how your comment data is processed.