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 I

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 be placed in distinct rows and columns to avoid attacks.
  • The maximum sum can be achieved by iterating over all combinations of three rows and three columns.
  • The problem can be reduced to calculating the maximum possible sum for selected rows and columns.

Space and Time Complexity

Time Complexity: O(m^3 * n^3) - iterating through combinations of rows and columns. Space Complexity: O(1) - no additional data structures used beyond a few variables.

Solution

To solve the problem, we will use a brute-force approach that iterates through all combinations of three distinct rows and three distinct columns. For each combination, we will calculate the sum of the cell values at the intersections of these rows and columns, keeping track of the maximum sum encountered.

  1. Loop through all combinations of three rows (i1, i2, i3).
  2. Loop through all combinations of three columns (j1, j2, j3).
  3. For each combination, calculate the sum of the values at (i1, j1), (i2, j2), and (i3, j3).
  4. Update the maximum sum accordingly.

This approach ensures that we consider all valid placements of the rooks without them attacking each other.

Code Solutions

from itertools import combinations

def maxRookSum(board):
    m, n = len(board), len(board[0])
    max_sum = float('-inf')
    
    for rows in combinations(range(m), 3):
        for cols in combinations(range(n), 3):
            current_sum = board[rows[0]][cols[0]] + board[rows[1]][cols[1]] + board[rows[2]][cols[2]]
            max_sum = max(max_sum, current_sum)
    
    return max_sum
← Back to All Questions