Removing duplicate elements within array

Question

I would like to understand a specific line in this code I am studying from geeksfogeeks. Here is the main code:

class Main
{
    // Function to remove duplicate elements
    // This function returns new size of modified
    // array.
   static int removeDuplicates(int arr[], int n)
   {
    // Return, if array is empty
    // or contains a single element
    if (n==0 || n==1)
        return n;

    int[] temp = new int[n];

    // Start traversing elements
    int j = 0;
    for (int i=0; i<n-1; i++)
        // If current element is not equal
        // to next element then store that
        // current element
        if (arr[i] != arr[i+1])
            temp[j++] = arr[i];

    // Store the last element as whether
    // it is unique or repeated, it hasn't
    // stored previously
    temp[j++] = arr[n-1];   

    // Modify original array
    for (int i=0; i<j; i++)
        arr[i] = temp[i];

    return j;
}

public static void main (String[] args) 
{
    int arr[] = {1, 2, 2, 3, 4, 4, 4, 5, 5};
    int n = arr.length;

    n = removeDuplicates(arr, n);

    // Print updated array
    for (int i=0; i<n; i++)
       System.out.print(arr[i]+" ");
}
}

If I understand this code correctly, what it is doing is iterating through the intial given array and comparing if the next element of the array is of same value. If it's not, then it adds that 'unique' element to the temp array, which then uses the value of j (which has been increasing in value according to how many unique elements there are) to rewrite the original array over.

What I don't get is this line

 temp[j++] = arr[n-1];

What is the purpose of this line? I know it is increasing the value of J but the " n-1" doesn't make whole lot of sense.

I would appreciate any insight on this topic and thank you ahead of time for well..your time.

Possible duplicate of [How to efficiently remove duplicates from an array without using Set](https://stackoverflow.com/questions/17967114/how-to-efficiently-remove-duplicates-from-an-array-without-using-set) — Vikasdeep Singh, Mar 28 '18 at 00:41
I suggest returning the result Array. And don't modify the origin one — John, Mar 28 '18 at 00:53

score 1 · Answer 1 · edited Mar 28 '18 at 01:35

Removing duplicate elements within array

Your program doesn't remove duplicates from the array. It only removes them if they are successive. E.g. {1,2,2,3} becomes {1,2,3} but {1,2,3,2} still remains {1,2,3,2}. However, if the input array is sorted, then all the duplicates will be removed. Please, notice that in the {1,2,2,3} the second number two is added to temp[]. (Meaning that only the last number in sequence of equal numbers is added to temp[]).

static int removeDuplicates(int arr[], int n)

You don't need the caller to pass the size of the array. In Java, arrays are special objects that offer a property called length. So you can figure out the length like so int n = arr.length;. You need to pass the array size in languages like C, not in Java.

What I don't get is this line

temp[j++] = arr[n-1];

Examine the conditions of your for loop above this statement.

for (int i=0; i<n-1; i++)

As you can see, it is run only till i is less than n-1. In English words, you are running this loop till the second last element only. This is because inside the for loop, you are comparing the ith element with i+1th element. That way, in the last iteration, you are comparing the second last element with the last element. You can't go further since there is nothing after the last element. However, with this approach you won't be adding the last element in the temp array. So you had to write an extra line of code to add the last element after the loop is over.

score 1 · Answer 2 · edited Mar 28 '18 at 01:55

temp[j++] = arr[n-1] is required because of the conditions of the for loop.

For loop is iterating until i is less than n-1. If the size of an array is 4, for example array: {1, 2, 3, 4}

n-1 = index 3 cannot be compared with index 4 (arr[i+1])

This prevents the for loop from going out of bounds. Since the last element is not added to the temp array, temp[j++] = arr[n-1] is needed to add the last element to the temp array.

Removing duplicate elements within array

2 Answers2