How can I count how many horizontal brush strokes are required to draw an array of buildings?

Question

By given an array of integers, each element represents a building. For example: int buildings[] = {1, 4, 3, 2, 3, 1}.

If I drew the buildings horizontally with a brush, how many brush strike I would use?

I should write a function that returns the number of these brush strokes. For example 5.

I can do it easily on run time O(n^2), by using 2 loops.

The external loop running on the levels of each building (according to the highest building).
The inner loop is running on the array from 0 to n, and compares the difference of the height (0 or 1) between two near elements.

How can I do this in the O(n) time and O(n) space?

samgak · Accepted Answer · 2019-05-31 00:09:40Z

33

A brush stroke starts whenever the height increases going from left to right, and ends when it decreases. You only need to look at when it increases, because if you just count the starting points of each stroke you will have the stroke count. Instead of looping over the height levels in an inner loop, just subtract one height level from the previous to get the difference.

In pseudo-code:

int BrushCount(int[] buildings)
{
    int brushCount = 0;
    int prevHeight = 0;
    for(int i = 0; i < buildings.length; i++)
    {
        if(buildings[i] > prevHeight)
             brushCount = brushCount + (buildings[i] - prevHeight);
        prevHeight = buildings[i];
    }
    return brushCount;
}

Runs in O(n).

edited May 31, 2019 at 0:09

answered May 30, 2019 at 7:36

samgak

24.5k4 gold badges63 silver badges86 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

גלעד ברקן Over a year ago

Just a little nitpick - your pseudocode fails for the OP's two examples. Can you tell why?

AlexR Over a year ago

The update to prevHeight needs to happen unconditionally, otherwise the algorithm is incortect whenever you need multiple brush strokes on one height.

גלעד ברקן · Accepted Answer · 2019-05-30 14:48:14Z

4

A little code golf :) (Based on samgak's excellent explanation.)

const f = A => A.reduce((a,b,i,A) => a + Math.max(0, b - A[i-1]));

console.log(f([1, 4, 3, 2, 3, 1]))
console.log(f([4, 1, 2, 1, 2, 2]))

answered May 30, 2019 at 14:48

גלעד ברקן

24k3 gold badges29 silver badges64 bronze badges

3 Comments

גלעד ברקן Over a year ago

@Neil what makes mine not "actual?"

David Hammen Over a year ago

Code golf is about making code as short as possible. It's a fun game, but one that should never be used on code written for ones employer.

גלעד ברקן Over a year ago

@Neil that's only if you're planning to win the round. I maintain my line is code golf, albeit not the shortest.

RBB · Accepted Answer · 2019-05-30 07:49:40Z

Counting from the end of the array use the last element as the initial value of the result, and compare the previous one with the current one.

If they are the same value then, the result increase one; if the previous one is smaller than the current one, do nothing; if the previous one is bigger than the current one then, result = result +previous-current

int i=sizeof buildings;
int t=buildings[i]; 
while(i>0){
  if(buildings[i-1]-buildings[i]>0) t+=(buildings[i-1]-buildings[i]);
  else if(buildings[i-1]-buildings[i]==0) ++t;
  --i;
}
return t;

Haim Ruso · Accepted Answer · 2020-03-31 19:38:01Z

2

public static int brushCount(int[] buildings)
{
    int count=0;
    for(int i=0; i<=buildings.length-1; i++){
        if((i+1)<(buildings.length)){
            if(buildings[i]>buildings[i+1]){
                count += buildings[i]-buildings[i+1];
            }
        }else{
            count += buildings[i];
        } 
    }
    return count;
}

edited Mar 31, 2020 at 19:38

answered Mar 31, 2020 at 19:19

Haim Ruso

212 bronze badges

Comments

black.swordsman · Accepted Answer · 2022-08-25 06:11:07Z

You can easily see that we need a stack like approach to keep heights in increasing order and add the difference between top element and current element when our current value is less than top value.

Since we don't values before the top, we can just keep a variable for the top element.

#include <bits/stdc++.h>

using namespace std;
using ll = int64_t;

int solve(vector<int> v) {
    int brushes = 0, lastMax = 0;

    for (auto val: v) {
        if (val > lastMax) {
            brushes += lastMax - val;
        }
        lastMax = val;
    }

    brushes += lastMax;

    return brushes;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    vector<int> v1 {1, 4, 3, 2, 3, 1}, v2 {4, 1, 2, 1, 2, 2};
    cout << solve(v1) << ' ' << solve(v2) << endl; // 5 6
}

Dr.jacky · Accepted Answer · 2022-05-22 10:21:58Z

0

Kotlin version of @samgak's answer:

fun brush(nums: IntArray): Int {
    var c = 0
    var ph = 0
    
    nums.forEach {
        if (it > ph) c += (it - ph)
        ph = it
    }
    
    return c
}

answered May 22, 2022 at 10:21

Dr.jacky

3,6036 gold badges58 silver badges98 bronze badges

Comments

Hanh Nguyen · Accepted Answer · 2022-06-22 02:15:33Z

0

Shortly java answer:

int BrushCount(int[] buildings) {
    int s=0,p=0;
    for(int x:buildings) s-=(x>p?p:x)-(p=x);
    return s;
}

answered Jun 22, 2022 at 2:15

Hanh Nguyen

1351 silver badge16 bronze badges

1 Comment

D.T Over a year ago

is s supposed to add, not substract? it should be s+=

K14 · Accepted Answer · 2023-04-17 01:27:25Z

0

Scala version of @samgak's answer:

object Solution {
  def solution(a: Array[Int]): Int = {
    var brushCount = 0;
    var prevheight = 0;
    for (i <- a) {
      if (i > prevHeight) {
        brushCount = brushCount + - (i - prevHeight);
      }
      prevHeight = i;
    }
    return brushCount;
  }
}

answered Apr 17, 2023 at 1:27

K14

1917 bronze badges

Comments

Ahmad · Accepted Answer · 2023-11-10 11:16:18Z

0

This question is asking for help using C#, but also there is Scala, Kotlin, and C++ so there is a Python code.

def BrushCount(A):
    if not A:
        return 0

    total_strokes = 0
    max_height = 0

    for height in A:
        strokes_needed = max(0, height - max_height)
        total_strokes += strokes_needed
        max_height = max(max_height, height)

    return total_strokes

Goodluck!

answered Nov 10, 2023 at 11:16

Ahmad

1,8846 gold badges30 silver badges59 bronze badges

Collectives™ on Stack Overflow

How can I count how many horizontal brush strokes are required to draw an array of buildings?

9 Answers 9

2 Comments

3 Comments

Comments

Comments

Comments

Comments

1 Comment

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

9 Answers 9

2 Comments

3 Comments

Comments

Comments

Comments

Comments

1 Comment

Comments

Comments

Linked

Related