But you're assuming that the input array (nums) is sorted; the problem description doesn't state that. And sorting it first would make the solution O(N * log N) instead of just O(N).

It can be a bit hard to explain, but each element of the solution posted here tells us two things... but about different numbers. One number is the actual value of the element, the other is the number that is equal to the index of the element plus 1.

So if we reach the end, for example, and see that nums[5] = 20002, then we know that the number 6 (i = 5 so i + 1 = 6) was seen twice, not the number 2. And yet we still preserved our ability to read the number 2 in this element with 20002 % 10000.

That's important because we'll be modifying the elements out of order in our first pass, and don't want to screw up our ability to properly read each number later on in the pass.

So in other words, in the first pass we're reading nums at i, but we're modifying nums at nums[i]. That's because we're treating nums very much like we would its own "seen" or "visited" array. We just don't want those two purposes for nums to impact each other, so we just... overlay another level of meaning onto the values stored in nums.

It's very much similar to using bit manipulation to combine two pieces of data into one.

Specialising in accessibility and website load speed / performance. If you have a question about [accessibility] or [page-speed-insights] ask away and I will help any way I can!

But you're assuming that the input array (

nums) is sorted; the problem description doesn't state that. And sorting it first would make the solutionO(N * log N)instead of justO(N).It can be a bit hard to explain, but each element of the solution posted here tells us two things...

but about different numbers. One number is the actual value of the element, the other is the number that is equal to theindexof the element plus1.So if we reach the end, for example, and see that

nums[5] = 20002, then we know that the number6(i = 5soi + 1 = 6) was seen twice,notthe number2. And yet we still preserved our ability to read the number2in this element with20002 % 10000.That's important because we'll be modifying the elements out of order in our first pass, and don't want to screw up our ability to properly read each number later on in the pass.

So in other words, in the first pass we're reading

numsati, but we're modifyingnumsatnums[i]. That's because we're treatingnumsvery much like we would its own "seen" or "visited" array. We just don't want those two purposes fornumsto impact each other, so we just... overlayanotherlevel of meaning onto the values stored innums.It's very much similar to using bit manipulation to combine two pieces of data into one.

This is why I am rubbish at these problems, I forget that

`.sort`

is expensive!I get it entirely now and thanks for taking the time to give such a detailed explanation!

No worries, and thanks for the question!