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

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.

enter image description here

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?

arraysalgorithm


Solution 1:[1]

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

Solution 2:[2]

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;

Solution 3:[3]

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;
}

Solution 4:[4]

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
}

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 גלעד ברקן
Solution 2
Solution 3
Solution 4 Dr.jacky

Related Questions