Sum of Distinct Values on the Borders of All Maximum-Sum Square Frames
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Online Assessment
You are given a rectangular matrix of integers and an integer `frame_size`. A frame is any square submatrix made of `frame_size` consecutive rows and `frame_size` consecutive columns. The border of a frame is the set of its cells that lie in its first row, last row, first column or last column; the cells inside it are not part of the border. The border sum of a frame is the sum of the values in its border cells, each cell counted once.
First find the maximum border sum over all frames. Then take every frame whose border sum equals that maximum, collect the values in all of their border cells, and return the sum of the distinct values in that collection.
### Function Signature
```python
def max_frame_distinct_sum(matrix: list[list[int]], frame_size: int) -> int:
```
### Rules
- Frames are axis-aligned. A frame's top-left cell can be any `(r, c)` with `r + frame_size <= R` and `c + frame_size <= C`, where `R` and `C` are the numbers of rows and columns.
- When `frame_size` is 1, the border is the single cell. When `frame_size` is 2, every cell of the frame is on its border.
- Distinctness is by value, across the union of the borders of all maximum frames: a value that appears on the borders of two maximum frames, or twice on one border, is added once.
- Values from frames whose border sum is below the maximum are ignored, even if the same cells belong to a maximum frame's interior.
- Negative values are added as they are.
### Constraints
- `1 <= R, C <= 100`, where `R = len(matrix)` and `C = len(matrix[0])`; every row has length `C`.
- `1 <= frame_size <= min(R, C)`
- `-10^4 <= matrix[i][j] <= 10^4`
- The absolute value of the answer is at most 50,005,000, which fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: matrix = [
[1, 2, 3, 4],
[5, 100, 7, 8],
[9, 10, 11, 12]
], frame_size = 3
Output: 150
```
There are two frames. The frame over columns 0 to 2 has border cells 1, 2, 3, 5, 7, 9, 10, 11 with sum 48; the 100 is inside it, not on its border. The frame over columns 1 to 3 has border cells 2, 3, 4, 100, 8, 10, 11, 12 with sum 150; here the 100 is in its first column. Only the second frame has the maximum sum, and its distinct border values add up to 150.
**Example 2**
```text
Input: matrix = [
[1, 1, 1],
[1, 5, 1],
[1, 1, 1]
], frame_size = 2
Output: 6
```
All four 2 by 2 frames contain the center 5 and three 1s, so each has border sum 8 and all four are maximum frames. The distinct values on their borders are 1 and 5, so the answer is 6.
**Example 3**
```text
Input: matrix = [
[3, 7],
[7, -2]
], frame_size = 1
Output: 7
```
Each cell is its own frame. The maximum border sum is 7, reached by two frames, and the only distinct value among them is 7.
Overview: Among all square frames of a given size inside an integer matrix, find those with the largest border sum, then add up the distinct values that appear on the borders of every such frame. Tests careful border enumeration that excludes interior cells, tie handling across several frames, and de-duplication by value.
You are given a rectangular matrix of integers with R rows and C columns, and an integer frame_size. A frame is any square submatrix made of frame_size consecutive rows and frame_size consecutive columns. Frames are axis-aligned: a frame's top-left cell can be any (r, c) with r + frame_size <= R and c + frame_size <= C.
The border of a frame is the set of its cells that lie in its first row, last row, first column or last column; the cells inside it are not part of the border. When frame_size is 1, the border is the single cell. When frame_size is 2, every cell of the frame is on its border. The border sum of a frame is the sum of the values in its border cells, each cell counted once.
First find the maximum border sum over all frames. Then take every frame whose border sum equals that maximum, collect the values in all of their border cells, and return the sum of the distinct values in that collection.
- Distinctness is by value, across the union of the borders of all maximum frames: a value that appears on the borders of two maximum frames, or twice on one border, is added once.
- Values from frames whose border sum is below the maximum are ignored, even if the same cells belong to a maximum frame's interior.
- Negative values are added as they are.
Implement max_frame_distinct_sum(matrix, frame_size), which returns this sum as an integer.
Constraints:
- 1 <= R, C <= 100, where R = len(matrix) and C = len(matrix[0]); every row has length C.
- 1 <= frame_size <= min(R, C)
- -10^4 <= matrix[i][j] <= 10^4
- The absolute value of the answer is at most 50,005,000, which fits in a 32-bit signed integer. No border sum or answer can exceed 2^31 - 1, so int is sufficient in Java and C++.
Example 1:
Input: matrix = [[1, 2, 3, 4], [5, 100, 7, 8], [9, 10, 11, 12]], frame_size = 3
Output: 150
There are two frames. The frame over columns 0 to 2 has border cells 1, 2, 3, 5, 7, 9, 10, 11 with sum 48; the 100 is inside it, not on its border. The frame over columns 1 to 3 has border cells 2, 3, 4, 100, 8, 10, 11, 12 with sum 150. Only the second frame has the maximum sum, and its distinct border values add up to 150.
Example 2:
Input: matrix = [[1, 1, 1], [1, 5, 1], [1, 1, 1]], frame_size = 2
Output: 6
All four 2 by 2 frames contain the center 5 and three 1s, so each has border sum 8 and all four are maximum frames. The distinct values on their borders are 1 and 5, so the answer is 6.
Constraints
- 1 <= R, C <= 100, where R = len(matrix) and C = len(matrix[0]); every row has length C.
- 1 <= frame_size <= min(R, C)
- -10^4 <= matrix[i][j] <= 10^4
- The absolute value of the answer is at most 50,005,000, which fits in a 32-bit signed integer.
Examples
Input: ([[5]], 1)
Expected Output: 5
Explanation: Minimum valid input: one cell is the only frame.
Input: ([[1, 2, 3, 4], [5, 100, 7, 8], [9, 10, 11, 12]], 3)
Expected Output: 150
Explanation: Source example 1: the 100 is interior to the left frame but on the right frame's border; only the right frame (sum 150) is maximum.
Hints
- Write down exactly which cells form a frame's border for frame_size 1, 2 and 3; make sure no cell is counted twice and no interior cell is counted at all.
- You cannot tell which frames count until the maximum border sum over all frames is known.
- Distinctness is by value, not by cell position: the same value on several cells or several qualifying frames contributes once.