Skip to content

← leetcode

Find Missing and Repeated Values

· Easy

LeetCode problem 2965

We need to find the duplicate value and the missing value.

  • we can find the duplicate value by iterating through grid and checking which values appear twice
  • we can find the missing value by summing all the values from 1 to n*n and subtracting the sum of all the values in grid minus the duplicate value from it

code

class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        int n = grid.size();
        int mp[2501] = {0};

        int sum = 0;
        int duplicate = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                ++mp[grid[i][j]];
                if (mp[grid[i][j]] == 2) {
                    duplicate = grid[i][j];
                }
                sum += grid[i][j];
            }
        }

        return {duplicate, (n*n)*(n*n+1)/2 - sum + duplicate};
    }
};

complexity

  • Time: O(n)
  • Space: O(n)