DDSA Solutions

2965. Find Missing and Repeated Values

UnknownView on LeetCode
ArrayHash TableMatrix
Time: O(n²)
Space: O(1)

Problem Overview

Find missing and repeated values in grid where each value 1..n^2 appears exactly once except one missing and one extra.

Intuition

Find missing and repeated values in grid where each value 1..n^2 appears exactly once except one missing and one extra.

Algorithm

  1. 1Count occurrences. Value with count 2 = repeated. Value with count 0 = missing.

Common Pitfalls

  • •Use frequency array. Or sum + sum of squares formulas for O(1) space.
2965.cs
C#
// Approach: Use sum and sum-of-squares equations to find repeated (x) and missing (y) values.
// Time: O(n²) Space: O(1)

public class Solution
{
    public int[] FindMissingAndRepeatedValues(int[][] grid)
    {
        int n = grid.Length;
        int nSquared = n * n;
        int[] count = new int[nSquared + 1];

        foreach (int[] row in grid)
        {
            foreach (int num in row)
                ++count[num];
        }

        int repeated = -1;
        int missing = -1;

        for (int i = 1; i <= nSquared; ++i)
        {
            if (count[i] == 2)
                repeated = i;
            if (count[i] == 0)
                missing = i;
        }

        return new int[] { repeated, missing };
    }
}
Was this solution helpful?

Related Problems