algoadvance

Leetcode 1732. Find the Highest Altitude

Problem Statement

Given an array of integers gain where gain[i] is the net gain in altitude between the (i-1)-th and the i-th points on a trip, return the highest altitude of a point.

Clarifying Questions

  1. Input Constraints:
    • What is the length of the array gain?
    • Are the integers in gain positive, negative, or both?
    • Is it guaranteed that the initial altitude is zero?
  2. Output Requirements:
    • Should the result be the highest altitude reached at any point?

Code

Here is a Java solution to the problem.

public class HighestAltitude {
    public int largestAltitude(int[] gain) {
        int currentAltitude = 0;
        int highestAltitude = 0;

        for (int i = 0; i < gain.length; i++) {
            currentAltitude += gain[i];
            if (currentAltitude > highestAltitude) {
                highestAltitude = currentAltitude;
            }
        }

        return highestAltitude;
    }

    public static void main(String[] args) {
        HighestAltitude solver = new HighestAltitude();
        
        int[] gain1 = {-5, 1, 5, 0, -7};
        System.out.println(solver.largestAltitude(gain1));  // Output: 1

        int[] gain2 = {-4, -3, -2, -1, 4, 3, 2};
        System.out.println(solver.largestAltitude(gain2));  // Output: 0
    }
}

Strategy

  1. Initialization:
    • Start with currentAltitude set to 0, which is the starting altitude.
    • highestAltitude is also initially set to 0.
  2. Iterate through the gain array:
    • For each element in the array, update the currentAltitude by adding the current gain to it.
    • If currentAltitude exceeds highestAltitude, update highestAltitude to the current value of currentAltitude.
  3. Return the highest altitude reached during the trip.

Time Complexity

This approach ensures an efficient solution to the problem while keeping the implementation straightforward.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI