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.
The above skyline above is represented like
[1,3,2,1,2,1,5,3,3,4,2]
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)
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];
}