algoadvance

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. The array gain represents the net gain in altitude experienced while traversing from one point to the next along a hiking trail.

Your task is to find the highest altitude possible during the hike. Assume that the starting altitude is 0.

Example

Input:

gain = [-5, 1, 5, 0, -7]

Output:

1

Explanation:

• Starting at altitude 0.
• Gain -5: altitude = 0 - 5 = -5
• Gain 1: altitude = -5 + 1 = -4
• Gain 5: altitude = -4 + 5 = 1
• Gain 0: altitude = 1 + 0 = 1
• Gain -7: altitude = 1 - 7 = -6
• The highest altitude is 1.

Clarifying Questions

1. Can gain contain both positive and negative integers?
   • Yes.
2. Is it guaranteed that gain will have at least one element?
   • Yes.

Strategy

1. Initialize current_altitude to 0 and max_altitude also to 0.
2. Iterate through each value in gain and adjust current_altitude by adding the current gain.
3. During each adjustment, compare and update max_altitude if current_altitude is higher.
4. Return max_altitude after completing the iteration.

Code

def largestAltitude(gain):
    current_altitude = 0
    max_altitude = 0

    for g in gain:
        current_altitude += g
        if current_altitude > max_altitude:
            max_altitude = current_altitude

    return max_altitude

Time Complexity

The time complexity of the solution is O(n), where n is the length of the gain array. This is because we need to iterate through all the elements of the gain array once.

The space complexity is O(1) because we are using a constant amount of space regardless of the input size.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?