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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Missing and Repeated Values

Number: 3227

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Microsoft, Meta

Problem Description

Given an n x n matrix containing numbers in the range [1, n²] where all but two numbers appear exactly once—one number appears twice and one is missing—find the repeating number and the missing number. Return the answer as a 0-indexed array where the first element is the repeated number and the second is the missing one.

Key Insights

  • The grid is treated as a flattened list of numbers in the range [1, n²].
  • Use a frequency counter (hash table or array) to track occurrences of each integer.
  • The number with frequency 2 is the repeated value, while the one with frequency 0 is the missing value.
  • The grid size is small (n up to 50), so a simple O(n²) approach is efficient.

Space and Time Complexity

Time Complexity: O(n²), where n² is the total number of elements in the grid. Space Complexity: O(n²), for storing the frequency of each number in the worst case.

Solution

Flatten the grid and use a hash table (or frequency array) to count appearances of each number from 1 to n². Then iterate through the range [1, n²] to determine which number appears twice (the repeated value) and which number is missing (has a count of zero). Return these two numbers in an array where the repeated number is first and the missing number is second. This method leverages simple counting and iteration to efficiently solve the problem.

Code Solutions

def find_missing_repeated(grid):
    # Determine n from the grid dimensions
    n = len(grid)
    total_numbers = n * n
    # Create a frequency dictionary to count occurrences
    frequency = {}
    # Iterate through each number in the grid and count its frequency
    for row in grid:
        for num in row:
            frequency[num] = frequency.get(num, 0) + 1
    repeated = -1
    missing = -1
    # Iterate through the expected numbers from 1 to total_numbers
    for num in range(1, total_numbers + 1):
        count = frequency.get(num, 0)
        if count == 0:
            missing = num  # Found the missing number
        elif count == 2:
            repeated = num  # Found the repeated number
    return [repeated, missing]

# Example usage:
grid = [[1, 3], [2, 2]]
print(find_missing_repeated(grid))  # Output: [2, 4]
← Back to All Questions