Find Missing and Repeated Values - Practice Coding Problems

Find Missing and Repeated Values - Problem

You are given a 0-indexed 2D integer matrix grid of size n * n with values in the range [1, n²]. Each integer appears exactly once except:

a which appears twice
b which is missing

Your task is to find the repeating and missing numbers a and b.

Return a 0-indexed integer array ans of size 2 where:

ans[0] equals to a (the repeated number)
ans[1] equals to b (the missing number)

Input & Output

Example 1 — Basic Case

$ Input: grid = [[1,3],[2,2]]

› Output: [2,4]

💡 Note: In a 2×2 grid, numbers should be [1,2,3,4]. Number 2 appears twice (repeated), number 4 is missing.

Example 2 — Larger Grid

$ Input: grid = [[9,1,7],[8,9,2],[3,4,6]]

› Output: [9,5]

💡 Note: In a 3×3 grid, numbers should be [1,2,3,4,5,6,7,8,9]. Number 9 appears twice, number 5 is missing.

Example 3 — Edge Positions

$ Input: grid = [[1,2],[4,4]]

› Output: [4,3]

💡 Note: Number 4 appears twice at positions (1,0) and (1,1). Number 3 is missing from the sequence [1,2,3,4].

Constraints

1 ≤ n ≤ 100
1 ≤ grid[i][j] ≤ n²
Exactly one number appears twice
Exactly one number is missing

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

2D grid with one repeated and one missing number from range [1, n²]

Count & Compare

Compare actual numbers against expected sequence [1, 2, 3, 4]

Result

Return [repeated, missing] as the answer

Key Takeaway

🎯 Key Insight: Use frequency counting or mathematical formulas to efficiently identify the duplicate and missing values

Asked in

a Amazon 25 M Microsoft 20 G Google 15 Apple 12

The key insight is to identify which number appears twice and which is missing from the expected sequence [1, n²]. The hash map approach provides the best balance of simplicity and efficiency. Time: O(n²), Space: O(n²) for counting, or use mathematical formulas for O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map - Count Frequencies	O(n²)	O(n²)	Use hash map to count frequency of each number in single pass
Mathematical Formula	O(n²)	O(1)	Use sum and sum of squares formulas to find repeated and missing numbers
Brute Force - Count Each Number	O(n⁴)	O(1)	Check each number from 1 to n² and count its occurrences in the grid

Hash Map - Count Frequencies — Algorithm Steps

Create hash map to store frequency of each number
Iterate through grid and count frequencies
Find number with frequency 2 (repeated) and missing number

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Single pass through grid, store counts in hash map

Check Counts

Look for frequency 2 (repeated) and 0 (missing)

Return Result

Found repeated and missing numbers

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int** grid, int n, int* returnSize) {
    *returnSize = 2;
    int* result = (int*)malloc(2 * sizeof(int));
    int* freq = (int*)calloc(n * n + 1, sizeof(int));
    
    // Count frequency of each number in grid
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            freq[grid[i][j]]++;
        }
    }
    
    int repeated = 0, missing = 0;
    
    // Find repeated and missing numbers
    for (int num = 1; num <= n * n; num++) {
        if (freq[num] == 2) {
            repeated = num;
        } else if (freq[num] == 0) {
            missing = num;
        }
    }
    
    result[0] = repeated;
    result[1] = missing;
    free(freq);
    return result;
}

int main() {
    int grid[4][4] = {{1,3},{2,2}};
    int* gridPtrs[2] = {grid[0], grid[1]};
    int n = 2;
    
    int returnSize;
    int* result = solution(gridPtrs, n, &returnSize);
    printf("[%d,%d]\n", result[0], result[1]);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

One pass through n² grid elements plus one pass through numbers 1 to n²

⚠ Quadratic Growth

Space Complexity

O(n²)

Hash map stores up to n² key-value pairs

⚠ Quadratic Space

33.2K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map - Count Frequencies — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler