#2965

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find Missing and Repeated Values

Find the missing and repeated numbers in an n x n grid using array scanning and hash lookup.

Problem Statement

You are given an n x n grid, where each number between 1 and n^2 appears exactly once except for one number, which is repeated, and another, which is missing. Your task is to identify the repeated and missing numbers. You must return an array of size 2, where the first element is the repeated number and the second element is the missing number.

For example, if the grid is [[1, 3], [2, 2]], number 2 is repeated and number 4 is missing, so the answer is [2, 4].

Examples

Example 1

Input: grid = [[1,3],[2,2]]

Output: [2,4]

Number 2 is repeated and number 4 is missing so the answer is [2,4].

Example 2

Input: grid = [[9,1,7],[8,9,2],[3,4,6]]

Output: [9,5]

Number 9 is repeated and number 5 is missing so the answer is [9,5].

Constraints

2 <= n == grid.length == grid[i].length <= 50
1 <= grid[i][j] <= n * n
For all x that 1 <= x <= n * n there is exactly one x that is not equal to any of the grid members.
For all x that 1 <= x <= n * n there is exactly one x that is equal to exactly two of the grid members.
For all x that 1 <= x <= n * n except two of them there is exactly one pair of i, j that 0 <= i, j <= n - 1 and grid[i][j] == x.

Solution Approach

Array Scanning

Iterate through each element of the grid while marking the presence of numbers using an auxiliary data structure, such as a hash set, to detect the repeated number and identify the missing number by elimination.

Hash Lookup

Create a hash table to store the occurrences of each number. The missing number can be identified by looking for the one that does not appear, and the repeated number is the one that appears twice.

Math Approach

Leverage mathematical properties of the sum of integers and the sum of squares to find the missing and repeated numbers using the differences between the expected and actual sums.

Complexity Analysis

Metric	Value
Time	O(n^2)
Space	O(1)

The time complexity is O(n^2) due to the grid traversal, and the space complexity is O(1) because we are asked to use constant space, aside from the input grid.

What Interviewers Usually Probe

Efficiently applies array scanning combined with hash lookup for problem-solving.
Handles edge cases such as the smallest grid and missing number properly.
Uses mathematical tricks for sum or square comparisons in a clever manner.

Common Pitfalls or Variants

Common pitfalls

Not using an efficient hash table approach or array scanning pattern.
Missing the condition that exactly one number repeats, which can confuse the detection logic.
Overcomplicating the solution by introducing unnecessary algorithms or extra space usage.

Follow-up variants

Handling different grid sizes and ensuring the algorithm scales well.
Applying the method to non-square grids or matrices.
Exploring alternative methods that don’t involve hashing, such as sorting or indexing.

FAQ

What is the time complexity of the solution for Find Missing and Repeated Values?

The time complexity of the solution is O(n^2) because the grid needs to be scanned fully, and each element is processed once.

How do I approach solving Find Missing and Repeated Values using hash lookup?

You can use a hash table to store the frequency of each number and find which number repeats and which is missing by checking for the absence of a number in the hash table.

What is the role of mathematical sums in solving this problem?

Mathematical sums help by comparing the expected sum of numbers with the actual sum, providing a way to identify the missing and repeated numbers based on these differences.

How can I optimize space complexity for Find Missing and Repeated Values?

Space complexity can be optimized to O(1) by modifying the input grid directly, marking the visited numbers in place, instead of using an additional hash table.

What are the key pitfalls to avoid when solving Find Missing and Repeated Values?

Common pitfalls include using unnecessary extra space, not accounting for the exact number of repetitions, and mishandling edge cases such as the smallest possible grid.

terminal

Solution

Solution 1: Counting

We create an array $cnt$ of length $n^2 + 1$ to count the frequency of each number in the matrix.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        n = len(grid)
        cnt = [0] * (n * n + 1)
        for row in grid:
            for v in row:
                cnt[v] += 1
        ans = [0] * 2
        for i in range(1, n * n + 1):
            if cnt[i] == 2:
                ans[0] = i
            if cnt[i] == 0:
                ans[1] = i
        return ans

Continue Practicing

#3044 most frequent prime #2963 count the number of good partitions #2946 matrix similarity after cyclic shifts