algoadvance

Given a 2D integer matrix matrix, return a new 2D matrix such that for each cell (i, j) in the new matrix:

• The matrix value is 1 if the sum of its surrounding 8 cells in the original matrix is odd.
• The matrix value is 0 if the sum of its surrounding 8 cells is even.

Note:

• Cells outside the bounds of the matrix are considered to have a value of 0.
• The surrounding 8 cells of a cell (i, j) are the cells (i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i+1, j), and (i+1, j+1).

Clarifying Questions:

1. What should be the size of the new matrix?
   • The new matrix should have the same dimensions as the input matrix.
2. Should the original matrix be modified?
   • No, the original matrix should remain unchanged.
3. How should the edges and corners be handled since they have fewer than 8 neighbors?
   • Assume cells out of the boundary are zero.

Strategy:

1. Initialize a new matrix with the same dimensions as the input matrix.
2. Iterate through each cell in the original matrix.
3. Compute the sum of the 8 surrounding cells.
   • Use boundary checks to ensure cells out of bounds are treated as 0.
4. Set the value of the corresponding cell in the new matrix based on whether the sum is odd or even.
5. Return the modified matrix.

Time Complexity:

• The solution involves iterating through all cells of the matrix and checking the eight neighbors for each cell.
• For an M x N matrix, the time complexity would be O(M * N).

Let’s proceed with the code implementation.

Code:

def modify_matrix(matrix):
    if not matrix or not matrix[0]:
        return []
    
    rows, cols = len(matrix), len(matrix[0])
    new_matrix = [[0]*cols for _ in range(rows)]

    for i in range(rows):
        for j in range(cols):
            sum_neighbors = 0
            
            # Calculate the sum of 8 surrounding cells
            for x in (-1, 0, 1):
                for y in (-1, 0, 1):
                    if x == 0 and y == 0:
                        continue
                    ni, nj = i + x, j + y
                    if 0 <= ni < rows and 0 <= nj < cols:
                        sum_neighbors += matrix[ni][nj]
            
            # Set the value in new_matrix
            new_matrix[i][j] = 1 if sum_neighbors % 2 != 0 else 0
    
    return new_matrix

# Example Usage:
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

print(modify_matrix(matrix))

This code should handle the input matrix as specified and produce an output matrix where each cell is determined by the sum of its neighboring cells.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?