Asked in interview today:
You want to paint a skyline on your wall using only horizontal brush strokes. You are given an array of numbers, each representing the size of the column/building in that position. E.g. [1,2,1] - you can use two (horizontal) brush strokes. The first will paint the entire first row, and the second will paint the middle of the 2nd column.
Write an efficient algorithm to do so.
Here's my solution - idea being you count each end of strokes, and wipe out a row (or go up a row) for every iteration:
def solution(A): strokes = 0 copy = [a for a in A] while sum(copy) > 0: for i in range(len(copy)): if (copy[i] > 0) and ((i+1 == len(copy)) or (copy[i+1] == 0)): strokes += 1 if copy[i] > 0: copy[i] -= 1 return strokes
solution([1,0,5,8,0]) will output 9