Given a sorted array, we have to write a code to remove the duplicates in-place such that each element appear only once and return the new length.
For this problem, we don’t have to use extra space. As we have to remove duplicates in-place (In O(1)).
Note that we have to return the new length, make sure to change the original array as well in place
For example:
Input : { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7 }
Output: 7
Our function should return length 7 with first seven elements of array are {1, 2, 3, 4, 5, 6, 7}. It doesn’t matter what you leave beyond the returned length
In this tutorial, I am going to discuss how we can efficiently remove the duplicate elements from a sorted array and it’s java code.
In an interview, I have seen many people try to solve this problem using Set (Set does not allow duplicates). But before using Set or any other data structure first clarify with your interviewer whether extra space is allowed or not.
Let me clarify again, we have to solve this problem in a single traversal and without using any extra space.
Remove Duplicates from Sorted Array – Java Code
In the problem statement it is already mentioned that the array is sorted. To solve this problem we can declare two indexes i an j to remove duplicate elements from an array.
Traverse an array and increment the value of i at each step. The value of index j is incremented when arr[i] is not equal to arr[i+1]. Repeat this step until the array is traversed completely.
The time complexity of this approach is O(n) and it’s space complexity is O(1).
Remove duplicates from an unsorted array
|
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
/* Remove Duplicate elements from Sorted Array */ public class RemoveDuplicate { public static int removeDuplicate(int[] arr) { /* If an array doesn't contain any element, Simply return 0. */ if(arr.length == 0) { return 0; } int j = 0; //Traverse an array for (int i = 0; i < arr.length - 1; i++) { //Put the unique element in an array //and increment the count of j if (arr[i] != arr[i + 1]) { arr[j++] = arr[i]; } } //Put the last element arr[j++] = arr[arr.length - 1]; return j; } public static void main(String[] args) { int arr[] = { 1, 2, 2, 3, 4, 4, 5, 6, 6, 7 }; int j = removeDuplicate(arr); for (int k = 0; k < j; k++) { System.out.print(arr[k] + " "); } } } |
Remove duplicates from sorted linked list
Remove Duplicates from Sorted Array InterviewBit Solution
Similar problem is present in an InterviewBit. In function argument instead of array it is list of integer. Let’s write it’s code.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
//Remove duplicates from sorted array interviewbit solution public class Solution { public int removeDuplicates(ArrayList<Integer> a) { if(a.size() == 0) return 0; int count = 0; for(int i = 0; i < a.size()-1; i++) { if(!a.get(i).equals(a.get(i+1))) { a.set(count++,a.get(i)); } } a.set(count++, a.get(a.size()-1)); return count; } } |
