We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

First Completely Painted Row or Column

Difficulty: Medium

Problem Description

You are given a 0-indexed integer array arr, and an m x n integer matrix mat. arr and mat both contain all the integers in the range [1, m * n]. Go through each index i in arr starting from index 0 and paint the cell in mat containing the integer arr[i]. Return the smallest index i at which either a row or a column will be completely painted in mat.

Key Insights

  • The problem requires tracking the painting of cells in a matrix based on the order of elements in an array.
  • A row or column is considered completely painted when all its cells have been painted.
  • Efficiently mapping the locations of the integers in the matrix allows for quick updates and checks.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m + n)

Solution

To solve this problem, we will use the following approach:

  1. Create a mapping of each integer in the matrix mat to its corresponding row and column indices.
  2. Use two arrays (or dictionaries) to count how many integers have been painted in each row and each column.
  3. Iterate through the arr, marking the corresponding position in the matrix as painted and updating the counts for the row and column.
  4. After each paint operation, check if any row or column has been completely painted. If so, return the current index.

Code Solutions

def firstCompleteIndex(arr, mat):
    m, n = len(mat), len(mat[0])
    index_map = {}
    
    # Create a mapping from value to its position in the matrix
    for r in range(m):
        for c in range(n):
            index_map[mat[r][c]] = (r, c)
    
    row_count = [0] * m
    col_count = [0] * n
    
    # Iterate through arr and paint cells
    for i in range(len(arr)):
        r, c = index_map[arr[i]]
        row_count[r] += 1
        col_count[c] += 1
        
        # Check if any row or column is completely painted
        if row_count[r] == n or col_count[c] == m:
            return i
            
    return -1  # Should never reach here as per problem constraints
← Back to All Questions