Problem

Given an array of integers, find out duplicates in it.

Examples

Example 1:

1
2
3

Input: nums = [4, 6, 2, 1, 2, 5]
Output: [2]
Explanation: The number 2 occurs twice.

Example 2:

1
2
3

Input: nums = [1, 6, 5, 2, 3, 3, 2]
Output: [2, 3]
Explanation: The number 2 and 3 occur twice.

Similar Problems

Special Cases

There are some special cases as well. For example:

Solution

Method 1 - Naive

Use two nested loops to compare each element in the array with all other elements and identify if any of them have the same value.

Time Complexity : O(n^2) Space Complexity: O(1)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> duplicates = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] == nums[j] && !duplicates.contains(nums[i])) {
                    duplicates.add(nums[i]);
                }
            }
        }
        return duplicates;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] nums1 = {1, 2, 3, 1, 2, 4};
        System.out.println("Duplicates in the array are: " + solution.findDuplicates(nums1));  // Output: [1, 2]

        int[] nums2 = {4, 5, 6, 5, 7, 8, 7};
        System.out.println("Duplicates in the array are: " + solution.findDuplicates(nums2));  // Output: [5, 7]

        int[] nums3 = {9, 9, 10, 11, 12, 10};
        System.out.println("Duplicates in the array are: " + solution.findDuplicates(nums3));  // Output: [9, 10]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def findDuplicates(self, nums):
        duplicates = []
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] == nums[j] and nums[i] not in duplicates:
                    duplicates.append(nums[i])
        return duplicates

# Example usage
solution = Solution()
nums1 = [1, 2, 3, 1, 2, 4]
print(f"Duplicates in the array are: {solution.findDuplicates(nums1)}")  # Output: [1, 2]

nums2 = [4, 5, 6, 5, 7, 8, 7]
print(f"Duplicates in the array are: {solution.findDuplicates(nums2)}")  # Output: [5, 7]

nums3 = [9, 9, 10, 11, 12, 10]
print(f"Duplicates in the array are: {solution.findDuplicates(nums3)}")  # Output: [9, 10]

Method 2 - Sorting

Sort the array, which will group any duplicates together. Then, traverse the array and check adjacent elements to identify duplicates.

Time Complexity : O(nlogn) Space Complexity: O(1) by using merge sort.

Code

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

public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        Arrays.sort(nums);  // Sorting the array
        List<Integer> duplicates = new ArrayList<>();
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1] && !duplicates.contains(nums[i])) {
                duplicates.add(nums[i]);
            }
        }
        return duplicates;
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def findDuplicates(self, nums):
        nums.sort()  # Sorting the array
        duplicates = []
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1] and nums[i] not in duplicates:
                duplicates.append(nums[i])
        return duplicates

Method 3 - Using Hashmap

Store the count of each element of array in a hash table and later check in Hash table if any element has count more than 1. ( Similar approach is used in problem – First Unique Character in a String) Time Complexity : O(n) and Space Complexity: O(n).

Code

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

public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> duplicates = new ArrayList<>();
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num)) {
                duplicates.add(num);
            } else {
                seen.add(num);
            }
        }
        return duplicates;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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