We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Missing and Repeated Values

Difficulty: Easy

Problem Description

You are given a 0-indexed 2D integer matrix grid of size n * n with values in the range [1, n^2]. Each integer appears exactly once except a which appears twice and b which is missing. The task is to find the repeating and missing numbers a and b.

Return a 0-indexed integer array ans of size 2 where ans[0] equals to a and ans[1] equals to b.

Key Insights

  • The matrix contains unique values from 1 to n^2, except for one number that repeats and one that is missing.
  • We can utilize a set or an array to track the occurrences of numbers.
  • The constraints ensure that we only need to check for two special cases (one missing, one repeated).

Space and Time Complexity

Time Complexity: O(n^2) - We need to traverse the entire grid to find the repeated and missing numbers. Space Complexity: O(n) - We may use a set or an array of size n^2 to track the occurrences.

Solution

To solve this problem, we can maintain a set to track the numbers we have seen while iterating through the grid. As we go through each element:

  1. If the number is already in the set, we identify it as the repeated number a.
  2. If it is not in the set, we add it.
  3. After processing all numbers, we can determine the missing number b by checking which number from 1 to n^2 is not in the set.

Code Solutions

def find_missing_and_repeated(grid):
    n = len(grid)
    seen = set()
    repeated = -1
    
    # Traverse the grid to find the repeated number
    for row in grid:
        for num in row:
            if num in seen:
                repeated = num  # Found the repeated number
            else:
                seen.add(num)  # Add unique numbers to the set
    
    # Find the missing number
    total_numbers = n * n
    missing = -1
    for i in range(1, total_numbers + 1):
        if i not in seen:
            missing = i  # Found the missing number
    
    return [repeated, missing]
← Back to All Questions