3033. Modify the Matrix


Problem Description

Given a two-dimensional grid, 'matrix', with m rows and n columns, we are asked to create an identical grid, 'answer'. The task involves identifying elements in 'matrix' with a value of -1 and updating them to the maximum value found in their respective columns. It's important to keep in mind that our grids are 0-indexed, meaning that row and column indices start from 0. The goal is to process 'matrix' and transform it into 'answer' following this rule, ultimately returning 'answer'.

Intuition

The solution revolves around handling the grid column by column. For each column, we look for the highest number (disregarding any -1 values, since we're only interested in positive numbers for replacement). After finding this maximum value, we proceed down the same column, substituting any instance of -1 with the column's maximum value we previously found.

The process can be split into two main steps:

  1. Traverse each column of the matrix to determine the maximum non-negative value present in that column.

  2. Go through the matrix again, this time replacing every -1 with the maximum value found in step 1 for the respective column.

We perform this for every column, and once all substitutions are made, we have our 'answer' matrix ready to be returned. The approach is direct and mimics the exact procedure described in the problem, requiring no additional data structures or complicated logic—simple iteration and replacement suffice to solve this problem.

Solution Approach

The algorithm implemented in the provided solution is straightforward and efficient. It employs a nested loop structure to process the matrix column by column.

Here's the step-by-step breakdown of the algorithm:

  1. Determine the size of the matrix using the 'len' function to find m (number of rows) and n (number of columns).

  2. Use an outer loop to iterate through each column index from 0 to n - 1.

  3. Inside the outer loop, perform a list comprehension to determine the maximum value mx in the current column. This is done by iterating over each row i for the current column j and collecting each element's value, except for -1. The max function then gives the highest value in that column.

    • This is achieved with the expression: max(matrix[i][j] for i in range(m))
  4. After finding the maximum value for the column, we use another inner loop to go through each row for the same column.

  5. Here we check if any element is -1 and replace it with the maximum value mx found earlier.

    • The replacement is done only when the condition if matrix[i][j] == -1: is true.
  6. Once all the columns have been processed, the original matrix is now modified to the answer matrix with all -1s replaced by their respective column maximums.

  7. Lastly, return the modified matrix as the result.

No additional data structures or complex patterns are used in this implementation; it utilizes only basic loops and list comprehension techniques. The space complexity is constant, as we're simply updating the original matrix in place, without using any extra space proportional to the size of the input (beyond the fixed number of variables needed for iteration).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Suppose we have the following grid matrix, consisting of 3 rows and 4 columns:

1matrix = [
2  [0, -1, 3, 4],
3  [3,  2,  1, -1],
4  [-1, 2, -1, 0]
5]

Following the steps of the solution approach:

  1. Determine the size of the matrix. We can see that m is 3 and n is 4.

  2. Start with the first column (j=0). We iterate through each row and find that the maximum value for this column is 3 (ignoring the -1).

  3. Replace all -1 values in this column with the maximum value found. There is one -1 value in the third row, so we get:

    1matrix = [
    2  [0, -1, 3, 4],
    3  [3,  2,  1, -1],
    4  [3,  2, -1, 0]
    5]
  4. Move to the second column (j=1). The maximum value for this column is 2.

  5. Replace -1 values in this column. There is one -1 in the first row, resulting in:

    1matrix = [
    2  [0, 2, 3, 4],
    3  [3, 2, 1, -1],
    4  [3, 2, -1, 0]
    5]
  6. Continue to the third column (j=2). The maximum value, ignoring -1, is 3.

  7. Replace -1 values in the third column. There is one -1 in the third row, leading to:

    1matrix = [
    2  [0, 2, 3, 4],
    3  [3, 2, 1, -1],
    4  [3, 2, 3, 0]
    5]
  8. Finally, proceed to the last column (j=3). The maximum value is 4.

  9. There's one -1 in the second row that needs to be replaced:

    1matrix = [
    2  [0, 2, 3, 4],
    3  [3, 2, 1, 4],
    4  [3, 2, 3, 0]
    5]

After completing these steps, matrix is now transformed into answer by replacing all -1 values with the maximum values in their respective columns. The resulting matrix is:

1answer = [
2  [0, 2, 3, 4],
3  [3, 2, 1, 4],
4  [3, 2, 3, 0]
5]

This matrix is then returned as the final output of the algorithm. The approach ensures that each -1 in the original matrix is replaced by the maximum positive value present in its respective column.

Solution Implementation

1from typing import List
2
3class Solution:
4    def modifiedMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
5        # Get the number of rows (m) and columns (n) in the matrix
6        num_rows, num_columns = len(matrix), len(matrix[0])
7      
8        # Iterate over each column
9        for col in range(num_columns):
10            # Find the maximum value in the current column
11            max_value = max(matrix[row][col] for row in range(num_rows))
12          
13            # Replace all occurrences of -1 with the maximum value in the current column
14            for row in range(num_rows):
15                if matrix[row][col] == -1:
16                    matrix[row][col] = max_value
17      
18        # Return the modified matrix
19        return matrix
20
1class Solution {
2
3    /**
4     * Modifies a given matrix such that every -1 entry in a column is replaced with
5     * the maximum value in that column.
6     *
7     * @param matrix The original matrix that will be modified.
8     * @return The modified matrix.
9     */
10    public int[][] modifiedMatrix(int[][] matrix) {
11        // Get the number of rows m and the number of columns n in the matrix
12        int rowCount = matrix.length;
13        int columnCount = matrix[0].length;
14      
15        // Iterate over columns
16        for (int column = 0; column < columnCount; ++column) {
17            // Initialize the maximum value for the current column, starting with the smallest possible integer value
18            int maxInColumn = Integer.MIN_VALUE;
19            // Find the maximum value in the current column
20            for (int row = 0; row < rowCount; ++row) {
21                maxInColumn = Math.max(maxInColumn, matrix[row][column]);
22            }
23            // Replace all -1 entries in the current column with the maximum value found
24            for (int row = 0; row < rowCount; ++row) {
25                if (matrix[row][column] == -1) {
26                    matrix[row][column] = maxInColumn;
27                }
28            }
29        }
30        // Return the modified matrix
31        return matrix;
32    }
33}
34
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // The function modifiedMatrix takes a 2D vector of integers, representing a matrix,
7    // and modifies it according to certain rules.
8    std::vector<std::vector<int>> modifiedMatrix(std::vector<std::vector<int>>& matrix) {
9        // Get the number of rows and columns in the matrix.
10        int rowCount = matrix.size();
11        int colCount = matrix[0].size();
12      
13        // Iterate over columns
14        for (int col = 0; col < colCount; ++col) {
15            // Initialize 'maxValue' to the smallest possible integer to find the maximum later.
16            int maxValue = std::numeric_limits<int>::min();
17          
18            // Find the maximum value in the current column.
19            for (int row = 0; row < rowCount; ++row) {
20                maxValue = std::max(maxValue, matrix[row][col]);
21            }
22          
23            // Replace all -1s in the current column with the maximum value found.
24            for (int row = 0; row < rowCount; ++row) {
25                if (matrix[row][col] == -1) {
26                    matrix[row][col] = maxValue;
27                }
28            }
29        }
30      
31        // Return the modified matrix.
32        return matrix;
33    }
34};
35
1function modifiedMatrix(matrix: number[][]): number[][] {
2    // Get the number of rows (m) and columns (n) from the matrix.
3    const numberOfRows = matrix.length;
4    const numberOfColumns = matrix[0].length;
5  
6    // Iterate over each column.
7    for (let columnIndex = 0; columnIndex < numberOfColumns; ++columnIndex) {
8        // Initialize maximum value in the column as the smallest possible number.
9        let maximumInColumn = -1;
10      
11        // Find the maximum value in the current column.
12        for (let rowIndex = 0; rowIndex < numberOfRows; ++rowIndex) {
13            maximumInColumn = Math.max(maximumInColumn, matrix[rowIndex][columnIndex]);
14        }
15      
16        // Replace all -1s in the current column with the maximum value found.
17        for (let rowIndex = 0; rowIndex < numberOfRows; ++rowIndex) {
18            if (matrix[rowIndex][columnIndex] === -1) {
19                matrix[rowIndex][columnIndex] = maximumInColumn;
20            }
21        }
22    }
23  
24    // Return the modified matrix.
25    return matrix;
26}
27

Time and Space Complexity

The time complexity of the given code is O(m * n), where m is the number of rows and n is the number of columns in the matrix. This is because the code contains two nested loops, the outer loop iterating over the columns, and the inner loop iterating over the rows. For each column, the maximum value is found (taking O(m) time), and then each row in that column is updated if necessary (another O(m) time). Therefore, for each of the n columns, the algorithm performs work proportional to the number of rows m, leading to a total time complexity of O(m * n).

The space complexity of the algorithm is O(1). This reflects that the amount of extra space needed by the algorithm does not depend on the size of the input matrix. The only additional memory used is for the loop variables and the temporary variable mx, and this does not scale with the size of the input matrix, hence the constant space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