Largest Local Values Problem

Given a 2D matrix of integers, your task is to find the largest local value for each element, excluding the border elements. The local value for an element at position (i, j) is defined as the maximum value within its 3x3 submatrix centered on (i, j).

• Input: A 2D matrix of dimensions n x m(where n>=3 and m>=3).

• Output: A 2D matrix result of dimensions (n-2) x (m-2), where each element in result[i][j] represents the largest local value from the 3x3 submatrix centered at matrix[i+1][j+1].

Brute force code:

To find the largest local values in a matrix, we define "local" as a 3x3 submatrix centered on each element. The brute-force approach involves examining each element and its surrounding 3x3 submatrix.

def largest_local_values_brute_force(matrix): rows = len(matrix) cols = len(matrix[0]) largest_values = []

for i in range(1, rows - 1): row = [] for j in range(1, cols - 1): max_val = matrix[i][j] for k in range(i - 1, i + 2): for l in range(j - 1, j + 2): max_val = max(max_val, matrix[k][l]) row.append(max_val) largest_values.append(row)

return largest_values

#example usage

matrix = [ [9, 1, 2, 3, 4], [4, 5, 6, 7, 8], [8, 1, 1, 2, 3], [9, 4, 3, 4, 5], [6, 5, 2, 1, 8] ]

result = largest_local_values_brute_force(matrix) for row in result: print(row)

• This code loops through each element of the matrix, excluding the border elements.

• For each element, it examines the surrounding 3x3 submatrix to find the maximum value.

• The results are stored in largest_values.

Optimised approach:

To optimize this approach, we can use sliding window technique to avoid redundant comparisons. This involves maintaining the maximum values of columns in the current window and using them to find the maximum values of rows.

def largest_local_values_optimized(matrix): import collections

rows = len(matrix) cols = len(matrix[0])

def sliding_window_maximum(arr, k): deq = collections.deque() result = []

for i in range(len(arr)): while deq and deq[0] < i - k + 1: deq.popleft() while deq and arr[deq[-1]] < arr[i]: deq.pop() deq.append(i) if i >= k - 1: result.append(arr[deq[0]]) return result

col_maxes = [[0] * cols for _ in range(rows - 2)]

for j in range(cols): col = [matrix[i][j] for i in range(rows)] max_col = sliding_window_maximum(col, 3) for i in range(len(max_col)): col_maxes[i][j] = max_col[i]

largest_values = []

for i in range(rows - 2): row_max = sliding_window_maximum(col_maxes[i], 3) largest_values.append(row_max)

return largest_values

#example usage

matrix = [ [9, 1, 2, 3, 4], [4, 5, 6, 7, 8], [8, 1, 1, 2, 3], [9, 4, 3, 4, 5], [6, 5, 2, 1, 8] ]

result = largest_local_values_optimized(matrix) for row in result: print(row)

• sliding_window_maximum function calculates the maximum in every sliding window of size 3 in a 1D array.

• For each column, we calculate the sliding window maximum to get the column-wise maximums for every 3x3 window.

• Then, for each row of the resulting column maximums, we again calculate the sliding window maximum.

• This reduces the number of comparisons by reusing the maximum values, leading to a more efficient solution.

Complexity Analysis

• The brute-force approach has a time complexity of O(n^2⋅9)=O(n^2) where n is the size of the matrix (assuming it's square).

• The optimized approach has a time complexity of O(n⋅m), where n and m are the dimensions of the matrix, due to the sliding window computations being linear in nature.