Finding Missing and Repeated Values

Problem Link 🔗

Problem Statement

The problem "Find Missing and Repeated Values" requires us to analyze a n x n grid containing numbers ranging from 1 to n^2. Each number appears exactly once, except for one number that appears twice, while another number is missing from the sequence.

Example

Input:

grid = [[1,3],[2,2]]

Output:

[2,4]

Explanation:

The number 2 is repeated, while 4 is missing. Therefore, the output is [2, 4].

Algorithm

To solve this problem, follow these steps:

1. Iterate through the 2D array and convert it into a 1D array.

2. Iterate through the 1D array and find the occurrences of each element.

3. Iterate through the occurrences array and determine the missing and repeated values.

Approach

To solve this problem efficiently, we break it down into two main steps:

1. Flatten the grid: Since the input is a 2D list, we first convert it into a 1D list for easier processing.

2. Identify the repeated and missing values: We count the occurrences of each number and determine which one appears twice and which one is missing.

Let's now walk through the code implementation step by step.

Code Implementation and Explanation

Step 1: Flatten the Grid

The function get_combined_array() converts a 2D grid into a 1D array.

def get_combined_array(input_arr):
    combined_array = []
    for mainIndex in range(len(input_arr)):
        for subIndex in range(len(input_arr[mainIndex])):
            combined_array.append(input_arr[mainIndex][subIndex])

    return combined_array

Explanation:

• We initialize an empty list combined_array to store the flattened values.

• We iterate over the 2D list using two nested loops:

  • The outer loop iterates through each row.

  • The inner loop iterates through each element in that row.

• Each value is appended to combined_array.

Step 2: Find the Missing and Repeated Values

The function find_missing_and_repeated_values() takes the flattened array as input and identifies the repeated and missing numbers.

def find_missing_and_repeated_values(combined_array):
    n = len(combined_array)
    num_count = {}

    for num in combined_array:
        num_count[num] = num_count.get(num, 0) + 1

    repeated_value = missing_value = 0

    for num in range(1, n + 1):
        if num_count.get(num, 0) == 2:
            repeated_value = num
        elif num not in num_count:
            missing_value = num

    return [repeated_value, missing_value]

Explanation:

• We determine the length of combined_array, which represents n^2.

• We create a dictionary num_count to store the frequency of each number.

• We iterate through combined_array, updating the dictionary with the count of each number.

• Next, we loop through the numbers from 1 to n:

  • If a number appears twice, we assign it to repeated_value.

  • If a number is missing, we assign it to missing_value.

• Finally, we return [repeated_value, missing_value].

Step 3: Running the Code

The if __name__ == "__main__" block initializes the grid and executes the functions.

if __name__ == "__main__":
    grid = [[9,1,7],[8,9,2],[3,4,6]]
    combined_array = get_combined_array(grid)
    result = find_missing_and_repeated_values(combined_array)
    print(f"Final result: {result}")

Explanation:

• We define a sample 2D grid.

• We call get_combined_array(grid) to flatten the 2D list into a 1D list.

• We call find_missing_and_repeated_values(combined_array) to identify the missing and repeated numbers.

• The result is printed to the console.

Complexity Analysis

Time Complexity

• Flattening the 2D array takes O(n^2).

• Counting occurrences takes O(n^2).

• Checking for missing/repeated values takes O(n^2).

Thus, the overall time complexity is O(n^2).

Space Complexity

• combined_array stores all n^2 elements → O(n^2).

• num_count dictionary stores at most n^2 elements → O(n^2).

• Other variables take constant space → O(1).

Thus, the overall space complexity is O(n^2).

Topics Covered in This Solution

1. 2D Array Manipulation: Converting a grid into a 1D list.

2. Hashing (Dictionary in Python): Counting occurrences of elements efficiently.

3. Iterative Approach: Using loops to process elements systematically.

This approach is simple and easy to understand, making it suitable for beginners solving similar problems involving missing and repeated numbers.

Thank You!

Thank you for reading!
I hope you enjoyed this post. If you did, please share it with your network and stay tuned for more insights on software development. I'd love to connect with you on LinkedIn or have you follow my journey on HashNode for regular updates.

Happy Coding!
Darshit Anjaria