First Completely Painted Row or Column - Practice Coding Problems

First Completely Painted Row or Column - Problem

You are given a 0-indexed integer array arr, and an m x n integer matrix mat. Both arr and mat 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.

Input & Output

Example 1 — Basic Case

$ Input: arr = [1,3,4,2], mat = [[1,4],[2,3]]

› Output: 2

💡 Note: Paint cells in order: (0,0)→1, (1,1)→3, (0,1)→4. After painting 4, row 0 is complete: [1,4]. Return index 2.

Example 2 — Column Completion

$ Input: arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]

› Output: 3

💡 Note: Paint: (0,1)→2, (2,0)→8, (2,1)→7, (1,1)→4. After painting 4, column 1 is complete: [2,4,7]. Return index 3.

Example 3 — Single Row

$ Input: arr = [5,1,3], mat = [[1,3,5]]

› Output: 2

💡 Note: Paint: (0,2)→5, (0,0)→1, (0,1)→3. After painting 3, the entire row is complete. Return index 2.

Constraints

m == mat.length
n == mat[i].length
arr.length == m * n
1 ≤ m, n ≤ 10⁵
1 ≤ m * n ≤ 10⁵
1 ≤ arr[i], mat[r][c] ≤ m * n
All the integers of arr are unique
All the integers of mat are unique

Visualization

Tap to expand

Understanding the Visualization

Input

Array sequence [1,3,4,2] and matrix [[1,4],[2,3]]

Process

Paint cells following array order until row/column complete

Output

Return index 2 when first complete row/column found

Key Takeaway

🎯 Key Insight: Use counters to track painting progress instead of checking completion from scratch

Asked in

G Google 12 a Amazon 8 M Microsoft 6

The key insight is to use counters to track painted cells per row and column instead of checking completion from scratch each time. The optimal approach maintains row_count and col_count arrays, incrementing them as we paint cells. When any counter equals the row/column size, we've found our answer. Time: O(m×n), Space: O(m×n).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Counters	O(m × n)	O(m × n)	Use counters to track painted cells per row/column, avoiding full scans
Brute Force	O(m × n × (m + n))	O(m × n)	Paint each cell and check all rows/columns for completion after each paint

Optimized with Counters — Algorithm Steps

Step 1: Create position map for quick value-to-coordinate lookup
Step 2: Initialize counters for each row and column
Step 3: For each painted cell, increment its row and column counters
Step 4: Check if counter equals row/column size for instant completion detection

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup Counters

Create arrays to count painted cells per row/column

Paint & Update

Find position, increment row and column counters

Check Counters

Compare counter to row/column size for instant completion

Early Return

Return immediately when counter equals size

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* arr, int arrSize, int** mat, int matSize, int* matColSize) {
    int m = matSize, n = matColSize[0];
    
    // Create position map
    int* posR = (int*)malloc((m * n + 1) * sizeof(int));
    int* posC = (int*)malloc((m * n + 1) * sizeof(int));
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            posR[mat[i][j]] = i;
            posC[mat[i][j]] = j;
        }
    }
    
    // Counters for painted cells in each row and column
    int* rowCount = (int*)calloc(m, sizeof(int));
    int* colCount = (int*)calloc(n, sizeof(int));
    
    for (int idx = 0; idx < arrSize; idx++) {
        // Get position and update counters
        int r = posR[arr[idx]];
        int c = posC[arr[idx]];
        rowCount[r]++;
        colCount[c]++;
        
        // Check if row or column is complete
        if (rowCount[r] == n || colCount[c] == m) {
            free(posR); free(posC);
            free(rowCount); free(colCount);
            return idx;
        }
    }
    
    free(posR); free(posC);
    free(rowCount); free(colCount);
    return arrSize - 1;
}

int main() {
    int arr[] = {1,3,4,2};
    int arrSize = 4;
    
    int row1[] = {1,4};
    int row2[] = {2,3};
    int* mat[] = {row1, row2};
    int matSize = 2;
    int matColSize[] = {2, 2};
    
    printf("%d\n", solution(arr, arrSize, mat, matSize, matColSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n)

Single pass through arr with O(1) position lookup and counter updates

✓ Linear Growth

Space Complexity

O(m × n)

Position map plus arrays for row and column counters

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~15 min Avg. Time

945 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with Counters — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler