Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Problem Challenge 1: Find the Corrupt Pair (easy)

Problem Statement

We are given an unsorted array containing ‘n’ numbers taken from the range 1 to ‘n’. The array originally contained all the numbers from 1 to ‘n’, but due to a data error, one of the numbers got duplicated which also resulted in one number going missing. Find both these numbers.

Example 1:

Input: [3, 1, 2, 5, 2]
Output: [2, 4]
Explanation: '2' is duplicated and '4' is missing.

Example 2:

Input: [3, 1, 2, 3, 6, 4]
Output: [3, 5]
Explanation: '3' is duplicated and '5' is missing.

Constraints:

  • 2 <= nums.length <= 10^4

.....

.....

.....

Like the course? Get enrolled and start learning!
S

Sinai Park

· 3 years ago

solution Image

S

sumeet sood

· 3 years ago

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];
}
Show 2 replies
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findNumbers(self, nums):
   
    def swap(i, j):
      nums[i], nums[j] = nums[j], nums[i]

    for i in range(len(nums)):
      while nums[i] != i + 1 and nums[i] != nums[nums[i] - 1]:
        swap(i, nums[i] - 1)

    result = []
    for i in range(len(nums)):
      if nums[i] != i + 1:
        result.append(nums[i])
        result.append(i + 1)
        return result

    return None