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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Value Sum by Placing Three Rooks I

Number: 3550

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an m x n chessboard (represented as a 2D array) where each cell has a value, we want to place exactly three rooks such that no two rooks are in the same row or the same column. The goal is to maximize the sum of the values at the placed rooks’ positions.

Key Insights

  • Since rooks attack along rows and columns, any two rooks must be placed in distinct rows and distinct columns.
  • With only three rooks to place, although m and n can be as large as 100, we only “use up” three rows and three columns.
  • A dynamic programming (DP) or recursion with memoization approach can iterate row‐by‐row and make a decision in each row: either skip the row or place one rook in an as‐yet unused column.
  • The state can be defined by the current row index, the count of rooks placed so far, and the set (or sorted tuple) of columns already used.
  • The small constant “three” lets us avoid the exponential explosion one might have for a general “rook placement” problem.

Space and Time Complexity

Time Complexity: O(m * (n choose 0 + n choose 1 + n choose 2 + n choose 3)) ≈ O(m * n³)
Space Complexity: O(m * (number of states)) where the number of states is bounded by O((n choose ≤3)) due to the small count of placed rooks.

Solution

We solve the problem using a recursive DP (depth-first search) with memoization. At each row, we consider two options:

  1. Do not place a rook in the current row.
  2. Place a rook in the current row in any column that is not already used.

The state is defined by:

  • The current row index.
  • The number of rooks placed so far.
  • The set of columns that have been used (kept in sorted order or as a bit-mask).

When three rooks have been placed, the recursion stops and returns 0 (as no additional value can be added). If all rows are processed and fewer than three rooks have been placed, we return a very small number (representing an impossible state). The optimal answer is the maximum sum computed by taking the best option at each step.

The key “gotcha” is to properly memoize on the state, including which columns have been used, because the same row index with a different set of used columns will yield different possibilities.

This solution is implemented below in multiple languages with detailed line-by-line comments.

Code Solutions

# Python solution using recursion with memoization

from functools import lru_cache
import math

def maxRookSum(board):
    m = len(board)
    n = len(board[0])
    
    # Use -inf to represent an impossible scenario when not enough rooks are placed.
    NEG_INF = -10**18

    # Recursive function: row index, count rooks used, used_columns is a tuple of column indices (sorted)
    @lru_cache(maxsize=None)
    def dfs(row, count, used_columns):
        # If 3 rooks have been placed, no more value is added.
        if count == 3:
            return 0
        # If no more rows are available but we haven't placed 3 rooks, state is invalid.
        if row == m:
            return NEG_INF
        
        # Option 1: Skip current row.
        best = dfs(row + 1, count, used_columns)
        
        # Option 2: Try placing a rook in any column that is not already used.
        used = set(used_columns)
        for col in range(n):
            if col in used:
                continue  # cannot place rook in an already used column
            # Add the current column to used columns (and keep tuple sorted for consistency).
            new_used = tuple(sorted(used | {col}))
            current_value = board[row][col]
            candidate = current_value + dfs(row + 1, count + 1, new_used)
            best = max(best, candidate)
        return best
    
    return dfs(0, 0, ())

# Example usage:
# board = [[-3,1,1,1],[-3,1,-3,1],[-3,2,1,1]]
# print(maxRookSum(board))  # Expected output: 4
← Back to All Questions