How to find all duplicates in an array without using extra space?
Given an array of integers, the integers are in the range of 1 ≤ a[i] ≤ n (n = size of array). In this Array, some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
We have to solve this problem without using extra space and in O(n) time complexity.
For Example:
Input: [4, 3, 2, 7, 8, 2, 3, 1]
Output: [2, 3]
This problem is very simple, if extra space is allowed. If extra space is allowed, we can use Set, HashMap or other data structure to find all the elements that appear twice in this array.
But in this problem, we have to find duplicates in O(n) time and O(1) extra space.
I have also added video tutorial link at the end of this post.
Programming Questions on Array
Interview questions for practice
Find All Duplicates in an Array – Java Code
In this example, we are going to solve this problem without using extra space.
The idea here is to traverse an array and take each array element at a time. Then visit the index which is array element minus one and flip the number at that index from positive to negative. If the number present at that index is already negative then the current element is already appeared in this array. So, This number is a duplicate number. Similarly, we repeat this process until the array is traversed completely.
The time complexity of this approach is O(n) and it’s space complexity is O(1).
|
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 |
//Find All Duplicates in an Array public List<Integer> findDuplicates(int[] nums) { //Declared list of integers for output List<Integer> result = new ArrayList<>(); //Traverse an array for (int val : nums) { //Visit at that index int index = Math.abs(val) - 1; /* If number present at index is -ve, It means it is already appeared in an array. */ if (nums[index] < 0) result.add(index + 1); else nums[index] = -nums[index]; } return result; } |
