Last updated on January 21st, 2025 at 02:06 am
Here, we see a Find All Duplicates in an Array LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array
Companies
Pocketgems
Level of Question
Medium

Find All Duplicates in an Array LeetCode Solution
Table of Contents
1. 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, 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 extra space.
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: []
2. Coding Pattern Used in Solution
The coding pattern used in this code is “Index Marking” or “Index Manipulation”. This pattern leverages the input array itself to store information by modifying its elements (e.g., marking indices as visited by negating the values). This avoids the need for extra space, making the solution efficient in terms of space complexity.
3. Code Implementation in Different Languages
3.1 Find All Duplicates in an Array C++
class Solution { public: vector<int> findDuplicates(vector<int>& nums) { vector<int>ans; int n=size(nums); for(int i=0;i<n;i++){ int x=abs(nums[i]); if(nums[x-1]<0){ ans.push_back(x); } nums[x-1]*=-1; } return ans; } };
3.2 Find All Duplicates in an Array Java
class Solution { public List<Integer> findDuplicates(int[] nums) { List<Integer> ans = new ArrayList<>(); int n = nums.length; for (int i = 0; i < n; i++) { int x = Math.abs(nums[i]); if (nums[x - 1] < 0) { ans.add(x); } nums[x - 1] *= -1; } return ans; } }
3.3 Find All Duplicates in an Array JavaScript
var findDuplicates = function(nums) { const ans = []; const n = nums.length; for (let i = 0; i < n; i++) { const x = Math.abs(nums[i]); if (nums[x - 1] < 0) { ans.push(x); } nums[x - 1] *= -1; } return ans; };
3.4 Find All Duplicates in an Array Python
class Solution(object): def findDuplicates(self, nums): ans =[] n=len(nums) for x in nums: x = abs(x) if nums[x-1]<0: ans.append(x) nums[x-1] *= -1 return ans
4. Time and Space Complexity
Time Complexity | Space Complexity | |
C++ | O(n) | O(k) |
Java | O(n) | O(k) |
JavaScript | O(n) | O(k) |
Python | O(n) | O(k) |
- Time Complexity (
O(n)
): The algorithm processes each element of the array exactly once, making it linear in time. - Space Complexity (
O(k)
): The result listans
grows with the number of duplicates, but no additional space is used for processing since the input array is modified in-place. - In-place Modification: The algorithm modifies the input array, so if the original array is needed later, it must be copied beforehand.