92. Cleanest Cut
A mosaic is built from stacked horizontal rows of tiles. wall[r] lists the widths of the tiles in row r, from left to right, and rows may have different total widths. A glass cutter will run one straight vertical laser line through all rows at an integer position x, measured from the left edge, where 1 <= x < W and W is the total width of the narrowest row. A tile is damaged only if x lies strictly inside it; a line that follows the seam between two tiles damages neither.
Return the minimum number of tiles that can be damaged by choosing the best x.
Example 1
- Input:
- wall = [[2,3],[1,4],[3,2]]
- Output:
- 2
- Explanation:
The narrowest row has width 5; the seams are at 2, 1 and 3, so any of those positions damages 2 tiles, and no position damages fewer.
Example 2
- Input:
- wall = [[1,1,1],[2,1],[1,2]]
- Output:
- 1
- Explanation:
Position 1 is a seam in rows 0 and 2 and position 2 is a seam in rows 0 and 1; either way only 1 tile is damaged.
Constraints
1 ≤ wall.length ≤ 105
2 ≤ wall[r].length ≤ 1000
The total number of tiles is at most 5 * 105
1 ≤ wall[r][i] ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(T)
- Space
- O(T)