algoadvance

You are given an integer array nums of size n containing each integer in the range [1, n] inclusive, exactly once or twice. There is one repeated number and the rest appear exactly once. Your task is to find the repeated and the missing integers. Return them in the form of a list [repeated, missing].

Clarifying Questions

  1. Input Constraints:
    • Is it guaranteed that there will be exactly one repeated number and exactly one missing number?
      • Yes.
  2. Output Format:
    • Return the repeated and missing numbers as a list [repeated, missing].
  3. Array Characteristics:
    • Can we modify the input array?
      • Yes, modifications to the input array are allowed if needed.

Strategy

To find the repeated and the missing values efficiently, we can use mathematical properties and iterative checks:

Steps:

  1. Traverse the list and identify the repeated number by checking the signs.
  2. Traverse the list again and identify the missing number based on non-visited elements.

Here’s a method to achieve this:

  1. Iterate through the array nums.
  2. Mark visited places by negating the value at the index corresponding to the current element’s absolute value.
    • Example: If the current element is x, negate the value at index abs(x) - 1.
  3. If we find a number that has already been marked negative, that’s our repeated number.
  4. To find the missing number, traverse the array a second time and look for the first positive value; the index of this value plus one will be our missing number.

Code

from typing import List

def findErrorNums(nums: List[int]) -> List[int]:
    n = len(nums)
    duplicate = -1
    missing = -1

    # Identify duplicate
    for num in nums:
        if nums[abs(num) - 1] < 0:
            duplicate = abs(num)
        else:
            nums[abs(num) - 1] *= -1

    # Identify missing
    for i in range(n):
        if nums[i] > 0:
            missing = i + 1
    
    return [duplicate, missing]

# Example usage
example = [4, 3, 6, 2, 1, 1]
print(findErrorNums(example))  # Output should be [1, 5]

Time Complexity

This approach ensures that we can find the repeated and missing values efficiently with linear time complexity and constant space complexity by modifying the input array in place.

Try our interview co-pilot at AlgoAdvance.com