2965. Find Missing and Repeated Values

UnknownView on LeetCode

Array Hash Table Matrix

Time: O(n²)

Space: O(1)

Intuition

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

Algorithm

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

// 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?