Saturday, 4 July 2015

How to Remove Duplicates From a Sorted Array In Java?

In this tutorial, i am going to explain the solution in detail.

problem: Remove all duplicates from a sorted array, without using any additional array.

input   : [1,1,1,2,3,3,3,3,4,5,6,6,6,7,8,9,10,11,11]
output : [1,2,3,4,5,6,7,8,9,10,11]

Solution:

Let's see how to solve this problem.

The clue you can find here is, the array is a sorted array. Let's take an integer sorted array like below.

int a[] = {1,1,1,2,3,3,3,3,3,4,5,6,6,6,7,8,9,10,11,11};

By observing the input and output given at top, we can conclude that, apart from the first element (1) , all the elements have shifted their positions in the output. In other words, each unique element except first element, has been moved as far to the left as possible.

How to detect the duplicates in the original array?

In the sorted array, all the duplicate elements will be in adjacent positions. For example, elements 1,1,1 are all in adjacent positions, similarly 3,3,3,3,3,3 are adjacent to each other.

To find duplicates, we need to compare every two adjacent elements in the array traversal. The possible outcomes of comparison are

1. The two elements are equal, which means they are duplicates.
2. The two elements are not equal, which means they are distinct.

We need to treat the above two cases differently, to solve above problem.

i will explain, how to treat the above two cases with an example. Now consider a small array [15,23,23,23,26].

a. First 15 is compared with 23, and the 23 is the most recent unique element encountered and so it should be moved as far to the left as possible. Here 15 is already at 0th position, and is also unique, so 23 goes no where.
b. Compare next pair, i.e 23 ( at index 2), 23 ( at index 3). Since they are duplicates and 23 is already been accounted for in previous step, the only action we must take is to move to the next pair.
c. Once again, two 23s are compared and so again all we can do is move to the next step. Continue this process, until you find the non equal adjacent pair.
d. At the end, 26 is compared to 23, and 26 is the most recently encountered unique element, we move it to the index 2. i.e the array becomes [ 15, 23, 26, 23,23,26].
e. finally, we give only portion of the array which contains only unique elements as a result. i.e [15,23,26].

What we did here is, when two adjacent elements are equal, we are checking next pair. If any pair is not duplicate, we are moving the 2nd element in the pair to some other location. To do this we need to use two counters.

counter i, j. counter i is for looping the array, counter j indicates the position at which the most recently encountered unique element(2nd element in the pair, if elements are not equal) to be placed. It also represents the unique elements found in the array.

Now take a look at the algorithm :

1. Take two counters, i = 1, j = 0. Counter i is for looping the array, j indicates the position at which the most recently encountered unique element to be placed.
2. Compare successive pairs of elements, i.e compare 1st element with 0th element, 2nd element with 1st element, 3rd element with 2nd element ans so on.
3. While examining all pairs,
   a. If the pair of elements are equal, increment the counter i only.
   b. If the pair of elements are not equal, increment both counter i and j. Move the unique element to the        jth position.

The program is below.
package com.speakingcs.arrays;

public class RemoveDups {

 
 public static void main(String[] args) {
  
  int[] a = {1,1,1,2,3,3,3,3,4,5,6,6,6,7,8,9,10,11,11};
  
  removeDuplicates(a);
  
 }

 private static void removeDuplicates(int[] a) {
  
  // counter "i" is iterating the array, counter j indicates a position where unique element found so far has  to be placed. 
  // we start comparing of our adjacent elements from 1 i.e compare 1st and 0th elements, 2nd and 1st elements and so on. 
  // you can modify the code such that,compare 0th element with 1st, 1st element with 2nd and so on. 
  
  int i = 1, j = 0;
  
  // i increments every time.
  for(; i < a.length; i++) {
   
   //j increments only when adjacent pairs are not equal.
   if(a[i] != a[i-1]) {
    
    a[++j] = a[i];
   }
   
  }
  
  // print the array to console.
  for(i = 0; i <= j; i++) {
   System.out.print(a[i] +" ");
  }
  
 }

}



0 comments:

Post a Comment

Note: only a member of this blog may post a comment.