Problem Description

You are given a 2D integer matrix grid with dimensions n × n (0-indexed). The matrix contains values ranging from 1 to n².

The matrix has the following properties:

• Every integer from 1 to n² should appear exactly once
• However, there's one integer a that appears twice (duplicate)
• And there's one integer b that is missing (doesn't appear at all)

Your task is to identify these two numbers:

• Find the number a that appears twice in the matrix
• Find the number b that is missing from the matrix

Return your answer as an array ans of size 2, where:

• ans[0] = a (the repeated number)
• ans[1] = b (the missing number)

For example, if you have a 2×2 matrix that should contain numbers 1 through 4, but instead contains [1, 2, 2, 3], then:

• The number 2 appears twice (repeated)
• The number 4 is missing
• You would return [2, 4]

Intuition

The key insight is that we need to track which numbers appear in the matrix and how many times each appears. Since we know the matrix should contain exactly the numbers from 1 to n², we can use a frequency counting approach.

Think of it like taking attendance in a classroom where each student has a unique ID from 1 to n². We go through the entire matrix and mark how many times we see each number. After counting:

• The number that was marked twice is our duplicate
• The number that was never marked is our missing value

Why does counting work here? Because we have a well-defined range [1, n²] and we know exactly what should be present. It's like having a checklist of numbers 1 through n² and checking off each number as we encounter it in the matrix.

The counting array cnt acts as our checklist where cnt[i] tells us how many times number i appears in the matrix. In a perfect scenario, every cnt[i] would be 1. But since we have one duplicate and one missing:

• One position will have cnt[i] = 2 (the repeated number)
• One position will have cnt[i] = 0 (the missing number)
• All other positions will have cnt[i] = 1

This approach is straightforward because we're directly addressing what the problem asks for - finding frequencies of numbers in a known range.

Learn more about Math patterns.

Solution Approach

The implementation follows a counting strategy using an array to track the frequency of each number:

Step 1: Initialize the Counting Array

We create an array cnt of size n * n + 1 initialized with zeros. We use size n * n + 1 instead of n * n to make indexing convenient - cnt[i] will store the count of number i, and we can ignore index 0.

n = len(grid)
cnt = [0] * (n * n + 1)

Step 2: Count Frequencies

We traverse through the entire matrix and increment the count for each number we encounter:

for row in grid:
    for v in row:
        cnt[v] += 1

After this step:

• cnt[i] = 0 means number i never appeared (missing)
• cnt[i] = 1 means number i appeared exactly once (normal)
• cnt[i] = 2 means number i appeared twice (duplicate)

Step 3: Find the Duplicate and Missing Numbers

We iterate through numbers 1 to n² and check their frequencies:

ans = [0] * 2
for i in range(1, n * n + 1):
    if cnt[i] == 2:
        ans[0] = i  # Found the duplicate
    if cnt[i] == 0:
        ans[1] = i  # Found the missing number

Time and Space Complexity:

• Time Complexity: O(n²) for traversing the matrix once and then checking the count array once
• Space Complexity: O(n²) for the counting array

The beauty of this solution lies in its simplicity - we're essentially creating a frequency map and then scanning it to find anomalies (count of 2 for duplicate, count of 0 for missing).

Example Walkthrough

Let's walk through a concrete example with a 3×3 matrix that should contain numbers 1 through 9.

Given matrix:

grid = [[1, 3, 2],
        [9, 7, 6],
        [5, 3, 8]]

Step 1: Initialize the counting array

We create cnt with size 10 (n² + 1 = 9 + 1):

cnt = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
      index: 0  1  2  3  4  5  6  7  8  9

Step 2: Count frequencies by traversing the matrix

Processing row by row:

