Find number of horizontal brush strokes to paint a skyline

Question

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

Answer 1

With every height drop by 1 point, a line ends. So you just need to calculate the sum of height drops. Don't forget to account for the last height. You could also do the same thing from the other end (every height increase starts a line).

def skyline(heights):
  diffs = [e1 - e2 for e1, e2 in zip(heights, heights[1:])]
  return sum(diff for diff in diffs if diff > 0) + heights[-1]

---

Some remarks on your code:

• copy = [a for a in A] can be rewritten as copy = A.copy()

• some parentheses in (copy[i] > 0) and ((i+1 == len(copy)) or (copy[i+1] == 0)) can be omitted:

  if copy[i] > 0 and (i+1 == len(copy) or copy[i+1] == 0):

• you can use enumerate in the for loop:

  for i, elem in enumerate(copy):
    if elem > 0 and (i+1 == len(copy) or copy[i+1] == 0):
      strokes += 1
    if elem > 0:
      copy[i] -= 1
  

• the ifs can be merged:

  for i, elem in enumerate(copy):
    if elem > 0:
      copy[i] -= 1
      if i+1 == len(copy) or copy[i+1] == 0:
        strokes += 1