2965. Find Missing and Repeated Values

📝 Problem Details

• Title: 2965. Find Missing and Repeated Values
• Link: https://leetcode.com/problems/find-missing-and-repeated-values/
• Difficulty: Easy
• Tags/Categories:

input: 2D integer matrix grid of size n * n with values in the range of 1,n^2 each integer appears exactly once except a which appears twice and b which is missing find the repeating and missing numbers a and b, returning it in an array of size 2

💡 Explanation of Solution

- create a hashmap to store frequencies of each number
- iterate from 1 to n^2
	- check if the number exists in the map
		- if it doesn't, store it as the missing number
	- check if the frequency == 2
		- if it doesn't, store it as the single number

	- return both in an array

⌛ Complexity Analysis

Time Complexity: O(n^2) for iterating through the grid
Space Complexity: O(n^2) for storing results in the hashmap

💻 Implementation of Solution

class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        int n = grid.size();
        int missing = -1, repeat = -1;
 
        // Store frequency of each number in the grid
        unordered_map<int, int> freq;
        for (auto& row : grid) {
            for (int num : row) {
                freq[num]++;
            }
        }
 
        // Check numbers from 1 to n^2 to find missing and repeated values
        for (int num = 1; num <= n * n; num++) {
            if (!freq.count(num)) {
                missing = num;  // Number not present in grid
            } else if (freq[num] == 2) {
                repeat = num;  // Number appears twice
            }
        }
 
        return {repeat, missing};
    }
};