easy Problem 4 Find the Highest Altitude

Problem Statement

A bike rider is going on a ride. The road contains n + 1 points at different altitudes. The rider starts from point 0 at an altitude of 0.

Given an array of integers gain of length n, where gain[i] represents the net gain in altitude between points i and i + 1 for all (0 <= i < n), return the highest altitude of a point.

Examples

Example 1

• Input: gain = [-5, 1, 5, 0, -7]
• Expected Output: 1
• Justification: The altitude changes are [-5, -4, 1, 1, -6], where 1 is the highest altitude reached.

Example 2

• Input: gain = [4, -3, 2, -1, -2]
• Expected Output: 4
• Justification: The altitude changes are [4, 1, 3, 2, 0], where 4 is the highest altitude reached.

Example 3

• Input: gain = [2, 2, -3, -1, 2, 1, -5]
• Expected Output: 4
• Justification: The altitude changes are [2, 4, 1, 0, 2, 3, -2], where 4 is the highest altitude reached.

Constraints:

• n == gain.length
• 1 <= n <= 100
• -100 <= gain[i] <= 100

Solution

To solve this problem, we'll track the cumulative altitude as we traverse the array of altitude changes. We start with an initial altitude of zero. As we iterate through the array, we continually update the current altitude by adding the current change (which could be positive, negative, or zero) to it.

Simultaneously, we keep track of the highest altitude reached so far. This can be done by comparing the current altitude with the maximum altitude recorded after each update. Once we have gone through all the changes, the recorded maximum altitude is the answer. This approach efficiently calculates the highest altitude with a single pass through the array, ensuring optimal time complexity.

Here is the solution with detailed steps.

1. Initialize Variables:

   • Start by initializing two variables: currentAltitude and maxAltitude.
   • Set both currentAltitude and maxAltitude to 0, as the starting point is considered at sea level (zero altitude).

2. Iterate Through the Array:

   • Loop through each element of the given array of altitude changes.
   • For each element in the array, consider it as a change in altitude (gain or loss).

3. Update Current Altitude:

   • During each iteration, add the current element (altitude change) to currentAltitude.

4. Check and Update Maximum Altitude:

   • After updating currentAltitude, compare it with maxAltitude.
   • If currentAltitude is greater than maxAltitude, update maxAltitude with the value of currentAltitude.
   • This ensures that maxAltitude always holds the highest altitude reached so far.

5. Continue Until the End of the Array:

   • Continue the process of updating currentAltitude and checking/updating maxAltitude until you reach the end of the array.

6. Return the Highest Altitude:

   • After completing the iteration through the entire array, maxAltitude will hold the highest altitude reached during the journey.
   • Return maxAltitude as the final result.

Algorithm Walkthrough

• Initialize currentAltitude = 0 and maxAltitude = 0.
• Loop begins:
  • i = 0: Add 2 to currentAltitude => currentAltitude = 2. maxAltitude is updated to 2.
  • i = 1: Add 2 to currentAltitude => currentAltitude = 4. maxAltitude is updated to 4.
  • i = 2: Add -3 to currentAltitude => currentAltitude = 1. maxAltitude remains 4.
  • i = 3: Add -1 to currentAltitude => currentAltitude = 0. maxAltitude remains 4.
  • i = 4: Add 2 to currentAltitude => currentAltitude = 2. maxAltitude remains 4.
  • i = 5: Add 1 to currentAltitude => currentAltitude = 3. maxAltitude remains 4.
  • i = 6: Add -5 to currentAltitude => currentAltitude = -2. maxAltitude remains 4.
• Loop ends.
• maxAltitude which is 4 is returned as the output.

Code

Here is the code for this algorithm:

public class Solution {

  public int largestAltitude(int[] gain) {
    int currentAltitude = 0; // To store the current altitude during iteration
    int maxAltitude = 0; // To store the maximum altitude encountered

    // Iterate through the gain array, updating the current and max altitudes
    for (int i : gain) {
      currentAltitude += i;
      maxAltitude = Math.max(currentAltitude, maxAltitude);
    }

    return maxAltitude;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    System.out.println(solution.largestAltitude(new int[] { -5, 1, 5, 0, -7 })); // Expected: 1

    // Example 2
    System.out.println(
      solution.largestAltitude(new int[] { 4, -3, 2, -1, -2 })
    ); // Expected: 4

    // Example 3
    System.out.println(
      solution.largestAltitude(new int[] { 2, 2, -3, -1, 2, 1, -5 })
    ); // Expected: 4
  }
}

Complexity Analysis

Time Complexity

• Single pass: The algorithm iterates through the gain array once, processing each element to update the currentAltitude and check the maxAltitude. This requires time, where N is the length of the gain array.

• No nested loops or repeated operations are present, so the time complexity remains linear.

Overall time complexity: .

Space Complexity

• Constant space: The algorithm only uses a few extra variables (currentAltitude and maxAltitude), both of which require constant space, .

• No additional data structures (like arrays or lists) are used that scale with the input size.

Overall space complexity: .