Maximum Sum of a Matrix Stripe Python Interview Question

We define the Matrix Sum of a matrix as the maximum possible sum of matrix elements such that none of the selected elements share the same row or column.

Given a matrix of integer numbers, return the Matrix Sum.

Example #1

Input: matrix =

Output: 17

Explanation: One possible way of selecting is 3, 6, and 8. You can also select 3, 5, and 9, but the result will still be 17.

Intuition

In an interview, we have two main goals: correctness and efficiency. If we focus solely on correctness, things become more straightforward. For this particular question, we’re going to concentrate on ensuring the solution is correct.

One way to ensure correctness is by following these steps:

1. Generate all possible selections.
2. While generating the selections:
   • No two numbers can be selected from the same row.
   • No two numbers can be selected from the same column.
3. Sum the values from each selection, then compare and return the one with the maximum value.

To ensure both rules are satisfied, let’s think about them separately:

1. We must ensure no two numbers are selected from the same row.
2. We must ensure no two numbers are selected from the same column.

Let’s start with the first rule. Suppose we are working with the 0th row of the matrix. How can we ensure we don’t select more than one number from this row? The key is to move to the next row after making a selection. Essentially, if we’ve selected a number from a given row and want to choose another number, we need to make sure that the next selection comes from the following row.

For the second rule, we iterate through the numbers in the current row and check that no number from the same column has been selected in previous rows. Once a number is selected, we mark its column as visited, ensuring that no other number can be chosen from this column in subsequent rows.

What’s interesting about this approach is that we keep asking the same question at each step: how do we select a number from the matrix while changing some parameters? Each time, we adjust the row for the next selection and mark the columns as visited. This leads to a recursive solution!

To implement this recursively, we need to know two things: which row of the matrix we are currently on, and which columns have already been visited (i.e., the columns from which numbers have been selected). Let’s define a function called to achieve this.

Finally, we will call this function starting at the 0th row of the matrix.

Base Case

If we have no rows left to explore, the recursion stops:

Recursive Case

Let’s say we are currently on the th row. According to our plan, we will iterate through all the numbers in the row (i.e., all columns), and ensure that the column hasn’t been selected before. If a column hasn’t been selected, we mark it as visited to prevent selecting numbers from it in the future. For the next recursive call, we move to the next row, and the selected column will remain marked as visited.

To keep track of visited columns efficiently, we use a set in Python, as checking the existence of an element in a set have $O(1)$ time complexity, unlike lists, which have $O(n)$ time complexity.

The logic looks like this:

Here is the full code:

In the above code, we are using the method of sets. In case you are not familiar with it, the method creates a new copy of the set. This means any changes made to the copied set won't affect the original one.

Now, why do we need to copy the set? When you pass a set (or a list) to a function in Python, the function gets the original set, not a separate version. So, if we make changes to the set inside the function, those changes will apply to the original set, which can cause issues in other parts of the code.

By using , we ensure that each function call has its own version of the set. This way, changes made in one call won't affect the original set or any other recursive calls, helping us avoid unwanted side effects.

Optimized Approach

If you prefer not to copy the set, an alternative is to define the set outside the helper function. After each recursive call, remove the element you added, so only one shared set is used, without one call affecting the others.

Here’s how to do that:

Comparison:

Copying the Set:

• Pros: Clearer separation of state; each recursion branch is independent.
• Cons: Higher memory usage due to multiple copies.

Shared Set:

• Pros: More memory-efficient; uses a single set.
• Cons: Requires careful management to avoid affecting other calls.