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\$
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
    
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ clever, simple and elegant... wish I would have thought of it :-) \$\endgroup\$ – David Refaeli Dec 7 '19 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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