Solution

Method 1 – Enumeration of All Valid Placements

Intuition

To maximize the sum, we need to place three rooks on the board such that no two share a row or column. This is equivalent to choosing three distinct rows and three distinct columns, and summing the values at those intersections. Enumerating all such combinations gives the optimal answer.

Approach

For all combinations of three distinct rows and three distinct columns:
- For each permutation of columns, sum the values at (row[i], col[perm[i]]).
- Track the maximum sum found.
Return the maximum sum.

Complexity

⏰ Time complexity: O(m^3 * n^3 * 6) — All combinations of rows and columns, and all permutations (6) for each.
🧺 Space complexity: O(1) — Only variables for tracking maximum sum.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maxValueSum(vector<vector<int>>& board) {\n        int m = board.size(), n = board[0].size(), ans = INT_MIN;\n        vector<int> rows(m), cols(n);\n        iota(rows.begin(), rows.end(), 0);\n        iota(cols.begin(), cols.end(), 0);\n        for (int r1 = 0; r1 < m; ++r1)\n        for (int r2 = r1+1; r2 < m; ++r2)\n        for (int r3 = r2+1; r3 < m; ++r3)\n        for (int c1 = 0; c1 < n; ++c1)\n        for (int c2 = c1+1; c2 < n; ++c2)\n        for (int c3 = c2+1; c3 < n; ++c3) {\n            vector<int> r = {r1, r2, r3}, c = {c1, c2, c3};\n            sort(c.begin(), c.end());\n            do {\n                int sum = 0;\n                for (int i = 0; i < 3; ++i) sum += board[r[i]][c[i]];\n                ans = max(ans, sum);\n            } while (next_permutation(c.begin(), c.end()));\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span>

Related Tags

Continue Practicing