Problem Statement
Brute Force [Accepted]
class Solution:
def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
N = len(grid)
seen = set()
a, b = 0, 0
for row in range(N):
for col in range(N):
if grid[row][col] in seen:
a = grid[row][col]
seen.add(grid[row][col])
for i in range(1, N*N + 1):
if i not in seen:
b = i
return [a, b]
Editorial
Approach 1: Hash Map
class Solution:
def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
n = len(grid)
freq = {}
# Store frequency of each number in the grid
for row in grid:
for num in row:
freq[num] = freq.get(num, 0) + 1
# Check numbers from 1 to n^2 to find missing and repeated values
for num in range(1, n * n + 1):
if num not in freq:
missing = num # Number not present in grid
elif freq[num] == 2:
repeat = num # Number appears twice
return [repeat, missing]
Approach 2: Math
class Solution:
def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
# Get grid dimensions
n = len(grid)
total = n * n
# Calculate actual sums from grid
sum_val = sum(num for row in grid for num in row)
sqr_sum = sum(num * num for row in grid for num in row)
# Calculate differences from expected sums
# Expected sum: n(n+1)/2, Expected square sum: n(n+1)(2n+1)/6
sum_diff = sum_val - total * (total + 1) // 2
sqr_diff = sqr_sum - total * (total + 1) * (2 * total + 1) // 6
# Using math: If x is repeated and y is missing
# sum_diff = x - y
# sqr_diff = x² - y²
repeat = (sqr_diff // sum_diff + sum_diff) // 2
missing = (sqr_diff // sum_diff - sum_diff) // 2
return [repeat, missing]
