Difficulty: Easy | Acceptance: 83.20% | Paid: No Topics: Array, Hash Table, Math, Matrix
You are given a 0-indexed 2D integer matrix grid of size n x n, where (r, c) represents:
A cell containing a value from 1 to n², inclusive. The value at cell (r, c) is unique, except for one value that appears twice and one value that is missing.
Return a 0-indexed integer array ans of size 2 where:
ans[0] is the repeated value. ans[1] is the missing value.
- Examples
- Constraints
- Hash Map / Frequency Array
- Mathematical Approach
- XOR Approach
- In-place Marking
Examples
Input: grid = [[1,3],[2,2]]
Output: [2,4]
Explanation: The number 2 is repeated and the number 4 is missing.
Input: grid = [[9,1,7],[8,9,2],[3,6,5]]
Output: [9,3]
Explanation: The number 9 is repeated and the number 3 is missing.
Constraints
2 <= n <= 50
1 <= grid[i][j] <= n²
Hash Map / Frequency Array
Intuition Use a frequency array to count occurrences of each number from 1 to n². The number with count 2 is repeated, and the number with count 0 is missing.
Steps
- Create a frequency array of size n² + 1
- Iterate through the grid and increment count for each value
- Scan the frequency array to find the repeated (count = 2) and missing (count = 0) numbers
class Solution:
def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
n = len(grid)
n_sq = n * n
count = [0] * (n_sq + 1)
for i in range(n):
for j in range(n):
count[grid[i][j]] += 1
repeated = 0
missing = 0
for i in range(1, n_sq + 1):
if count[i] == 2:
repeated = i
elif count[i] == 0:
missing = i
return [repeated, missing]Complexity
- Time: O(n²)
- Space: O(n²)
- Notes: Simple and intuitive, but uses extra space for the frequency array.
Mathematical Approach
Intuition Use sum and sum of squares formulas to create two equations and solve for the repeated and missing numbers.
Steps
- Calculate expected sum of 1 to n² and expected sum of squares
- Calculate actual sum and actual sum of squares from the grid
- Let x be repeated and y be missing. Solve: x - y = diff and x + y = sq_diff / diff
- Compute x and y from these equations
class Solution:
def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
n = len(grid)
n_sq = n * n
expected_sum = n_sq * (n_sq + 1) // 2
expected_sq_sum = n_sq * (n_sq + 1) * (2 * n_sq + 1) // 6
actual_sum = 0
actual_sq_sum = 0
for i in range(n):
for j in range(n):
actual_sum += grid[i][j]
actual_sq_sum += grid[i][j] * grid[i][j]
diff = actual_sum - expected_sum
sq_diff = actual_sq_sum - expected_sq_sum
sum_xy = sq_diff // diff
x = (diff + sum_xy) // 2
y = (sum_xy - diff) // 2
return [x, y]Complexity
- Time: O(n²)
- Space: O(1)
- Notes: Constant space but requires careful handling of large numbers to avoid overflow.
XOR Approach
Intuition XOR all numbers from 1 to n² with all grid elements. The result is XOR of repeated and missing numbers. Use bit manipulation to separate them.
Steps
- XOR all numbers from 1 to n² with all grid elements to get x XOR y
- Find the rightmost set bit in the result
- Partition numbers into two groups based on this bit and XOR each group separately
- Check which of the two numbers appears in the grid to identify the repeated one
class Solution:
def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
n = len(grid)
n_sq = n * n
xor = 0
for i in range(1, n_sq + 1):
xor ^= i
for i in range(n):
for j in range(n):
xor ^= grid[i][j]
rightmost_set_bit = xor & -xor
x = 0
y = 0
for i in range(1, n_sq + 1):
if i & rightmost_set_bit:
x ^= i
else:
y ^= i
for i in range(n):
for j in range(n):
if grid[i][j] & rightmost_set_bit:
x ^= grid[i][j]
else:
y ^= grid[i][j]
for i in range(n):
for j in range(n):
if grid[i][j] == x:
return [x, y]
return [y, x]Complexity
- Time: O(n²)
- Space: O(1)
- Notes: Elegant bit manipulation solution with constant space, but slightly more complex to understand.
In-place Marking
Intuition Use the grid itself as a marker by negating values at corresponding indices. The repeated number will be encountered twice, and the missing number’s position will remain positive.
Steps
- For each value in the grid, compute its index and negate the value at that index
- If we encounter a negative value, we found the repeated number
- After processing, the positive value indicates the missing number’s position
class Solution:
def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
n = len(grid)
n_sq = n * n
repeated = 0
missing = 0
for i in range(n):
for j in range(n):
idx = abs(grid[i][j]) - 1
row = idx // n
col = idx % n
if grid[row][col] < 0:
repeated = abs(grid[i][j])
else:
grid[row][col] *= -1
for i in range(n):
for j in range(n):
if grid[i][j] > 0:
missing = i * n + j + 1
break
return [repeated, missing]Complexity
- Time: O(n²)
- Space: O(1)
- Notes: Modifies the input array in-place, achieving constant space without extra data structures.