2 Added note from comments. edited Oct 10 '17 at 12:55 David Richerby 74.7k1616 gold badges117117 silver badges208208 bronze badges There's an obvious in-place variant of the boolean array technique using the order of the elements as the store (where arr[x] == x for "found" elements). Unlike the partition variant that can be justified for being more general I'm unsure when you'd actually need something like this, but it is simple. for idx from n-4 to n while arr[arr[idx]] != arr[idx] swap(arr[arr[idx]], arr[idx])  This just repeatedly puts arr[idx] at the location arr[idx] until you find that location already taken, at which point it must be a duplicate. Note that the total number of swaps is bounded by $$n$$ since each swap makes its exit condition correct. There's an obvious in-place variant of the boolean array technique using the order of the elements as the store (where arr[x] == x for "found" elements). Unlike the partition variant that can be justified for being more general I'm unsure when you'd actually need something like this, but it is simple. for idx from n-4 to n while arr[arr[idx]] != arr[idx] swap(arr[arr[idx]], arr[idx])  This just repeatedly puts arr[idx] at the location arr[idx] until you find that location already taken, at which point it must be a duplicate. There's an obvious in-place variant of the boolean array technique using the order of the elements as the store (where arr[x] == x for "found" elements). Unlike the partition variant that can be justified for being more general I'm unsure when you'd actually need something like this, but it is simple. for idx from n-4 to n while arr[arr[idx]] != arr[idx] swap(arr[arr[idx]], arr[idx])  This just repeatedly puts arr[idx] at the location arr[idx] until you find that location already taken, at which point it must be a duplicate. Note that the total number of swaps is bounded by $$n$$ since each swap makes its exit condition correct. 1 answered Oct 9 '17 at 19:29 Veedrac 56811 gold badge55 silver badges1414 bronze badges There's an obvious in-place variant of the boolean array technique using the order of the elements as the store (where arr[x] == x for "found" elements). Unlike the partition variant that can be justified for being more general I'm unsure when you'd actually need something like this, but it is simple. for idx from n-4 to n while arr[arr[idx]] != arr[idx] swap(arr[arr[idx]], arr[idx])  This just repeatedly puts arr[idx] at the location arr[idx] until you find that location already taken, at which point it must be a duplicate.