3256. Maximum Value Sum by Placing Three Rooks I LeetCode Solution
In this guide, you will get 3256. Maximum Value Sum by Placing Three Rooks I LeetCode Solution with the best time and space complexity. The solution to Maximum Value Sum by Placing Three Rooks I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Value Sum by Placing Three Rooks I
You are given a m x n 2D array board representing a chessboard, where board[i][j] represents the value of the cell (i, j).
Rooks in the same row or column attack each other. You need to place three rooks on the chessboard such that the rooks do not attack each other.
Return the maximum sum of the cell values on which the rooks are placed.
We can place the rooks in the cells (0, 2), (1, 3), and (2, 1) for a sum of 1 + 1 + 2 = 4.
Example 2:
Input: board = [[1,2,3],[4,5,6],[7,8,9]]
Output: 15
Explanation:
We can place the rooks in the cells (0, 0), (1, 1), and (2, 2) for a sum of 1 + 5 + 9 = 15.
Example 3:
Input: board = [[1,1,1],[1,1,1],[1,1,1]]
Output: 3
Explanation:
We can place the rooks in the cells (0, 2), (1, 1), and (2, 0) for a sum of 1 + 1 + 1 = 3.
3 <= m == board.length <= 100
3 <= n == board[i].length <= 100
-109 <= board[i][j] <= 109
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(m + n)
3256. Maximum Value Sum by Placing Three Rooks I LeetCode Solution in C++
class Solution {
public:
long long maximumValueSum(vector<vector<int>>& board) {
const int m = board.size();
const int n = board[0].size();
long ans = LONG_MIN;
using T = tuple<long, int, int>;
vector<vector<T>> rows(m); // [(val, i, j)]
vector<vector<T>> cols(n); // [(val, i, j)]
set<T> rowSet; // {(val, i, j)}
set<T> colSet; // {(val, i, j)}
set<T> topNine; // {(val, i, j)}
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
rows[i].emplace_back(board[i][j], i, j);
cols[j].emplace_back(board[i][j], i, j);
}
auto getTop3 = [](vector<T>& row) -> vector<T> {
partial_sort(row.begin(),
row.begin() + min(3, static_cast<int>(row.size())),
row.end(), greater<>());
row.resize(min(3, (int)row.size()));
return row;
};
for (vector<T>& row : rows) {
row = getTop3(row);
rowSet.insert(row.begin(), row.end());
}
for (vector<T>& col : cols) {
col = getTop3(col);
colSet.insert(col.begin(), col.end());
}
set_intersection(rowSet.begin(), rowSet.end(), colSet.begin(), colSet.end(),
inserter(topNine, topNine.begin()));
// At least 9 positions are required on the board to place 3 rooks such that
// none can attack another.
if (topNine.size() > 9) {
auto it = topNine.begin();
advance(it, topNine.size() - 9);
topNine.erase(topNine.begin(), it);
}
for (auto it1 = topNine.begin(); it1 != topNine.end(); ++it1)
for (auto it2 = next(it1); it2 != topNine.end(); ++it2)
for (auto it3 = next(it2); it3 != topNine.end(); ++it3) {
const auto [val1, i1, j1] = *it1;
const auto [val2, i2, j2] = *it2;
const auto [val3, i3, j3] = *it3;
if (i1 == i2 || i1 == i3 || i2 == i3 || //
j1 == j2 || j1 == j3 || j2 == j3)
continue;
ans = max(ans, val1 + val2 + val3);
}
return ans;
}
}; /* code provided by PROGIEZ */
3256. Maximum Value Sum by Placing Three Rooks I LeetCode Solution in Java
class Solution {
public long maximumValueSum(int[][] board) {
final int m = board.length;
final int n = board[0].length;
long ans = Long.MIN_VALUE;
List<int[]>[] rows = new ArrayList[m];
List<int[]>[] cols = new ArrayList[n];
Set<int[]> rowSet = new HashSet<>();
Set<int[]> colSet = new HashSet<>();
Set<int[]> boardSet = new HashSet<>();
for (int i = 0; i < m; ++i)
rows[i] = new ArrayList<>();
for (int j = 0; j < n; ++j)
cols[j] = new ArrayList<>();
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
int[] cell = new int[] {board[i][j], i, j};
rows[i].add(cell);
cols[j].add(cell);
}
Comparator<int[]> comparator = (a, b) -> Integer.compare(b[0], a[0]);
for (List<int[]> row : rows) {
row.sort(comparator);
rowSet.addAll(row.subList(0, Math.min(3, row.size())));
}
for (List<int[]> col : cols) {
col.sort(comparator);
colSet.addAll(col.subList(0, Math.min(3, col.size())));
}
boardSet.addAll(rowSet);
boardSet.retainAll(colSet);
// At least 9 positions are required on the board to place 3 rooks such that
// none can attack another.
List<int[]> topNine = new ArrayList<>(boardSet);
topNine.sort(comparator);
topNine = topNine.subList(0, Math.min(9, topNine.size()));
for (int i = 0; i < topNine.size(); ++i)
for (int j = i + 1; j < topNine.size(); ++j)
for (int k = j + 1; k < topNine.size(); ++k) {
int[] t1 = topNine.get(i);
int[] t2 = topNine.get(j);
int[] t3 = topNine.get(k);
if (t1[1] == t2[1] || t1[1] == t3[1] || t2[1] == t3[1] || //
t1[2] == t2[2] || t1[2] == t3[2] || t2[2] == t3[2])
continue;
ans = Math.max(ans, (long) t1[0] + t2[0] + t3[0]);
}
return ans;
}
} // code provided by PROGIEZ
3256. Maximum Value Sum by Placing Three Rooks I LeetCode Solution in Python
class Solution:
def maximumValueSum(self, board: list[list[int]]) -> int:
rows = [heapq.nlargest(3, [(val, i, j)
for j, val in enumerate(row)])
for i, row in enumerate(board)]
cols = [heapq.nlargest(3, [(val, i, j)
for i, val in enumerate(col)])
for j, col in enumerate(zip(*board))]
topNine = heapq.nlargest(9,
set(itertools.chain(*rows)) &
set(itertools.chain(*cols)))
return max(
(val1 + val2 + val3 for
(val1, i1, j1),
(val2, i2, j2),
(val3, i3, j3) in (itertools.combinations(topNine, 3))
if len({i1, i2, i3}) == 3 and len({j1, j2, j3}) == 3)) # code by PROGIEZ
