if (nums[i] < nums.length && nums[i] != nums[nums[i]])
swap(nums, i, nums[i]);
is
nums[i] != nums[nums[i]]
the same as
nums[i] != i
if (nums[i] < nums.length && nums[i] != nums[nums[i]])
swap(nums, i, nums[i]);
is
nums[i] != nums[nums[i]]
the same as
nums[i] != i
No. These are two different things.
In nums[i] != nums[nums[i]] :
A value at index i should not be equal to the value at index of nums[i].
Here we’ll find first value at index i and then that value will be the index for nums i.e. nums[value].
In nums[i] != i :
Value at index i should not be equal to index i.
Is my understanding correct:
nums[i] != i" would still produce the correct answer but “nums[i] != nums[nums[i]]” is a little bit more optimal because it avoids unnecessary swaps?
Hi Ilya!
If you are saying that nums[i] != i condition will give the same result as nums[i] != nums[nums[i]] in the while loop then it is not correct.
nums[i] != i
If index i is not the same as the value at index i then it will swap the index i and the value at index i . For example: in nums= [3, 1, 0, 4]
since value at index 0
which is 3
is not the same as its index i.e. 3!=0
. So it will make the index as 3
and value as 0
which is absolutely wrong. We don’t want to swap the index rather we want the values at the respective index to be equal to their indices.
nums[i] != nums[nums[I]]:
If the value at index i is not the same as the value at index nums[I] then it will swap the value of index i and the value at index nums[i] . For example: in nums= [3, 1, 0, 4]
since value at index 0
which is 3
is not the same as value at index 3
i.e. 3!=4
. So it will swap the 3
and 4
values at 0
and 3
indices respectively. Now the array will be converted to : nums= [4, 1, 0, 3]
. This approach is being used in our lesson.
Hope it helps. If you still face any confusion then please let us know.
Thank you.
Hi @Asma_Yasin ,
No matter if we use nums[i] != i OR nums[i] != nums[nums[I]] it both gives the same output. You can verify that by printing the sorted array for both cases, it matches. I think nums[i] != i should also work because, essentially what we want to achieve in cyclic sort is element at index i should be i nums[i] == i, and so if it’s not the case we swap values at indexes nums[i] and nums[nums[i]].
Can you please clarify why you think this is wrong ?
I got it, nums[i] != i condition might work in this specific problem because there are no duplicate numbers, but in the next problem (Find the missing number), nums[i] != i will make it stuck in the loop. For example here - [2, 2, 1, 4], nums[i] != i will return true and it keeps swapping 2 with 2 indefinitely because 0 != 2 forever . so checking nums[i] != nums[nums[I]] helps, because it checks number at current index shouldn’t be same at number it’s swapping with, so 2 != 2 will be false and it will skip swapping and move to next index in the loop.
Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Find the Missing Number (easy) - Grokking the Coding Interview: Patterns for Coding Questions