🚀 Optimized Bingo Solver: Fast Tracking Rows & Columns with Flattened Positions 🎯
IntuitionThe problem can be visualized as playing bingo, where we eliminate numbers from the matrix one by one. After each elimination, we need to check whether
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem can be visualized as playing bingo, where we eliminate numbers from the matrix one by one. After each elimination, we need to check whether a complete row or column has been marked. Instead of repeatedly checking the entire row and column after every elimination (brute force), we can optimize the process by maintaining a count of marked cells for each row and column. Whenever the count for any row or column matches its respective length, we can immediately return the index.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Preprocess the Matrix: Use a HashMap to store the positions of each value in the matrix. This allows O(1) lookup for the position of any value in arr.
2. Track Row and Column Counts: Maintain a freq array where:
    - freq[i][0] tracks the number of marked cells in the i-th row.
    - freq[j][1] tracks the number of marked cells in the j-th column.
3. Iterate Through the Input Array:
    - For each value in arr, find its position in the matrix using the preprocessed HashMap.
    - Update the counts for the corresponding row and column in the freq array.
    - Check if the count for any row or column matches its respective length (n for rows and m for columns). If so, return the index of the current value in arr.
4. Return Result: If no row or column is completely marked after processing all elements, return −1.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
    O(m*n)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
    O(m*n)

# Code
```java []
class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int m = mat.length; // Number of rows in the matrix
        int n = mat[0].length; // Number of columns in the matrix

        // Initialize a frequency array to track the count of marked cells for rows and columns.
        int[][] freq = new int[Math.max(m, n)][2];

        // Create a HashMap to store the positions of each value in the matrix.
        HashMap<Integer, int[]> map = new HashMap<>();

        // Populate the HashMap with the positions of values in the matrix.
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                map.put(mat[i][j], new int[]{i, j});
            }
        }

        // Iterate over the elements of the input array `arr`.
        for (int i = 0; i < arr.length; i++) {
            // Get the position of the current element in the matrix using the HashMap.
            int[] pos = map.get(arr[i]);
            int x = pos[0]; // Row index of the element in the matrix
            int y = pos[1]; // Column index of the element in the matrix

            // Increment the count for the corresponding row and column.
            freq[x][0]++; // Increment count for the row
            freq[y][1]++; // Increment count for the column

            // Check if the current row or column is completely marked.
            if (freq[x][0] == n || freq[y][1] == m) {
                return i; // Return the index of the current element in `arr`.
            }
        }

        // If no row or column is completely marked, return -1.
        return -1;
    }
}
```
---
---
# Further Optimization
To optimize the solution further, we can eliminate the need for a 2D frequency array (freq) by using two 1D arrays to directly track the counts of rows and columns. Additionally, instead of storing a HashMap with full matrix coordinates, we can preprocess the matrix into a flattened 1D array. This eliminates the overhead of storing the entire mapping and allows faster lookups by directly indexing into the flattened array.

# Optimized Approach
1. Flatten the Matrix:
    We can flatten the mat into a 1D array flatPos such that the value at flatPos[val] gives the row and column indices of the value val.

    For a value val in mat[i][j], store flatPos[val] = i * n + j.
    - This allows us to calculate the row index as row = flatPos[val] / n and the column index as col = flatPos[val] % n.
2. Use Separate Count Arrays for Rows and Columns:
    Instead of maintaining a 2D array for counts, use two 1D arrays:
    - rowCount of size m to track the number of marked cells in each row.
    - colCount of size n to track the number of marked cells in each column.
3. Process the Array arr in Order:
    - For each value in arr, compute its row and column indices from flatPos. 
    - Update the respective counts in rowCount and colCount. 
    - Check if any count reaches the required size (n for rows, m for columns), and return the index if it does.

4. Early Exit:
    - As soon as a row or column is completely marked, exit early without processing further elements.


---
# Optimized Code
```java []
class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int m = mat.length; // Number of rows
        int n = mat[0].length; // Number of columns
        int totalCells = m * n;

        // Step 1: Flatten the matrix into a position array
        int[] flatPos = new int[totalCells + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                flatPos[mat[i][j]] = i * n + j; // Store flattened position
            }
        }

        // Step 2: Initialize row and column count arrays
        int[] rowCount = new int[m];
        int[] colCount = new int[n];

        // Step 3: Process each number in the array
        for (int i = 0; i < arr.length; i++) {
            int pos = flatPos[arr[i]];
            int row = pos / n; // Extract row index
            int col = pos % n; // Extract column index

            // Increment the counts for the row and column
            rowCount[row]++;
            colCount[col]++;

            // Check if any row or column is completely marked
            if (rowCount[row] == n || colCount[col] == m) {
                return i; // Return the index
            }
        }

        // If no row or column is completely marked, return -1
        return -1;
    }
}

```
---

![Leetcode upvote bheek.jpeg](https://assets.leetcode.com/users/images/0eaa1272-e714-4e1f-91b7-2996c7d2a6b7_1737357345.9658515.jpeg)

['Array', 'Hash Table', 'Java']