educative.io

Https://www.educative.io/courses/grokking-coding-interview-patterns-java/solution-find-the-corrupt-pair

Courses
,
#1

given algorithm doesn’t sort the given array:

while (i < nums.length) {

        int correct = nums[i] - 1;

        if (nums[i] != nums[correct]) {

            swap(nums, i, correct);

        } else {

            i = i + 1;

        }

    }

solution comes out correct regardless but shouldn’t we be worried that the cyclic sort is not implemented correctly?

Input array ->[4, 3, 4, 5, 1]
output of sort algo ->[1,4,3,4,5]

Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Solution: Find the Corrupt Pair

Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Solution: Find the Corrupt Pair

1 Like
#2

Hello @Hubert_Dear,

You are correct in observing that the array is not fully sorted, but this behavior is intentional and acceptable for the specific task of finding the corrupted pair (one duplicated and one missing number). The goal of this algorithm is to find a pair of numbers where one is duplicated and the other is missing in a given array. It is not necessarily to sort the array. The cyclic sort in this algorithm is used to place numbers in their correct positions as much as possible, which is sufficient to identify the corrupted pair without needing to fully sort the array.

Despite not fully sorting the array, the algorithm efficiently identifies the corrupted pair with a time complexity of O(n), which is optimal for this problem.

I hope this helps in understanding why complete sorting is not applicable for this problem. Feel free to share further suggestions and feedback. We’d be happy to help. Thanks!

Happy learning!