Question about Array Problem (Finding duplicates)

Question

So I have been looking at some sources to prepare my skills for interviews. I am confused about this one algorithm to find duplicate values in an array and just want someone to clarify where in this code do two points come up. These two points are: The array elements are confined to a block of being less than the array length itself and, How does the code determine if there are duplicates based on a negative value?

public class CheckDuplicates {
    public void hasDuplicates(int[] arrA){
        for(int i = 0; i < arrA.length; i++){
            if(arrA[Math.abs(arrA[i])] < 0){
                System.out.println("Array has duplicates: " + Math.abs(arrA[i]));

            } else{
                arrA[Math.abs(arrA[i])] = arrA[Math.abs(arrA[i])] * -1;
            }
        }
    }

    public static void main(String[] args) {
        int a[] = {1,6,1,1,2,2,5,6, 8, 9, 6, 6, 6, 6, 10, 10};
        new CheckDuplicates().hasDuplicates(a);
        // TODO Auto-generated method stub
    }
}

Rami · Accepted Answer · 2019-04-27 18:52:23Z

This was an interesting algorithm, I tried this out to figure out what was going on and in the example I tried I had values that were greater then the length of the array which resulted in java.lang.ArrayIndexOutOfBoundsException. I then realized in your example all array values were less then the length of the array itself.

The reason this works is because the algorithm is using the array value itself as the index to mark in the array to determine if there is a duplicate. As it is iterating through each element it sets the value of the element at the index of that element value negative, so as it iterates if the same value is there it goes and checks that index if it was ever set to a negative value then we know that a duplicate was found.

This becomes more visibly clear if you print out the array itself after each iteration:

[1, -6, 1, 1, 2, 2, 5, 6, 8, 9, 6, 6, 6, 6, 10, 10]
[1, -6, 1, 1, 2, 2, -5, 6, 8, 9, 6, 6, 6, 6, 10, 10]
Array has duplicates: 1
[1, -6, 1, 1, 2, 2, -5, 6, 8, 9, 6, 6, 6, 6, 10, 10]
Array has duplicates: 1
[1, -6, 1, 1, 2, 2, -5, 6, 8, 9, 6, 6, 6, 6, 10, 10]
[1, -6, -1, 1, 2, 2, -5, 6, 8, 9, 6, 6, 6, 6, 10, 10]
Array has duplicates: 2
[1, -6, -1, 1, 2, 2, -5, 6, 8, 9, 6, 6, 6, 6, 10, 10]
[1, -6, -1, 1, 2, -2, -5, 6, 8, 9, 6, 6, 6, 6, 10, 10]
Array has duplicates: 6
[1, -6, -1, 1, 2, -2, -5, 6, 8, 9, 6, 6, 6, 6, 10, 10]
[1, -6, -1, 1, 2, -2, -5, 6, -8, 9, 6, 6, 6, 6, 10, 10]
[1, -6, -1, 1, 2, -2, -5, 6, -8, -9, 6, 6, 6, 6, 10, 10]
Array has duplicates: 6
[1, -6, -1, 1, 2, -2, -5, 6, -8, -9, 6, 6, 6, 6, 10, 10]
Array has duplicates: 6
[1, -6, -1, 1, 2, -2, -5, 6, -8, -9, 6, 6, 6, 6, 10, 10]
Array has duplicates: 6
[1, -6, -1, 1, 2, -2, -5, 6, -8, -9, 6, 6, 6, 6, 10, 10]
Array has duplicates: 6
[1, -6, -1, 1, 2, -2, -5, 6, -8, -9, 6, 6, 6, 6, 10, 10]
[1, -6, -1, 1, 2, -2, -5, 6, -8, -9, -6, 6, 6, 6, 10, 10]
Array has duplicates: 10
[1, -6, -1, 1, 2, -2, -5, 6, -8, -9, -6, 6, 6, 6, 10, 10]

From this we can see that the first iteration (i=0) the value of the array element is 1. The value of the array at index 1 = 6. This value is > 0 so it goes to the else condition and sets the value at this index to -6. The second iteration it does the same thing at takes the value at index 6 (note Math.abs is used to prevent negative index) and sets the value of 5 to -5 yet again in the second iteration it went to the else condition.

Now at the third iteration the value of the array[2] = 1 which has a value of -6. Since this is negative we know that we had to have seen this value prior as it set the value to a negative number and therefore must be a duplicate.

Please note that in order for this algorithm to work the following preconditions must be met:

1) The values of the array elements must be [0,n) where n = the length of the array

Wow, you explained it really nicely. Thank you for your help! I am still looking through it but now it makes a lot more sense.

Joakim Danielson · Accepted Answer · 2019-04-27 18:15:12Z

0

Since all elements are less than the length they can use the value of an element as index. By setting a value to negative it is being marked as have being read so if a negative value is found it means that the element has already been read for another index and since that index correspond to the same value as the current index, remember they are using values of elements as index, we have a duplicate.

For the array in the example, index 1 is first set to -6 for i = 0 and then when i is 2 the value is 1 and for index 1 we have -6 so we have a duplicate at index 0 and 2

answered Apr 27, 2019 at 18:15

Joakim Danielson

53.1k5 gold badges36 silver badges79 bronze badges

Collectives™ on Stack Overflow

Question about Array Problem (Finding duplicates)

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related