There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.
You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < n). Return the highest altitude of a point.
Example 1:
Input: gain = [-5,1,5,0,-7] Output: 1 Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.
Example 2:
Input: gain = [-4,-3,-2,-1,4,3,2] Output: 0 Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.
Constraints:
n == gain.length1 <= n <= 100-100 <= gain[i] <= 100
The description was taken from https://leetcode.com/problems/find-the-highest-altitude/.
#O(N) Time, O(N) Space
class Solution:
def largestAltitude(self, gain: List[int]) -> int:
prefix_sum = [0]
for i in range(len(gain)):
prefix_sum.append(gain[i] + prefix_sum[-1])
return max(prefix_sum)This problem is a very good introduction to Prefix Sum algorithms.
The brute force way of solving this problem would be to iterate through each index and at each index, calculate the sum of itself and each index before it, then compare that range sum to the maximum sum saved.
The problem with that is we are summing the same ranges over and over again. For example, by the time we get to the third index, we would have already summed the range between the first and second but would not be utilizing that sum and instead would recalculate it then add the third index to the range sum.
When we see that we are doing that, we can implement a prefix sum.
With a prefix sum, we can keep a rolling snowball of each previous sum so that we don't have to recalculate previous indices. Instead, we can just throw the current sum onto the snowball because each index within a prefix sum array will contain the sum of the current element plus the sum of each element before it.
Let's start by initializing our prefix sum array.
We'll set its first element to zero because a prefix sum utilizes the range sum at the previous index of the prefix sum array, and once we begin from the first index there will be no previous index.
It also mentions in the problem description that the biker starts with an altitude of zero.
prefix_sum = [0]
Now let's traverse the given input.
At each index, we will throw the current gain onto the previous gain's rolling range sum snowball.
for i in range(len(gain)):
prefix_sum.append(gain[i] + prefix_sum[-1])
Once we have finished traversing the input array, all we need to do is return the maximum altitude that we encountered which would be the maximum range sum within our prefix sum array.
return max(prefix_sum)