LeetCode Problem 2965

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Math, Matrix

Solution

LeetCode 2965 - Find Missing and Repeated Values

Problem Understanding

The problem gives us an n x n matrix called grid. Every value in the matrix should normally contain all integers from 1 to n² exactly once. However, there is one mistake in the matrix:

• One number appears twice.
• One number is completely missing.

Our task is to return these two numbers in the format:

• ans[0] = repeated number
• ans[1] = missing number

For example, if n = 2, then the valid numbers should be:

1, 2, 3, 4

If the matrix contains:

1, 2, 2, 3

then 2 is repeated and 4 is missing.

The input matrix is guaranteed to contain exactly one duplicated number and exactly one missing number. This guarantee is important because it simplifies the logic significantly. We do not need to handle multiple duplicates or invalid values outside the expected range.

The constraints are relatively small:

• 2 <= n <= 50
• Total elements are at most 2500

Since the total number of elements is small, even straightforward approaches are fast enough. We do not need highly optimized advanced algorithms. A clean linear solution works perfectly.

There are several important edge cases to think about:

• The repeated number could be 1.
• The missing number could be n².
• The duplicate may appear in different rows.
• The matrix is 2D, so we must correctly traverse every element.
• The duplicate might appear immediately next to itself or far apart.

The problem guarantees that exactly one value is repeated and exactly one value is missing, so we can rely on that invariant throughout the solution.

Approaches

Brute Force Approach

A naive solution would check every number from 1 to n² and count how many times it appears in the matrix.

For each candidate number:

1. Traverse the entire matrix.
2. Count occurrences.
3. If the count is 2, it is the repeated number.
4. If the count is 0, it is the missing number.

This approach is correct because it explicitly verifies the frequency of every possible value.

However, it is inefficient because for every number in the range [1, n²], we scan the entire matrix again. Since the matrix contains n² elements, this leads to quadratic work over the total number of values.

Optimal Approach

A much better solution uses a frequency array or hash set while traversing the matrix only once.

The key observation is that all values should appear exactly once. Therefore:

• The first time we see a number, we mark it as visited.
• If we see the same number again, that number is the duplicate.
• After processing the matrix, the number that was never visited is the missing number.

This works because the problem guarantees exactly one repeated value and exactly one missing value.

Since the values are constrained to the range [1, n²], we can use a simple frequency array of size n² + 1.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n⁴)	O(1)	Recounts occurrences for every number
Optimal	O(n²)	O(n²)	Single traversal with frequency tracking

Algorithm Walkthrough

1. Determine the size n of the matrix.
2. Create a frequency array called count of size n² + 1, initialized with zeros. Index i will store how many times number i appears in the matrix.
3. Traverse every row and every value in the matrix.
4. For each number:

• Increment its frequency in count.
• If the frequency becomes 2, record it as the repeated number.

5. After processing the matrix, iterate through numbers from 1 to n².
6. The number whose frequency is 0 is the missing number.
7. Return [repeated, missing].

Why it works

The matrix should contain every number from 1 to n² exactly once. Because exactly one number is duplicated and exactly one number is missing:

• The duplicated number will have frequency 2.
• The missing number will have frequency 0.
• Every other number will have frequency 1.

By counting occurrences directly, we uniquely identify both required values.

Python Solution

from typing import List

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        n = len(grid)
        max_value = n * n
        
        count = [0] * (max_value + 1)
        
        repeated = -1
        missing = -1
        
        for row in grid:
            for value in row:
                count[value] += 1
                
                if count[value] == 2:
                    repeated = value
        
        for number in range(1, max_value + 1):
            if count[number] == 0:
                missing = number
                break
        
        return [repeated, missing]

The implementation starts by calculating n², which represents the maximum expected value in the matrix.

A frequency array is then allocated. Since the values range from 1 to n², we use an array of size n² + 1 so that the number itself can act as the index.

The nested loops traverse every element in the matrix. Each number increments its frequency count. When a count becomes 2, we immediately know that the value is repeated.

After processing all elements, a final scan over the frequency array identifies the missing value, which is the only number whose count remains 0.

Finally, the function returns the repeated and missing values in the required order.

Go Solution

