Scale Engineer

Find All Duplicates in an Array

Med
#0429Time: O(n^2) - Due to the nested loops, for each element, we scan the rest of the array.Space: O(1) - We only use a few variables and the result list. The auxiliary space is constant, as the space for the output is excluded from consideration.1 company
Data structures
ArrayHash Table
Companies
Pocket Gems

Prompt

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears at most twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant auxiliary space, excluding the space needed to store the output

 

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

Example 2:

Input: nums = [1,1,2]
Output: [1]

Example 3:

Input: nums = [1]
Output: []

 

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n
  • Each element in nums appears once or twice.

Approaches

4 approaches with complexity analysis and trade-offs.

The most straightforward approach is to compare every element with every other element in the array. This method is easy to conceive but highly inefficient.

Algorithm

  1. Initialize an empty list duplicates to store the results.
  2. Iterate through the array with an index i from 0 to n-2.
  3. For each element nums[i], start an inner loop with index j from i+1 to n-1.
  4. Inside the inner loop, compare nums[i] and nums[j].
  5. If nums[i] == nums[j], it's a duplicate. Check if this number is already in the duplicates list. If not, add it.
  6. Return the duplicates list.

Walkthrough

We use two nested loops to find pairs of equal numbers. The outer loop iterates from the first element to the last, and the inner loop iterates from the next element of the outer loop's current position. If two elements nums[i] and nums[j] are found to be equal, we've identified a duplicate. To prevent adding the same duplicate number to our result list multiple times (e.g., for an input like [2, 2, 2]), we can check if the number is already in our result list before adding it.

import java.util.ArrayList;import java.util.List; class Solution {    public List<Integer> findDuplicates(int[] nums) {        List<Integer> duplicates = new ArrayList<>();        for (int i = 0; i < nums.length; i++) {            for (int j = i + 1; j < nums.length; j++) {                if (nums[i] == nums[j]) {                    // Check if this duplicate is already found                    if (!duplicates.contains(nums[i])) {                        duplicates.add(nums[i]);                    }                    break; // Move to the next i                }            }        }        return duplicates;    }}

Complexity

Time

O(n^2) - Due to the nested loops, for each element, we scan the rest of the array.

Space

O(1) - We only use a few variables and the result list. The auxiliary space is constant, as the space for the output is excluded from consideration.

Trade-offs

Pros

  • Simple to understand and implement.

  • Uses constant extra space (excluding the output list).

Cons

  • Extremely inefficient with a time complexity of O(n^2).

  • Will likely result in a 'Time Limit Exceeded' error for large inputs.

Solutions

class Solution {public  List<Integer> findDuplicates(int[] nums) {    int n = nums.length;    for (int i = 0; i < n; ++i) {      while (nums[i] != nums[nums[i] - 1]) {        swap(nums, i, nums[i] - 1);      }    }    List<Integer> ans = new ArrayList<>();    for (int i = 0; i < n; ++i) {      if (nums[i] != i + 1) {        ans.add(nums[i]);      }    }    return ans;  }  void swap(int[] nums, int i, int j) {    int t = nums[i];    nums[i] = nums[j];    nums[j] = t;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem