Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
This can be solved in single iteration

sumeet sood

May 8, 2023

function find_corrupt_numbers(nums) {     let duplicateNumber, currentIndex = 0, missingIndex;     while(currentIndex < nums.length) {         if(nums[currentIndex] == currentIndex+1) currentIndex++;         else {             let swapIndex = nums[currentIndex]-1;             if(nums[swapIndex] == nums[currentIndex]) {                 duplicateNumber = nums[swapIndex];                 missingIndex = currentIndex;                 currentIndex++;             }             else [nums[swapIndex], nums[currentIndex]] = [nums[currentIndex], nums[swapIndex]]         }     }     return [duplicateNumber, missingIndex+1]; }

0

0

Comments
Comments
S
sumeet sood2 years ago

2 iterations are not required, above solution solves it in single iteration only

Enrique Fernández
Enrique Fernández10 months ago

I came up with the same solution at first, but I found out it fails with the next test case: [3, 1, 2, 3, 6, 4]

Eventually, cyclic sort would be at the next step: [1, 2, 3, 3, 6, 4], therefore it would return as solution -> [3, 4], as the second three is in the wrong p...

On this page