The range is 0 .. n-1 and array is of size n. The array itself is used as flags by mutating it. The range is not -ve so a -ve value is used as flag. For x, a[x] is set to -ve on 1st visit if +ve, and added to dupes if -ve (after 1st visit). Note that the logic deals with item x and value a[x] where x = abs(x). As a[x] can be -ve, abs is needed.

i: i .. x a: a[i] .. a[x] //x = abs(a[i]) For x = 2, a[2] is set to -2 from 2. For x = -2, a[2] is -ve so added to dupes. i: 0 1 2 a: . 2 -2 -

//example - - a: 1 2 1 i: 0 1 2 dupes: 1

// does not work if a[i] = 0 (a): if a == null: throw set dupes = new for x in a: x = abs(x) if a[x] < 0: dupes.add(x) else: // a[x] >= 0 a[x] = -a[x] return dupesWhen a[x] is 0, set it to -n to be used as a flag (0 cannot be used as flag). Which means a[i] of -n denotes 0 so %n to handle it.

//example -n a: 0 0 0 i: 0 1 2 dupes: 0 --n a: 1 0 0 1 i: 0 1 2 3 dupes: 0 1

// O(n) time, O(1) space (a): if a == null: throw set dupes = new n = a.length() for x in a: x = abs(x) %n // to handle 0 values if a[x] < 0: dupes.add(x) else if a[x] > 0: a[x] = -a[x] else: //a[x] == 0 // to handle 0 values a[x] = -n return dupes

## No comments:

## Post a Comment