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.
