Search code examples
javascriptalgorithmstackbacktracking

How would I fix my approach to this Manhattan Skyline/Stone Wall and where did I go wrong? Javascript


I just came across this problem and thought I would give it a try, but now I'm stuck and need help if possible.

The problem I keep facing is my return is usually off by 1 or 2 but I can't figure out why not. I have traced my code back but still can't figure it out

The problem :

You are to write a program to assist an architect in drawing the skyline of a city. Building are rectangular in shape, the height of each building is represented by an element in a given array.

sample image

The above skyline above is represented like [1,3,2,1,2,1,5,3,3,4,2] sample image

SO FAR HERE IS WHAT I AM WORKING WITH:

const skyline =(H)=> {
let stack = [];
let count = 0;
let height = 0;

 const addBlock = (value) => {
    if (value > height) {
        stack.push(value - height);
        height = value;
        count += 1;
    }
 }

 const pop = (value) => {
    while (value < height) {
        height -= stack.pop();
    }  
    if (value > height) {
        addBlock(value)
    }
 }

  for (let i = 0; i < H.length; i += 1) {
    let value = H[i];
    if (value < height) {
        pop(value)
    } else if (value > height) { 
        addBlock(value)
     }
 }

    return count
 }

 skyline([1,3,2,1,2,1,5,3,3,4,2]) //Expect 9

// Test CASES:

let strokes = [1,3,2,1,2,1,5,3,3,4,2] // Expect 9
// let strokes = [5,8] // Expect 8
// let strokes = [1,1,1,1] //  Expect 1

skyline(strokes)

Solution

  • Is this the basic algorithm?

    * Big eats small (and equal-sized)
    
    * Small reduces big to small
      adding the difference
    
    * Count last one standing
    

    Examples:

    [5,8]
    -> 8 eats 5, count 8
    
    [1,1,1,1]
    -> 1 eats 1 eats 1 eats 1
    -> count 1
    
    [1,3,2,1,2,1,5,3,3,4,2]
    -> 3 eats 1
    -> 2 reduces 3 to 2 and adds 3-2
    -> 1 reduces 2 to 1 and adds 2-1
    -> 2 eats 1
    -> 1 reduces 2 to 1 and adds 2-1
    -> 5 eats 1
    -> 3 reduces 5 to 3 and adds 5-3
    -> 3 eats 3
    -> 4 eats 3
    -> 2 reduces 4 to 2 and adds 4-2
    -> count 2
    Total: 1 + 1 + 1 + 2 + 2 + 2 = 9
    

    JavaScript code:

    function f(A){
      let result = 0;
      for (let i=1; i<A.length; i++)
        result += Math.max(0, A[i-1] - A[i]);
      return result + A[A.length-1];
    }
    
    console.log(f([1,3,2,1,2,1,5,3,3,4,2]));
    console.log(f([5,8]));
    console.log(f([1,1,1,1]));

    One liner :)

    function f(A){
      return [0].concat(A).reduce((a,b,i,A) => a + Math.max(0, A[i-1] - b)) + A[A.length-1];
    }