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?

Answer 1

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).

Answer 2

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]))