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;
}

### Like this:

Like Loading...