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

Modify the Matrix

Number: 3330

Difficulty: Easy

Paid? No

Companies: Fidelity

Problem Description

Given an m x n matrix, create a new matrix "answer" which is initially identical to the input matrix. Then, for each cell in "answer" that contains a -1, replace that value with the maximum value found in its corresponding column in the original matrix. The guarantee is that every column contains at least one non-negative integer.

Key Insights

  • We need to compute the maximum for each column in the matrix.
  • After computing the column maximums, traverse the matrix again.
  • If an element is -1, replace it with the precomputed maximum for that column.
  • Given the constraints (matrix dimensions up to 50x50), a simple two-pass solution is efficient.

Space and Time Complexity

Time Complexity: O(m * n) – one pass to compute maximums and another pass to update the matrix. Space Complexity: O(n) – additional array to store the maximum element for each of the n columns.

Solution

The solution involves two major steps:

  1. Compute the maximum value for each column by iterating over all rows for each column.
    • Use an auxiliary list (or array) "colMax" of size n to store the maximum values.
  2. Create a copy of the original matrix called "answer" and iterate over it.
    • For each element that is equal to -1, replace it with the corresponding column maximum from "colMax". This approach uses basic array operations without any advanced data structures, ensuring clarity and efficiency.

Code Solutions

# Python solution for "Modify the Matrix"
def modifyMatrix(matrix):
    # Get the number of rows and columns in the matrix
    m = len(matrix)
    n = len(matrix[0])
    
    # Initialize an array to store maximum for each column
    col_max = [float('-inf')] * n
    
    # First pass: calculate the maximum for each column
    for row in range(m):
        for col in range(n):
            # Check if current element is greater than the stored maximum
            col_max[col] = max(col_max[col], matrix[row][col])
    
    # Create a copy of matrix for the answer
    answer = [row[:] for row in matrix]
    
    # Second pass: replace -1 with the column's maximum value
    for row in range(m):
        for col in range(n):
            if answer[row][col] == -1:
                answer[row][col] = col_max[col]
    
    return answer

# Example usage:
# matrix = [[1,2,-1],[4,-1,6],[7,8,9]]
# print(modifyMatrix(matrix))
← Back to All Questions