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 II

Number: 3542

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an m x n chessboard (represented as a 2D array “board”) where board[i][j] is an integer value, place exactly three rooks so that no two rooks attack each other (i.e. no two are in the same row or same column). Return the maximum sum of the board cell values at the positions where you place the rooks.

For example, in the board: [[-3,1,1,1], [-3,1,-3,1], [-3,2,1,1]] one optimal placement is rooks at (0,2), (1,3), and (2,1) which gives a total sum = 1 + 1 + 2 = 4.

Key Insights

  • Because rooks attack along rows and columns, any two chosen cells must be in distinct rows and distinct columns.
  • Placing only 3 rooks (a constant) means that even a search or recursive/backtracking approach – if pruned well – can be viable.
  • One can transform the problem into “pick three cells from the board with all different row and column indices” and maximize the sum.
  • Although a brute‐force over all board cells would be too slow in the worst case, the constant k (k = 3) suggests that techniques such as backtracking with sorting (and branch–bound pruning) or a maximum weight matching (assignment) formulation may be applied.
  • The solution uses a recursion over a sorted list of all cells (by descending value) so that once a high‐sum candidate is found, many branches can be pruned by a simple upper bound.

Space and Time Complexity

Time Complexity: O(mn * Depth) in the average case due to early pruning, though worst‐case (e.g. with many equal values) could be higher.
Space Complexity: O(mn) for storing the sorted list of cells plus recursion stack which is O(3) = O(1).

Solution

We solve the problem by first “flattening” the board into a list of entries [value, row, col] and then sorting this list in descending order by value. Because three rooks only are to be placed, we do a depth–first search (DFS) (or backtracking) that attempts to choose cells one by one. At each recursive call, we maintain: • the current sum
• the count of cells selected so far
• sets for the rows and columns already used
• the “starting” index in the sorted list to ensure we do not revisit earlier cells

In addition, we compute an upper–bound at every stage by assuming that, if we still need to pick (3 – current_count) cells, we could “ideally” add that many copies of the maximum cell value (from the beginning of our sorted list). If even the best possible additional sum does not overcome the best solution already found, we prune that branch without further recursion.

This approach leverages the fact that k = 3 is small so that the recursion depth is at most 3. Although in the worst–case (for example, when many cells have the same value) the algorithm might “touch” many cells, the early pruning (once a high sum is reached) helps to reduce the average work.

The algorithm uses: • A list to store and sort all board entries. • Recursion (backtracking) to try candidate cells. • Two sets (or arrays of booleans) to record which rows and columns are already occupied. • A branch–bound technique based on the maximum possible additional value from remaining candidates.

Note that other methods exist (for example, reducing the problem to a maximum–weight matching in a bipartite graph with 3 edges or dynamic programming over rows/columns) but the backtracking approach is straightforward when k is constant.

Code Solutions

# Python solution with detailed comments
def maximumRookSum(board):
    m = len(board)
    n = len(board[0])
    # Build list of (value, row, col) for all board positions
    cells = []
    for i in range(m):
        for j in range(n):
            cells.append((board[i][j], i, j))
    # Sort in descending order by cell value
    cells.sort(key=lambda x: x[0], reverse=True)
    
    # Global variable for best sum found
    best = float('-inf')
    total_cells = len(cells)
    # Global maximum cell value is cells[0][0] (if board not empty)
    max_val = cells[0][0] if cells else 0

    # Backtracking function: idx is current index in cells list;
    # count is number of rooks placed so far; curr_sum is current sum;
    # used_rows and used_cols (set) store rows and columns already used.
    def dfs(idx, count, curr_sum, used_rows, used_cols):
        nonlocal best
        # If we have placed 3 rooks, update best sum
        if count == 3:
            if curr_sum > best:
                best = curr_sum
            return
        # Upper bound: assume we can add (3 - count) cells each having max_val.
        if curr_sum + (3 - count) * max_val <= best:
            return
        # Iterate through remaining cells starting from index idx
        for i in range(idx, total_cells):
            value, row, col = cells[i]
            # Check if the cell is available (its row and col not used already)
            if row in used_rows or col in used_cols:
                continue
            # Choose the current cell and mark its row and col as used.
            used_rows.add(row)
            used_cols.add(col)
            dfs(i + 1, count + 1, curr_sum + value, used_rows, used_cols)
            # Backtrack: remove the cell's row and col from used sets.
            used_rows.remove(row)
            used_cols.remove(col)
    dfs(0, 0, 0, set(), set())
    return best

# Example usage:
if __name__ == "__main__":
    board1 = [[-3,1,1,1],
              [-3,1,-3,1],
              [-3,2,1,1]]
    print("Output:", maximumRookSum(board1))  # Expected Output: 4
← Back to All Questions