func findMissingAndRepeatedValues(grid [][]int) []int {
    n := len(grid)
    maxValue := n * n

    count := make([]int, maxValue+1)

    repeated := -1
    missing := -1

    for _, row := range grid {
        for _, value := range row {
            count[value]++

            if count[value] == 2 {
                repeated = value
            }
        }
    }

    for number := 1; number <= maxValue; number++ {
        if count[number] == 0 {
            missing = number
            break
        }
    }

    return []int{repeated, missing}
}

The Go implementation follows the same logic as the Python version.

The frequency array is created using make([]int, maxValue+1). Go slices are initialized with zero values automatically, so no extra initialization step is needed.

Since the constraints are small, integer overflow is not a concern. The largest possible value is only 2500.

The result is returned as a slice containing the repeated number followed by the missing number.

Worked Examples

Example 1

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

Here:

n = 2
n² = 4
Expected numbers: 1, 2, 3, 4

Initial frequency array:

Number	Count
1	0
2	0
3	0
4	0

Process the matrix:

Current Value	Updated Count	Repeated?
1	1	No
3	1	No
2	1	No
2	2	Yes, repeated = 2

Final frequency table:

Number	Count
1	1
2	2
3	1
4	0

The missing number is 4.

Final answer:

[2, 4]

Example 2

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

Here:

n = 3
n² = 9
Expected numbers: 1 through 9

Process the matrix:

Current Value	Updated Count	Repeated?
9	1	No
1	1	No
7	1	No
8	1	No
9	2	Yes, repeated = 9
2	1	No
3	1	No
4	1	No
6	1	No

Frequency summary:

Number	Count
1	1
2	1
3	1
4	1
5	0
6	1
7	1
8	1
9	2

The missing number is 5.

Final answer:

[9, 5]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Every matrix element is visited once
Space	O(n²)	Frequency array stores counts for numbers from 1 to n²

The matrix contains exactly n² elements, and each one is processed once. The final scan over the frequency array also takes O(n²) time, so the overall complexity remains linear with respect to the total number of elements.

The frequency array requires storage proportional to the range of possible values, which is also n².

Test Cases

from typing import List

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        n = len(grid)
        max_value = n * n
        
        count = [0] * (max_value + 1)
        
        repeated = -1
        missing = -1
        
        for row in grid:
            for value in row:
                count[value] += 1
                
                if count[value] == 2:
                    repeated = value
        
        for number in range(1, max_value + 1):
            if count[number] == 0:
                missing = number
                break
        
        return [repeated, missing]

solution = Solution()

assert solution.findMissingAndRepeatedValues([[1,3],[2,2]]) == [2,4]  # Example 1
assert solution.findMissingAndRepeatedValues([[9,1,7],[8,9,2],[3,4,6]]) == [9,5]  # Example 2

assert solution.findMissingAndRepeatedValues([[1,1],[3,4]]) == [1,2]  # Smallest duplicate
assert solution.findMissingAndRepeatedValues([[2,2],[3,4]]) == [2,1]  # Missing smallest number
assert solution.findMissingAndRepeatedValues([[1,2],[4,4]]) == [4,3]  # Missing middle value

assert solution.findMissingAndRepeatedValues([
    [1,2,3],
    [4,5,6],
    [7,8,8]
]) == [8,9]  # Missing largest value

assert solution.findMissingAndRepeatedValues([
    [5,1,2],
    [3,4,6],
    [7,8,5]
]) == [5,9]  # Duplicate appears in different rows

Test Summary

Test	Why
[[1,3],[2,2]]	Basic example case
[[9,1,7],[8,9,2],[3,4,6]]	Larger matrix example
[[1,1],[3,4]]	Duplicate is the smallest number
[[2,2],[3,4]]	Missing value is the smallest number
[[1,2],[4,4]]	Missing number in the middle
Matrix with duplicate 8	Missing largest value
Duplicate across rows	Confirms traversal correctness

Edge Cases

One important edge case occurs when the repeated number is 1. Some implementations accidentally assume the duplicate must appear later in the range. Our frequency-based approach handles this naturally because every value is treated identically.

Another important case is when the missing number is n², the largest possible value. Incorrect loops sometimes stop too early and fail to check the last number. Our implementation explicitly iterates from 1 through n² inclusive, so the largest value is always checked.

A third important edge case happens when the duplicate appears in different rows rather than adjacent positions. Since the algorithm traverses the entire matrix systematically and stores global frequencies, the physical location of the duplicate does not matter. The counting mechanism still correctly identifies the repeated value.