2661: First-Completely-Painted-Row-or-Column
Medium 2025-01-20

This question is quite straightforward and does not involve any funny business.

In my algorithm, I started off by iterating through the matrix mat and creating a hashmap mp that maps each integer in the range [1, m * n] to their respective positions in the matrix. This is possible as each integer present in arr and mat are unique, making a bijective hashmap mp possible (and necessary, as the integer’s position in arr and mat is random).

Then, keep an array of integers counts and iterate through arr, incrementing the count of values painted in each respective row and column, until the count of values painted in a row or column is equal to n or m respectively.

code

class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        unordered_map<int, pair<int, int>> mp;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                mp[mat[i][j]] = {i, j};
            }
        }
        vector<int> counts (m+n, 0);
        for (int i = 0; i < arr.size(); ++i) {
            int row = mp[arr[i]].first;
            int col = mp[arr[i]].second;
            ++counts[row];
            ++counts[m+col];
            if (counts[row] == n or counts[m+col] == m) {
                return i;
            }
        }

        return 0;
    }
};

complexity