Leetcode 442. Find All Duplicates in an Array

Problem Explanation

The problem asks to find all the duplicate elements in an array where the values of the elements are in the range of 1 to the size of the array. Instead of using extra space to solve the problem, it can be solved in a clever way with O(n) time complexity.

Consider the array: [4,3,2,7,8,2,3,1]. In each iteration, we take the absolute value of the current element, then we go to the index which is the absolute value of the current element - 1 and multiply it by -1. If the multiplied value becomes positive, it means the element is repeated so we add it to our result.

Solution Approach

Iterate over the array elements. For each element, make the element at the index of the absolute value of the current element - 1 negative. If it is already negative, then add the absolute value to the result. This works because each element appears twice and we flip the sign at the index of the current element—making it negative the first time and positive the second time.

This solution is based on using the array indices and clever in-place modification.

Python Solution

1
2python
3class Solution:
4  def findDuplicates(self, nums): 
5    ans = []
6
7    for num in nums:
8      if nums[abs(num) - 1] < 0:
9        ans.append(abs(num))
10      else:
11        nums[abs(num) - 1] *= -1
12
13    return ans

Java Solution

1
2java
3public class Solution {
4  public List<Integer> findDuplicates(int[] nums) {
5    List<Integer> ans = new ArrayList<>();
6
7    for (int i = 0; i < nums.length; ++i) {
8      int index = Math.abs(nums[i]) - 1;
9      if (nums[index] < 0)
10        ans.add(Math.abs(index + 1));
11      nums[index] = -nums[index];
12    }
13
14    return ans;
15  }
16}

JavaScript Solution

1
2javascript
3class Solution {
4  findDuplicates(nums) {
5    let ans = [];
6
7    for (let i = 0; i < nums.length; i++) {
8      let index = Math.abs(nums[i]) - 1;
9      if (nums[index] > 0)
10        nums[index] *= -1;
11      else
12        ans.push(Math.abs(index + 1));
13    }
14
15    return ans;
16  }
17}

C++ Solution

1
2cpp
3class Solution {
4public:
5  vector<int> findDuplicates(vector<int>& nums) {
6    vector<int> ans;
7
8    for (int i = 0; i < nums.size(); i++) {
9      int index = abs(nums[i]) - 1;
10      if (nums[index] > 0)
11        nums[index] *= -1;
12      else
13        ans.push_back(index + 1);
14    }
15
16    return ans;
17  }
18};

C# Solution

1
2csharp
3public class Solution {
4  public IList<int> FindDuplicates(int[] nums) {
5    List<int> ans = new List<int>();
6
7    for (int i = 0; i < nums.Length; i++) {
8      int index = Math.Abs(nums[i]) - 1;
9      if (nums[index] < 0)
10        ans.Add(Math.Abs(index + 1));
11      nums[index] = -nums[index];
12    }
13
14    return ans;
15  }
16}

In the above solutions, we iterate over the array and for each element, make the element at the index of the absolute value of the current element - 1 negative. If it is already negative (which occurs if that number was encountered before), then add the absolute value of the current element to the result list. This is how we collect duplicate numbers without using extra space.Using these solutions, we avoid creating an extra data structure such as a hash map or set, which would increase the space complexity. At the same time, we are still able to keep track of which values in the array have been seen previously and which values are duplicates, just by performing changes on the array itself.

However, it should be noted that the presented solutions work under the assumption that the input array only contains positive integers and that the contents of the array can be modified. This approach cannot be used if the input data cannot be changed. If the data cannot be mutated, a different technique would be required, which would likely involve using extra memory for storing previously encountered values. In such cases, a data structure like a hash set can be used to note the values that have been seen, and any repetition would be detected instantly.

It is a good illustration of a trade-off between memory efficiency and the constraint of data immutability. If there is flexibility in changing the data and memory efficiency is a priority, then the techniques showcased in the Python, Java, JavaScript, C++, and C# solutions can be utilized.