Brute Force Solution

The brute force solution involves iterating through the expected range of numbers (1 to n*n) and checking their occurrences in the grid. We can use a hash map or a simple counter for each number to keep track of occurrences. The number with two occurrences is the repeating number, and the number with zero occurrences is the missing number.

Code (Python)

def find_missing_repeating_brute_force(grid):
    n = len(grid)
    counts = {}
    for i in range(1, n * n + 1):
        counts[i] = 0

    for row in grid:
        for num in row:
            counts[num] += 1

    repeating = -1
    missing = -1
    for i in range(1, n * n + 1):
        if counts[i] == 0:
            missing = i
        elif counts[i] == 2:
            repeating = i

    return [repeating, missing]

Big O Analysis

• Time Complexity: O(n^2) - We iterate through the entire grid once and then iterate through the numbers from 1 to n*n, both taking O(n^2) time.
• Space Complexity: O(n^2) - We use a hash map to store the counts of each number, which takes O(n^2) space.

Optimal Solution

A more optimal solution leverages the mathematical properties of the sum and sum of squares of numbers. We can calculate the expected sum and sum of squares of numbers from 1 to n*n, and compare them with the actual sum and sum of squares of the numbers in the grid. The differences will allow us to derive the repeating and missing numbers.

Let:

• S_actual = Actual sum of numbers in the grid.
• SS_actual = Actual sum of squares of numbers in the grid.
• S_expected = Expected sum of numbers from 1 to n*n = n*n * (n*n + 1) / 2
• SS_expected = Expected sum of squares of numbers from 1 to n*n = n*n * (n*n + 1) * (2*n*n + 1) / 6
• a = repeating number
• b = missing number

Then:

• S_expected - S_actual = b - a
• SS_expected - SS_actual = b^2 - a^2 = (b - a) * (b + a)

Let diff_sum = S_expected - S_actual and diff_sum_sq = SS_expected - SS_actual

Then b - a = diff_sum and b + a = diff_sum_sq / diff_sum

We can solve these two equations to find a and b.

Code (Python)

def find_missing_repeating_optimal(grid):
    n = len(grid)
    s_actual = 0
    ss_actual = 0
    for row in grid:
        for num in row:
            s_actual += num
            ss_actual += num * num

    nn = n * n
    s_expected = nn * (nn + 1) // 2
    ss_expected = nn * (nn + 1) * (2 * nn + 1) // 6

    diff_sum = s_expected - s_actual
    diff_sum_sq = ss_expected - ss_actual

    sum_ab = diff_sum_sq // diff_sum

    a = (sum_ab - diff_sum) // 2
    b = diff_sum + a

    return [a, b]

Big O Analysis

• Time Complexity: O(n^2) - We iterate through the grid once to calculate the actual sum and sum of squares.
• Space Complexity: O(1) - We use only a few constant extra variables.

Edge Cases

• Empty Grid: The problem states that n >= 2, so an empty grid is not an applicable edge case.
• Large Numbers: The sums and sums of squares can become very large, so use appropriate integer types to avoid overflow (e.g., long in Java or int in Python). The Python solution handles this automatically as ints are arbitrarily sized.
• Zero: The numbers are in range [1, n^2], so we do not need to handle zero.

Summary

The optimal solution provides a significant improvement in space complexity compared to the brute force solution, while maintaining the same time complexity. It utilizes mathematical properties to avoid the need for extra data structures, making it more efficient and scalable.