Problem of The Day: Find All Duplicates in an Array

Problem Statement

My notes:

Intuition

Upon reviewing the problem, my initial thought was to utilize the given array to mark the presence of elements. Since the array consists of positive integers ranging from 1 to n, we can utilize the indices to mark the presence of elements and identify duplicates.

Approach

My approach involves iterating through the array and using the values as indices to access elements. For each element num, I check if the element at index num - 1 is negative. If it is negative, it means that num has appeared before, and it is a duplicate. In such cases, I append num to the result list. If it is positive, I mark the element at index num - 1 as negative to indicate its presence.

Complexity

• Time complexity: O(n), where n is the length of the input array nums. We traverse the array once.

• Space complexity: O(1)

Code

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []
        for i, num in enumerate(nums):
            idx = abs(num) - 1
            if nums[idx] < 0:
                res.append(abs(num))
            else:
                nums[idx] = -nums[idx]

        return res