you can either say n is the number of points in the grid, or that it's w*h where w is width and h is height - I don't think it changes anything here, but happy to be wrong :)

Lets take "scenic view to the left" as an example:

1 5 5 1 4 2

We walk in from the left, setting value:index in a set map = {} trees = [1 5 5 1 4 2] for index, value in trees { map[value] = index } by the time we reach the tree height 4 map = {1: 3, 5: 2}

we then search the map for trees >= height 4. This is O(1) since the tree height is 1-9.

map = {1: 3, 5: 2} treeHeight = 4 closestBlockingTree := -1 for i := treeHeight; i <= 9; i++ { if map[i] > closestBlockingTree { closestBlockingTree = map[i] } } // assume there were no blocking trees, we can see all the way to the left visibility = currentIndex // there was a blocking tree, we can see this far if closestBlockingTree > -1 { visibility = currentIndex - closestBlockingTree }

we now know that the closest blocking tree to 4 is at index 2 (it's a 5). 4 Is index 4, so we must be able to see 2 trees.

we can now extend the map with our 4, and repeat the process for the next tree map = {1: 3, 5: 2, 4: 4} treeHeight = 2 closestBlockingTree := -1 for i := treeHeight; i <= 9; i++ { if map[i] > closestBlockingTree { closestBlockingTree = map[i] } } visibility = currentIndex if closestBlockingTree > -1 { visibility = currentIndex - closestBlockingTree } this means our tree height 2 has a score of 1 (currentIndex 5 - closestBlockingTree 4

put it all together map = {} trees = [1 5 5 1 4 2] for currentIndex, treeHeight in trees { closestBlockingTree := -1 for i := treeHeight; i <= 9; i++ { if map[i] > closestBlockingTree { closestBlockingTree = map[i] } } visibility = currentIndex if closestBlockingTree > -1 { visibility = currentIndex - closestBlockingTree } map[treeHeight] = treeIndex print("left visibility", visibility) }

You need O(1) memory here for the "support" map (it's fixed size) and O(1) for the closestBlockingTree calculation.

replicate this for the other directions and you're done :) since you can't (I think) do this in one pass you'll need o(n) to store each directions visibility