Drone Flight Planner

You are planning the amount of fuel need to complete a drone flight.
To fly higher, the drone burns 1 liter of fuel per feet. However, flying lower charges the drone with the amount of energy equivalent to 1 liter of fuel for every feet. Flying sideways takes no energy (only flying up and down takes/charges energy).

Given an array of 3D coordinates namedroute, find the minimal amount of fuel the drone would need to fly through this route.
Explain and code the most efficient solution possible, with the minimal number of actions and variables.

Example:
Completing the route [{x:0, y:2, z:10},{x:3, y:5, z:0},{x:9, y:20, z:6},{x:10, y:12, z:15},{x:10, y:10, z:8}] requires a minimum of 5 liters of fuel.

Hints & Tips

You can assume that the drone stands on the first coordinate inroute, before its flight starts.
If you don't get the simple solution, try running the basic solution on paper and get the sense of it. Calculate the difference of the max height and starting height and notice why it's always enough.
To get the maximum rating for Problem Solving, your peer must come up with the efficient (and better) solution and explain it well.
If your peer is having a hard time, help them focus by getting thex&ycoordinates out of the way.
Another hint: ask your peer to focus on the example route array and to solve for this route first, coordinate after coordinate, and then generalize a solution.
A common solution for this question is calculating the difference between the max & min heights on the routes. That is, of course, a wrong answer. Try to think why.

Solution

Since the drone only spend/gain energy when flying up and down, we can ignore thexandycoordinates and focus only on thezcoordinate.
We should come up with the amount of initial fuel required to enable the flight. Therefore, we have to make sure we can climb up to every point inroute.

Basic & Easy Solution
Imagine you start the flight with an empty fuel tank, but are able to fuel the drone while it's in the air.
Iterating over all coordinates, count how many liters of fuel you need to add along the route to never be out of fuel.
This amount is the minimal amount of fuel you need to make it through the flight.

Using this on the example route, we get to a negative balance only when climbing from6to15. The negative balance on that point is-5and we add 5 liters to cover for it.

```java

function calcFuelBasic(zRoute):
   litersAdded = 0
   energyBalance = 0
   for i from 1 to length(zRoute)-1:
      energyBalance = energyBalance + (zRoute[i-1] - zRoute[i])
      if (energyBalance < 0):
         litersAdded = litersAdded - energyBalance
         energyBalance = 0
   return litersAdded

```

Runtime Complexity:linearO(n). Constant number of operations for each coordinates + a constant number of operations.
Number of operations:2-4 for each coordinate + 3 general.

Better: The Elegant & Efficient Solution
This solution is based on one observation: The initial fuel amount is what it takes the drone to climb from the start point to the highest (max) point on the route.
Getting to any height below the start height produces energy, and going above take at most the difference between max height and start height.
Even if we go below before climbing to the max height, by getting to the same height as the start, our balance is zero and we then need the energy to climb from start to max.

```java
function calcFuelSimple(zRoute):
   maxHeight = zRoute[0]
   for i from 1 to length(zRoute)-1:
      if (zRoute[i] > maxHeight):
         maxHeight = zRoute[i]
   return maxHeight - zRoute[0] 
```

Runtime Complexity:linearO(n). We iterate of the array once with constant number of actions per iteration.
Number of operations:1 or 2 per iteration + 2 general.

Drone Flight Planner