First Completely Painted Row or Column

class Solution {
public:
    int findFirstFullIndex(vector<int>& nums, vector<vector<int>>& grid) {
        unordered_map<int, int> valueToPosition;
        for (int idx = 0; idx < nums.size(); idx++) {
            valueToPosition[nums[idx]] = idx;
        }

        int minIndex = INT_MAX;
        int rowCount = grid.size();
        int colCount = grid[0].size();

        for (int r = 0; r < rowCount; r++) {
            int maxIndexInRow = INT_MIN;
            for (int c = 0; c < colCount; c++) {
                int mappedIndex = valueToPosition[grid[r][c]];
                maxIndexInRow = max(maxIndexInRow, mappedIndex);
            }
            minIndex = min(minIndex, maxIndexInRow);
        }

        for (int c = 0; c < colCount; c++) {
            int maxIndexInCol = INT_MIN;
            for (int r = 0; r < rowCount; r++) {
                int mappedIndex = valueToPosition[grid[r][c]];
                maxIndexInCol = max(maxIndexInCol, mappedIndex);
            }
            minIndex = min(minIndex, maxIndexInCol);
        }

        return minIndex;
    }
};

The provided C++ solution effectively finds the first completely painted row or column in a given grid, using a provided mapping list nums. This approach ensures that the solution is able to determine which row or column is painted first based on a predefined order.

Here's a concise explanation of how the solution operates:

• Initializes a dictionary valueToPosition to keep track of the position each value from nums corresponds to, utilizing their index.
• Initializes minIndex to INT_MAX to find the minimum index of fully painted rows or columns.
• Iterates through each row to find the maximum index in the row based on the values from nums.
• Updates minIndex to be the minimum between the previous minIndex and the maximum index found in the current row.
• Similarly, iterates through each column to find the maximum index in the column using the same mapping, and updates minIndex accordingly.
• Returns minIndex, which corresponds to the smallest index of fully painted rows or columns as per the mapping defined by nums.

This method provides an efficient way to evaluate a grid by leveraging space for mapping and time for iterating over the grid rows and columns only once each.

class Solution {

    public int completeIndex(int[] array, int[][] matrix) {
        // Store mapping of elements to their indices from array
        Map<Integer, Integer> elementIndexMap = new HashMap<>();
        for (int idx = 0; idx < array.length; idx++) {
            elementIndexMap.put(array[idx], idx);
        }

        int minIndex = Integer.MAX_VALUE;
        int maxRows = matrix.length;
        int maxCols = matrix[0].length;

        // Determine earliest row index with all elements present
        for (int r = 0; r < maxRows; r++) {
            int highestIdxInRow = Integer.MIN_VALUE;
            for (int c = 0; c < maxCols; c++) {
                int currentIdx = elementIndexMap.get(matrix[r][c]);
                highestIdxInRow = Math.max(highestIdxInRow, currentIdx);
            }
            minIndex = Math.min(minIndex, highestIdxInRow);
        }

        // Determine earliest column index with all elements present
        for (int c = 0; c < maxCols; c++) {
            int highestIdxInCol = Integer.MIN_VALUE;
            for (int r = 0; r < maxRows; r++) {
                int currentIdx = elementIndexMap.get(matrix[r][c]);
                highestIdxInCol = Math.max(highestIdxInCol, currentIdx);
            }
            minIndex = Math.min(minIndex, highestIdxInCol);
        }

        return minIndex;
    }
}

The provided Java program, Solution, includes a method completeIndex that identifies the earliest index in an array where all elements are completely present in any row or column of a matrix. The method uses a mapping strategy combined with iteration over matrix rows and columns to accomplish this.

• The completeIndex method starts by creating a HashMap (elementIndexMap) which maps each element in the given array to its index. This facilitates quick lookup of positions while scanning the matrix.

• Next, the function initializes minIndex with Integer.MAX_VALUE to keep track of the smallest index where a row or column is completely painted or filled.

• The method uses two nested loops to process each row of the matrix. In the inner loop for each row, it determines the maximum index of elements as present in the elementIndexMap. The minimum index among all rows is updated in minIndex.

• Similarly, another set of nested loops calculates the earliest completely painted column, updating minIndex in case a smaller index is found.

• After processing both rows and columns, the completeIndex method returns minIndex. If minIndex remains Integer.MAX_VALUE, it indicates that no row or column is fully covered by the elements of the array.

This approach ensures an efficient algorithm to find the first completely painted row or column by leveraging direct access data structures and iterative comparison.

class Solution:
    def completePaintIndex(self, sequence, grid):
        index_map = {}
        for index in range(len(sequence)):
            index_map[sequence[index]] = index

        earliest_full = float("inf")
        total_rows, total_cols = len(grid), len(grid[0])

        for r in range(total_rows):
            max_index_in_row = float("-inf")
            for c in range(total_cols):
                current_index = index_map[grid[r][c]]
                max_index_in_row = max(max_index_in_row, current_index)

            earliest_full = min(earliest_full, max_index_in_row)

        for c in range(total_cols):
            max_index_in_col = float("-inf")
            for r in range(total_rows):
                current_index = index_map[grid[r][c]]
                max_index_in_col = max(max_index_in_col, current_index)

            earliest_full = min(earliest_full, max_index_in_col)

        return earliest_full

This Python solution determines the first row or column in a grid that is completely painted based on a sequence of painting actions. The implemented approach efficiently finds out which row or column is fully painted first, using the following strategy:

• Establish a mapping from grid values (colors or identifiers) to their respective indices in the sequence array. This mapping indicates the order in which each color appears.
• Using two separate loops, compute the max sequence index for each row and column. Track the maximum sequence index encountered in each row and each column to identify the last paint action affecting it.
• Determine the minimum value from these maximum sequence indices to find the earliest painted row or column.
• The result will be the earliest sequence index at which a row or column is fully painted.

This involves iterating over each row and column, which ensures that all scenarios are checked. The solution efficiently compares sequence indices to determine the earliest point a row or column becomes fully painted, optimizing the process by focusing on the most essential calculations and comparisons.