C++ || don't use a hash map when a vector or an array does the trick
TODO(heder): Insert cute cat meme to ask for up-votes. ;)\n\n# Approach 1: vector (186ms)\n\nSeveral solutions are using an std::unordered_map for building an i
**TODO(heder): Insert cute cat meme to ask for up-votes. ;)**\n\n# Approach 1: vector (186ms)\n\nSeveral solutions are using an ```std::unordered_map``` for building an index, which is a waste as we know that the elements in ```mat``` are within $$[1, n * m]$$, hence we can just directly index into a ```std::vector```.\n\n```cpp\n    static int firstCompleteIndex(const vector<int>& arr, const vector<vector<int>>& mat) {\n        const int rows = size(mat);\n        const int cols = size(mat[0]);\n        \n        // build index for |mat|.\n        vector<pair<int,int>> index(rows * cols + 1);\n        for (int r = 0; r < rows; ++r)\n            for (int c = 0; c < cols; ++c)\n                index[mat[r][c]] = make_pair(r, c);\n        \n        // process |arr|.\n        vector<int> rc(rows);\n        vector<int> cc(cols);\n        for (int i = 0; i < size(arr); ++i) {\n            const auto [r, c] = index[arr[i]];\n            if (++rc[r] == cols) return i;\n            if (++cc[c] == rows) return i;\n        }\n        // unreachable.\n        assert(false);\n        return -1;\n    }\n```\n\n**Complexity Analysis**\nLet $$n$$ and $$m$$ be the dimension of ```mat``` and $$n * m$$ the size of ```arr``` then the \n  * Time complexity is $$O(n * m)$$ as we need to scan ```mat``` and ```arr``` and the\n  * Space complexity is $$O(n * m)$$ for the index we build.\n\n\n# Approach 2: dynamic array on stack (167ms, 100%?)\nAs pointed out @Ajna2, why bother with a vector when an array might be even cheaper. The code is kinda interesting that clang generates for multiple dynamic arrays on the stack: https://godbolt.org/z/h1975ojhj Instead of on the heap the temporary working memory is created on the stack. There is still an indirection happening though.\n\n```cpp\n    static int firstCompleteIndex(const vector<int>& arr, const vector<vector<int>>& mat) {\n        const int rows = size(mat);\n        const int cols = size(mat[0]);\n        \n        // build index for |mat|.\n        pair<int,int> index[rows * cols + 1];\n        for (int r = 0; r < rows; ++r)\n            for (int c = 0; c < cols; ++c)\n                index[mat[r][c]] = make_pair(r, c);\n        \n        // process |arr|.   \n        int rc[rows];\n        fill(rc, rc + rows, 0);\n        int cc[cols];\n        fill(cc, cc + cols, 0);\n        for (int i = 0; i < size(arr); ++i) {\n            const auto [r, c] = index[arr[i]];\n            if (++rc[r] == cols) return i;\n            if (++cc[c] == rows) return i;\n        }\n        // unreachable.\n        assert(false);\n        return -1;\n    }\n```\n\nThe complexity analysis remains the same.\n\n**Pro-Tips**\n\nI always have a header like this in my solutions. This speeds-up I/O:\n\n```cpp\n// https://leetcode.com/problems/first-completely-painted-row-or-column\n// problem: 2661\nstatic int fast_io = []() { std::ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); return 0; }();\n```\n\n_As always: Feedback, questions, and comments are welcome. Leaving an up-vote sparks joy! :)_\n\n**p.s. Join us on the [LeetCode The Hard Way Discord Server](https://discord.gg/hFUyVyWy2E)!**\n
['Array', 'C']