Problem of The Day: First Completely Painted Row or Column

Problem Statement

Intuition

The problem requires finding the first complete row or column after processing elements in the array arr. My initial thought was to keep track of the frequency of elements in rows and columns as they appear in arr and determine the point at which any row or column becomes “complete” (all elements in that row/column are present in arr).

Approach

1. Initialization:

   • Identify the number of rows (ROWS) and columns (COLS) in the matrix mat.
   • Create two frequency arrays, row_freq and col_freq, to track how many elements have been processed for each row and column.
   • Use a dictionary pos to map each value in mat to its coordinates (row, col).

2. Mapping Values:

   • Traverse the matrix mat and populate the pos dictionary with the positions of each value.

3. Processing Array:

   • Iterate through the array arr.
   • For each value in arr, retrieve its position (row, col) using the pos dictionary.
   • Increment the corresponding row and column frequencies in row_freq and col_freq.
   • Check if the updated frequency for the row or column equals the number of elements in that row/column:
     • If so, return the current index i as it represents the first complete row or column.

Complexity

• Time Complexity:

  • Preprocessing the matrix to populate pos takes \(O(ROWS \times COLS)\).
  • Iterating through the array arr takes \(O(n)\), where n is the length of arr.
  • Overall, the complexity is \(O(ROWS \times COLS + n)\).

• Space Complexity:

  • Storing the pos dictionary requires \(O(ROWS \times COLS)\).
  • Frequency arrays row_freq and col_freq require \(O(ROWS + COLS)\).
  • Overall, the complexity is \(O(ROWS \times COLS)\).

Code

class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        ROWS = len(mat)
        COLS = len(mat[0])
        row_freq = [0] * ROWS
        col_freq = [0] * COLS
        pos = defaultdict(list)

        for row in range(ROWS):
            for col in range(COLS):
                val = mat[row][col]
                pos[val] = [row, col]

        for i, x in enumerate(arr):
            row, col = pos[x]
            row_freq[row] += 1
            col_freq[col] += 1
            if row_freq[row] == COLS or col_freq[col] == ROWS:
                return i

Editorial

Approach 2: Brute Force Optimized with Counting

class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        num_rows, num_cols = len(mat), len(mat[0])
        row_count, col_count = [0] * num_rows, [0] * num_cols
        num_to_pos = {}

        # Create a map to store the position of each number in the matrix
        for row in range(num_rows):
            for col in range(num_cols):
                num_to_pos[mat[row][col]] = [row, col]

        for i in range(len(arr)):
            num = arr[i]
            row, col = num_to_pos[num]

            # Increment the count for the corresponding row and column
            row_count[row] += 1
            col_count[col] += 1

            # Check if the row or column is completely painted
            if row_count[row] == num_cols or col_count[col] == num_rows:
                return i

        # This line will never be reached as per the problem statement
        return -1

Approach 3: Reverse Mapping

class Solution:
    def firstCompleteIndex(self, arr, mat):
        # Map to store the index of each number in the arr
        num_to_index = {}
        for i in range(len(arr)):
            num_to_index[arr[i]] = i

        result = float("inf")
        num_rows, num_cols = len(mat), len(mat[0])

        # Check for the earliest row to be completely painted
        for row in range(num_rows):
            # Tracks the greatest index in this row
            last_element_index = float("-inf")
            for col in range(num_cols):
                index_val = num_to_index[mat[row][col]]
                last_element_index = max(last_element_index, index_val)

            # Update result with the minimum index where this row is fully painted
            result = min(result, last_element_index)

        # Check for the earliest column to be completely painted
        for col in range(num_cols):
            last_element_index = float("-inf")
            for row in range(num_rows):
                index_val = num_to_index[mat[row][col]]
                last_element_index = max(last_element_index, index_val)

            # Update result with the minimum index where this column is fully painted
            result = min(result, last_element_index)

        return result