The Problem

You are given an array representing the heights of neighboring buildings on a city street, from east to west. The city assessor would like you to write an algorithm that returns how many of these buildings have a view of the setting sun, in order to properly value the street.

For example, given the array [3, 7, 8, 3, 6, 1], you should return 3, since the top floors of the buildings with heights 8, 6, and 1 all have an unobstructed view to the west.

https://dailycodingproblem.com

My First Solution

const map = [3, 7, 8, 3, 6, 1]

const haveAView = (input) => input.reduce((acc, building, i) => {
	const nextBuilding = input[i + 1]
	const isCovered = nextBuilding && (nextBuilding > building)
	return acc + (isCovered ? 1 : 0)
}, 0)

const result = haveAView(map)
console.log(result)

---

Corrections

This solution turned out to be incorrect

This solution turned out to be incorrect. If one were to take the sample building map of:

[3, 7, 9, 5, 4, 8, 2, 1, 3]

It is clear that running the function above would result in an output of 4, even though it should in fact be three. The previous function only considered the next building when determining if a particular building was covered, and not the subsequent ones.

My Updated Solution

I updated my solution by including a recursive element in which if the input size does not match the output size, then the function is called again recursively with the output building set instead. This means that if they are in order: great, it returns the length. If they are not in order, the function is run again, eliminating at least one more building that is in the incorrect order. This process repeats until all of the buildings have been tested and none of them are being blocked by another building.

const map = [3, 7, 8, 3, 6, 1] // 3
const map2 = [3, 7, 9, 5, 4, 8, 2, 1, 3] // 3

const haveAView = (input) => {
	// Filter the "buildings" based on the height of the next one
	const output = input.reduce((acc, building, i) => {
		const nextBuilding = input[i + 1]
		const isCovered = nextBuilding && (nextBuilding > building)
	
		if (!isCovered) {
			return acc.concat([building])
		}

		return acc
	}, [])

	// If the output length is the same as the input length, return
	if (output.length === input.length) {
		return output.length
	}
	
	// Otherwise run the function again until the lengths are equal
	return haveAView(output)
}

const result = haveAView(map)
console.log('[Map 1] Should output 3')
console.log(result)

const result2 = haveAView(map2)
console.log('[Map 2] Should output 3')
console.log(result2)