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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

First Completely Painted Row or Column

Number: 2685

Difficulty: Medium

Paid? No

Companies: Google, Bloomberg, Citadel

Problem Description

Given an m x n matrix (mat) that contains all integers from 1 to mn (with unique entries) and an array (arr) of length mn representing a painting order, we need to paint cells in the matrix in the order given by arr. The task is to determine the smallest index i at which an entire row or column in the matrix becomes completely painted.

Key Insights

  • Preprocess the matrix to create a mapping from cell values to their (row, col) positions.
  • Maintain counters for each row and each column to track the number of painted cells.
  • As you process each element in arr, update the corresponding row and column counters.
  • Check if a row counter equals the number of columns or if a column counter equals the number of rows. If so, return the current index.
  • The algorithm performs a single pass over arr and constant-time operations for each step.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n) for the mapping plus O(m + n) for the counters

Solution

Create a mapping from each matrix value to its coordinates using a dictionary or hash map. Initialize two arrays (or hash maps) to store the count of painted cells in each row and column. Iterate through the array arr:

  • For each value, retrieve its (row, col) position from the mapping.
  • Increase the corresponding row and column counters.
  • Check if the count equals the total number of columns (for the row) or the total number of rows (for the column). If true, return the current index as the answer.

This approach efficiently simulates the painting process while tracking the condition required to complete a row or a column.

Code Solutions

# Python solution
def firstCompleteIndex(arr, mat):
    # Dimensions of matrix
    m, n = len(mat), len(mat[0])
    
    # Build a mapping from value to its (row, col) position
    mapping = {}
    for r in range(m):
        for c in range(n):
            mapping[mat[r][c]] = (r, c)
    
    # Arrays to track painted counts in rows and columns
    rowCount = [0] * m
    colCount = [0] * n
    
    # Process each number in arr
    for index, value in enumerate(arr):
        r, c = mapping[value]
        rowCount[r] += 1  # Increment count for this row
        colCount[c] += 1  # Increment count for this column
        
        # If entire row or column is painted, return current index
        if rowCount[r] == n or colCount[c] == m:
            return index

    return -1  # This line should never be reached based on constraints

# Example usage:
# arr = [1,3,4,2]
# mat = [[1,4],[2,3]]
# print(firstCompleteIndex(arr, mat))  # Output should be 2
← Back to All Questions