Lookout tiles
EasyOnline Assessment
Find the tiles of a rooftop terrace that make good lookout spots.
The terrace is a grid of square tiles, and heights[r][c] is the height of the tile in row r, column c (row 0 is the top row, column 0 the left column). The neighbours of a tile are the tiles that touch it, including diagonally: up to 8 of them. Tiles on an edge or in a corner have fewer neighbours, and tiles outside the terrace do not count as neighbours at all.
A tile is a lookout when it is strictly higher than more than half of its own neighbours. A neighbour of equal height does not count as lower. A tile with no neighbours is never a lookout.
Input: heights, a non-empty rectangular list of lists of integers.
Output: a list of [row, column] pairs, one for every lookout tile, in row-major order (by row, then by column). If there are none, return [].
Example 1
- Input:
- [[[3,1,2],[1,9,1],[2,1,4]]]
- Output:
- [[0,0],[0,2],[1,1],[2,0],[2,2]]
- Explanation
- The centre tile (height 9) beats all 8 neighbours. Each corner has only 3 neighbours: the corner 3 beats the two 1s next to it (2 of 3, more than half), and the other corners work the same way. The edge tiles (height 1) beat nothing. Result: the four corners and the centre.
Example 2
- Input:
- [[[4,4,1,7]]]
- Output:
- [[0,3]]
- Explanation
- On a single row each tile has at most 2 neighbours. The first 4 has neighbours 4 only, and equal does not count as lower. The second 4 beats the 1 but not the other 4: exactly half of its 2 neighbours, which is not more than half. Only the 7 qualifies, beating its single neighbour.
Example 3
- Input:
- [[[2,7,2,7],[7,2,7,2],[2,7,2,7]]]
- Output:
- [[0,1],[0,3],[1,0],[2,1],[2,3]]
- Explanation
- The 7 on the top edge has 5 neighbours (2, 2, 7, 2, 7) and beats three of them, which is more than half. The 7 in the middle of the second row has 8 neighbours and beats only 4 (the four 2s); four of eight is exactly half, so it is not a lookout. The top-right 7 is a corner with 3 neighbours and beats two.
Constraints
1 <= heights.length <= 301 <= heights[i].length <= 30, and every row has the same length0 <= heights[i][j] <= 1,000,000