• Row 1: [1, 3, 2]

  • See 1: cnt[1]++ → cnt = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
  • See 3: cnt[3]++ → cnt = [0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
  • See 2: cnt[2]++ → cnt = [0, 1, 1, 1, 0, 0, 0, 0, 0, 0]

• Row 2: [9, 7, 6]

  • See 9: cnt[9]++ → cnt = [0, 1, 1, 1, 0, 0, 0, 0, 0, 1]
  • See 7: cnt[7]++ → cnt = [0, 1, 1, 1, 0, 0, 0, 1, 0, 1]
  • See 6: cnt[6]++ → cnt = [0, 1, 1, 1, 0, 0, 1, 1, 0, 1]

• Row 3: [5, 3, 8]

  • See 5: cnt[5]++ → cnt = [0, 1, 1, 1, 0, 1, 1, 1, 0, 1]
  • See 3: cnt[3]++ → cnt = [0, 1, 1, 2, 0, 1, 1, 1, 0, 1]
  • See 8: cnt[8]++ → cnt = [0, 1, 1, 2, 0, 1, 1, 1, 1, 1]

Final count array:

cnt = [0, 1, 1, 2, 0, 1, 1, 1, 1, 1]
      index: 0  1  2  3  4  5  6  7  8  9

Step 3: Find the duplicate and missing numbers

Scan through indices 1 to 9:

• i = 1: cnt[1] = 1 (normal)
• i = 2: cnt[2] = 1 (normal)
• i = 3: cnt[3] = 2 ✓ Found duplicate! ans[0] = 3
• i = 4: cnt[4] = 0 ✓ Found missing! ans[1] = 4
• i = 5: cnt[5] = 1 (normal)
• i = 6: cnt[6] = 1 (normal)
• i = 7: cnt[7] = 1 (normal)
• i = 8: cnt[8] = 1 (normal)
• i = 9: cnt[9] = 1 (normal)

Result: ans = [3, 4]

• The number 3 appears twice in the matrix
• The number 4 is missing from the matrix

Solution Implementation

Time and Space Complexity

The time complexity is O(n²), where n is the side length of the matrix. This is because:

• The nested loops iterate through all elements in the n × n grid, performing n² iterations
• Each operation inside the loops (accessing and incrementing cnt[v]) takes O(1) time
• The second loop iterates from 1 to n², which is also O(n²) iterations
• Overall: O(n²) + O(n²) = O(n²)

The space complexity is O(n²), where n is the side length of the matrix. This is because:

• The cnt array has size n² + 1, which requires O(n²) space
• The ans array has fixed size 2, which is O(1)
• Overall: O(n²) + O(1) = O(n²)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Array Sizing

A frequent mistake is creating the counting array with size n * n instead of n * n + 1:

Incorrect:

cnt = [0] * (n * n)  # Wrong! This creates indices 0 to n²-1

Why it fails: Since we need to track numbers from 1 to n², we need indices 1 through n². With size n * n, the array only has indices 0 to n²-1, causing an IndexError when trying to access cnt[n²].

Correct Solution:

cnt = [0] * (n * n + 1)  # Correct! Indices 0 to n²

2. Early Termination Optimization Trap

Some might try to optimize by breaking early once both values are found:

Problematic:

for i in range(1, n * n + 1):
    if cnt[i] == 2:
        ans[0] = i
    if cnt[i] == 0:
        ans[1] = i
    if ans[0] != 0 and ans[1] != 0:
        break  # Seems logical but can cause issues

Why it's risky: While this works in theory, it assumes both conditions will be met before the loop ends. If there's any edge case or data corruption where multiple duplicates exist (even though the problem guarantees exactly one), this could return incorrect partial results.

Better Approach: Keep the simple iteration without early breaks - the performance gain is negligible for this problem size, and the code remains more robust.

3. Using a Dictionary Instead of Array

While using a dictionary seems intuitive for frequency counting:

Alternative approach:

freq = {}
for row in grid:
    for v in row:
        freq[v] = freq.get(v, 0) + 1

The issue: You then need to check for missing values differently:

for i in range(1, n * n + 1):
    if i not in freq:  # Missing value
        ans[1] = i
    elif freq[i] == 2:  # Duplicate
        ans[0] = i

While this works, it's slightly less efficient due to dictionary operations and the need to explicitly check for missing keys. The array approach is cleaner since missing values naturally have a count of 0.