3
\$\begingroup\$

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

\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

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
    
\$\endgroup\$
1
  • \$\begingroup\$ clever, simple and elegant... wish I would have thought of it :-) \$\endgroup\$ Dec 7, 2019 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.