💬 Discord
Sign In
NeetCode #55LC-2965EasyArrays & Hashing
← Back to All Problems

#55 · #2965 · Find Missing and Repeated Values(找出缺失和重复的数字)

📌 Problem Statement & Constraints

You are given an n x n grid where every integer from 1 to n^2 appears exactly once, except that one value is repeated and one is missing. Return [repeated, missing]. Constraints: 2 <= n <= 50.

💡 Core Algorithmic Approaches

  1. A hash set finds the repeated value in one pass.
  2. The missing value then follows from the sum identity: sum(grid) - n^2(n^2+1)/2 = repeated - missing.
  3. So missing = repeated - (sum(grid) - expected_sum).
  4. This avoids needing the sum of squares, and works for any grid shape.

💻 Benchmark Python3 Implementation

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        seen = set()
        repeated = -1
        total = 0
        n2 = len(grid) ** 2
        for row in grid:
            for v in row:
                total += v
                if v in seen:
                    repeated = v           # second sighting
                seen.add(v)
        expected = n2 * (n2 + 1) // 2
        missing = repeated - (total - expected)   # repeated - missing = total - expected
        return [repeated, missing]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): one pass over the grid.
💾 Space Complexity
O(n^2) for the set. A math-only variant (sum and sum of squares) would use O(1) space but risks overflow in fixed-width languages.

⚠️ Interview Pitfalls & Follow-ups

  • Sign error in the missing formula: total - expected == repeated - missing, so missing = repeated - (total - expected). Rearrange carefully.
  • Returning [missing, repeated]: the required order is [repeated, missing].
  • Using the sum-of-squares approach in a language with 32-bit ints: n^2 reaches 2500 and the sum of squares reaches about 5e9, which overflows. Python is safe, but mention the concern.
  • Forgetting that the grid is 2D: flatten it conceptually; the row structure is irrelevant.