442. Find All Duplicates in an Array - Explanation

Problem Link

1. Brute Force

Intuition

The most direct approach is to compare every element with every other element that comes after it. If we find two elements that are equal, we know that value appears twice (since the problem states each element appears at most twice).

Algorithm

1. For each element at index i:
   • Compare it with every element at index j where j > i.
   • If nums[i] == nums[j], add nums[i] to the result and break (no need to check further for this value).
2. Return the result list.

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = []

        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] == nums[j]:
                    res.append(nums[i])
                    break

        return res

Time & Space Complexity

• Time complexity: $O(n ^ 2)$
• Space complexity: $O(1)$ extra space.

---

2. Sorting

Intuition

After sorting, duplicate values will be adjacent to each other. We can simply scan through the sorted array and check if any element equals its neighbor. This is more efficient than the brute force approach since we only need one pass after sorting.

Algorithm

1. Sort the array.
2. Iterate through the array from index 0 to n-2:
   • If nums[i] == nums[i+1], add nums[i] to the result.
3. Return the result list.

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        nums.sort()
        res = []

        for i in range(len(nums) - 1):
            if nums[i] == nums[i + 1]:
                res.append(nums[i])

        return res

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

---

3. Hash Set

Intuition

We can use a hash set to track which numbers we have already seen. As we iterate through the array, if a number is already in the set, it must be a duplicate. Otherwise, we add it to the set. This gives us O(1) lookup time for each element.

Algorithm

1. Initialize an empty hash set seen and an empty result list.
2. For each number in the array:
   • If it is already in seen, add it to the result.
   • Otherwise, add it to seen.
3. Return the result list.

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        seen = set()
        res = []
        for num in nums:
            if num in seen:
                res.append(num)
            else:
                seen.add(num)
        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

4. Hash Map

Intuition

Instead of just tracking presence, we can count how many times each number appears using a hash map. After counting, we iterate through the map and collect all numbers that appear exactly 2.

Algorithm

1. Build a frequency map counting occurrences of each number.
2. Iterate through the map:
   • If a number has a count of 2, add it to the result.
3. Return the result list.

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        count = Counter(nums)
        res = []

        for num in count:
            if count[num] == 2:
                res.append(num)

        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

5. Negative Marking

Intuition

Since all values are in the range [1, n] where n is the array length, we can use the array itself as a hash map. The key insight is that each value v can be mapped to index v-1. When we encounter a value, we mark the element at its corresponding index as negative. If we encounter a value whose corresponding index is already negative, that value must be a duplicate.

Algorithm

1. For each number in the array:
   • Compute the index as abs(num) - 1.
   • If nums[idx] is already negative, add abs(num) to the result (this value was seen before).
   • Negate nums[idx] to mark that we have seen the value idx + 1.
2. Return the result list.

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []

        for num in nums:
            idx = abs(num) - 1
            if nums[idx] < 0:
                res.append(abs(num))
            nums[idx] = -nums[idx]

        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ extra space.