We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Value Sum by Placing Three Rooks II

Difficulty: Hard

Problem Description

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.

Key Insights

  • Rooks can only be placed in different rows and columns to avoid attacking each other.
  • The problem involves selecting the best combination of cells, which can be thought of as a combinatorial selection problem.
  • A brute-force approach would involve checking all combinations of three positions, which is inefficient for large boards.
  • Efficiently calculating the maximum sum requires considering the values of rows and columns in a structured manner.

Space and Time Complexity

Time Complexity: O(m^2 * n^2), where m is the number of rows and n is the number of columns. This is due to the combinations of selecting three distinct rows and columns. Space Complexity: O(1), as we are using a constant amount of space for variables.

Solution

To solve the problem, we can use a combination of nested loops to iterate over all possible combinations of three distinct rows and three distinct columns. The algorithm works as follows:

  1. Iterate through all combinations of three different rows.
  2. For each combination of rows, iterate through all combinations of three different columns.
  3. Calculate the sum of the values at the selected cell positions (i.e., board[row1][col1], board[row2][col2], board[row3][col3]).
  4. Keep track of the maximum sum encountered during the iterations.

This approach ensures that we only consider valid placements of rooks while maximizing the sum of the values.

Code Solutions

from itertools import combinations

def maxRookSum(board):
    m, n = len(board), len(board[0])
    max_sum = float('-inf')
    
    # Iterate over all combinations of 3 distinct rows
    for rows in combinations(range(m), 3):
        # Iterate over all combinations of 3 distinct columns
        for cols in combinations(range(n), 3):
            current_sum = sum(board[rows[i]][cols[i]] for i in range(3))
            max_sum = max(max_sum, current_sum)
    
    return max_sum
← Back to All Questions