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...

*Related*

Do this algo have assumptions that the elements should be sorted in their natural order

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.