LeetCodeArrayProblems/2373. LargestLocalValuesInAMatrix.py at main · plipustel/LeetCodeArrayProblems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 # @PROBLEM       : 2373. Largest Local Values in a Matrix
# @LEVEL         : EASY
# @STATUS        : SOLVED !
# @COMPLEXITY    : O(n^2)
# @SOLVED BY     : PLIPUS TELAUMBANUA <www.plipustel.com>
# @LEETCODE      : https://leetcode.com/u/plipustel/
# @DATE          : SATURDAY, JUN 23 2024
#
# @PROBELM SOURCE: https://leetcode.com/problems/largest-local-values-in-a-matrix/description/
# @PROBLEM DESC  :
# You are given an n x n integer matrix grid.
# Generate an integer matrix maxLocal of size (n - 2) x (n - 2) such that:
# maxLocal[i][j] is equal to the largest value of the 3 x 3 matrix in grid centered around row i + 1 and column j + 1.
# In other words, we want to find the largest value in every contiguous 3 x 3 matrix in grid.
# Return the generated matrix.

# Example 1:
# Input: grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]
# Output: [[9,9],[8,6]]
# Explanation: The diagram above shows the original matrix and the generated matrix.
# Notice that each value in the generated matrix corresponds to the largest value of a contiguous 3 x 3 matrix in grid.

# Example 2:
# Input: grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]]
# Output: [[2,2,2],[2,2,2],[2,2,2]]
# Explanation: Notice that the 2 is contained within every contiguous 3 x 3 matrix in grid.


# Constraints:
# n == grid.length == grid[i].length
# 3 <= n <= 100
# 1 <= grid[i][j] <= 100

class Solution(object):
    def largestLocal(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: List[List[int]]
        """
        n = len(grid)

        # build matrix n-2 x n-2
        output = [[None] * (n- 2) for x in range(n - 2)]

        for i in range(n - 2):
            for j in range(n - 2):
                find_max = max(grid[i][j], grid[i][j+1], grid[i][j+2],
                         grid[i+1][j], grid[i+1][j+1], grid[i+1][j+2],
                         grid[i+2][j], grid[i+2][j+1], grid[i+2][j+2])

                output[i][j] = find_max

        return output

# test
grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]
grid1 = [[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]]
sol = Solution()
print(sol.largestLocal(grid))