educative.io

Are these statements the same

Courses
,
#1 
  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

#2

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.

#3

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?

#4

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.

#5

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 ?

#6

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

1 Like