algoadvance

Leetcode 442. Find All Duplicates in an Array

Problem Statement

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, you need to find all the integers that appear twice.

You should implement an algorithm that runs in O(n) time and uses O(1) extra space (excluding the input and output).

Clarifying Questions

  1. What should be the return type of the function?
    • The function should return a list of integers that appear twice in the array.
  2. Can the input array be modified?
    • Yes, we can modify the input array to achieve the desired space complexity.
  3. Are there any duplicate numbers allowed in the output list?
    • No, each duplicate number should appear only once in the output list.

Strategy

To satisfy the O(n) time complexity and O(1) extra space complexity, we can use the array indices to track visited numbers:

  1. Iterate through the array nums.
  2. For each element nums[i], use its absolute value val = abs(nums[i]) to find the index val - 1.
  3. If nums[val-1] is positive, it indicates that the number val has not been visited yet, so negate nums[val-1] to mark it as visited.
  4. If nums[val-1] is already negative, it means the number val has been encountered before, and hence it is a duplicate.
  5. Collect all the duplicates and return them as a list.

This method ensures we only traverse the array once (O(n)) and use the array itself to keep track of visited elements, achieving O(1) extra space complexity.

Code

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> duplicates = new ArrayList<>();
        
        for (int i = 0; i < nums.length; i++) {
            int val = Math.abs(nums[i]);
            if (nums[val - 1] < 0) {
                duplicates.add(val);
            } else {
                nums[val - 1] = -nums[val - 1];
            }
        }
        
        return duplicates;
    }
}

Time Complexity

This approach efficiently finds all the duplicates with the given constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI