LeetCode 1732. Find the Highest Altitude Solution in Java, C++, Python & More | Explanation + Code

Description

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.length
• 1 <= n <= 100
• -100 <= gain[i] <= 100

Solutions

Solution 1: Prefix Sum (Difference Array)

We assume the altitude of each point is h_i. Since gain[i] represents the altitude difference between the ith point and the (i + 1)th point, we have gain[i] = h_{i + 1} - h_i. Therefore:

∑_{i = 0}^n-1 gain[i] = h₁ - h₀ + h₂ - h₁ + … + h_n - h_{n - 1} = h_n - h₀ = h_n

which implies:

h_i+1 = ∑_{j = 0}ⁱ gain[j]

We can see that the altitude of each point can be calculated through the prefix sum. Therefore, we only need to traverse the array once, find the maximum value of the prefix sum, which is the highest altitude.

In fact, the gain array in the problem is a difference array. The prefix sum of the difference array gives the original altitude array. Then find the maximum value of the original altitude array.

The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the array gain.

PythonJavaC++GoRustJavaScriptPHPC

class Solution: def largestAltitude(self, gain: List[int]) -> int: return max(accumulate(gain, initial=0))(code-box)

class Solution { public int largestAltitude(int[] gain) { int ans = 0, h = 0; for (int v : gain) { h += v; ans = Math.max(ans, h); } return ans; } }(code-box)

class Solution { public: int largestAltitude(vector<int>& gain) { int ans = 0, h = 0; for (int v : gain) h += v, ans = max(ans, h); return ans; } };(code-box)

func largestAltitude(gain []int) (ans int) { h := 0 for _, v := range gain { h += v if ans < h { ans = h } } return }(code-box)

impl Solution { pub fn largest_altitude(gain: Vec<i32>) -> i32 { let mut ans = 0; let mut h = 0; for v in gain.iter() { h += v; ans = ans.max(h); } ans } }(code-box)

/** * @param {number[]} gain * @return {number} */ var largestAltitude = function (gain) { let ans = 0; let h = 0; for (const v of gain) { h += v; ans = Math.max(ans, h); } return ans; };(code-box)

class Solution { /** * @param Integer[] $gain * @return Integer */ function largestAltitude($gain) { $max = 0; for ($i = 0; $i < count($gain); $i++) { $tmp += $gain[$i]; if ($tmp > $max) { $max = $tmp; } } return $max; } }(code-box)

#define max(a, b) (((a) > (b)) ? (a) : (b)) int largestAltitude(int* gain, int gainSize) { int ans = 0; int h = 0; for (int i = 0; i < gainSize; i++) { h += gain[i]; ans = max(ans, h); } return ans; }(code-box)