Find All Duplicates in an Array

To solve this problem without using any additional space and within O(n) time complexity, we can use the array itself as a marker for the presence of an integer. Since the integers in the array are in the range [1, n] and each integer appears once or twice, we can use the value of each integer as an index to mark its occurrence.

Here’s the step-by-step guide:

1. Iterate Through Array: Traverse each element in the array.
2. Find Corresponding Index: For the current integer num, find the corresponding index by taking the absolute value idx = abs(num) - 1.
3. Mark the Occurrence: If the value at the corresponding index nums[idx] is positive, negate it to mark the occurrence. If it’s already negative, then the number has occurred twice, so we add it to the result.
4. Collect Duplicates: Collect all the numbers that appear twice.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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

        for num in nums:
            idx = abs(num) - 1

            # If the value at idx is negative, then it's a duplicate
            if nums[idx] < 0:
                duplicates.append(idx + 1)
            else:
                # Negate the value at idx to mark the occurrence
                nums[idx] = -nums[idx]

        return duplicates

Explanation:

• For each number in nums, we use its absolute value minus one as the index (idx) to look up in the array.
• If the value at nums[idx] is negative, it means the current number has appeared before, so we add it to the result.
• Otherwise, we negate the value at nums[idx] to mark its occurrence.

This approach satisfies the constraint of using only constant extra space and runs in O(n) time, where n is the length of the array nums.

1
2
3
4
5
6
7
8

# @param {Integer[]} nums
# @return {Integer[]}
def find_duplicates(nums)
  hash = Hash.new(0)

  nums.each { |num| hash[num] += 1 }   
  hash.select { |k, v| v == 2 }.keys   	
end

0. Brute Force

   T: O(n^2) S: O(1)

1. We can use extra space, by using the set to check for duplicates?

2. Can you do it in O(1) space and O(n) runtime?

3. Sort the list and remove the duplicates? T:O(n log n) S:O(1) or O(n)

0.1 2 3 4 5 6 7 [4,3,2,7,8,2,3,1] i,j 4,3 4,2 4,7 4,8 4,2 4,3 4,1

size = 8

[4,3,2,7,8,2,3,1]

0, 6 1, 7

0 1 2 3 4 5 6 7 [1,2,2,3,3,4,7,8]

Two Pointers Approach T: O()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def find_duplicates(nums)
    output = []
    nums.sort!

    for i in (1..nums.size-1)
        if nums[i] == nums[i-1]
            output << nums[i]
        end
    end

    return output
end