Detect duplicates

Trying to start a new category to archive some algorithmic problems that I come across. Let’s start with a very simple one.

Q. Given an array of N elements in which each element is an integer between 1 and N, detect if there are any duplicates in linear time O(n) and constant space O(1).

Please think about it being looking at my code.

My solution (in Java):

// If we are allowed to modify the array, it can be as simple as the following.
boolean detectDup(int[] a) {
    for (int i = 0; i < a.length; i++) {
        int d = Math.abs(a[i]) - 1;
        if (a[d] < 0) {
            return true;
        }
        a[d] = -a[d];
    }
    return false;
}
Advertisements

2 thoughts on “Detect duplicates

    • It doesn’t, as all it does is to detect if there is any integer that appears more than once in the array. No assumption on ordering.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s