[LeetCode] 1732. Find the Highest Altitude

1. Question

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.

2. Thoughts

3. Tips learned

The itertools that later come at AI improvement is something I newly learned:

The itertools module in Python provides a collection of fast, memory-efficient tools that are useful by themselves or in combination. Here are some commonly used itertools functions and some examples of how they can be used:

1. chain: Used to combine several iterables into one long iterable.

import itertools

# Combines multiple lists into one
list(itertools.chain([1, 2, 3], ['a', 'b', 'c']))

2. cycle: Used to cycle through an iterable indefinitely.

import itertools

# Prints 'A', 'B', 'C', 'A', 'B', 'C', ..., endlessly
for i, letter in enumerate(itertools.cycle('ABC')):
    if i > 5:  # To prevent an infinite loop in the example
        break
    print(letter)

3. accumulate: Makes an iterator that returns accumulated sums, or accumulated results of other binary functions.

import itertools

# Computes the accumulated sums
list(itertools.accumulate([1, 2, 3, 4, 5]))  # [1, 3, 6, 10, 15]

4. combinations: Takes an iterable and a integer r to create an iterator that will return all the unique combinations of r elements in the iterable.

import itertools

# All unique combinations of two elements from the list
list(itertools.combinations([1, 2, 3], 2))  # [(1, 2), (1, 3), (2, 3)]

5. permutations: Takes an iterable and an optional integer r to create an iterator that will return all possible permutations of the elements in the iterable of length r.

import itertools

# All possible 2-element permutations
list(itertools.permutations([1, 2, 3], 2))  # [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

6. product: Takes several iterables and creates an iterator that will return the Cartesian product of those iterables, similar to a nested for-loop.

import itertools

# Cartesian product of the given two iterables
list(itertools.product([1, 2], ['a', 'b']))  # [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]

7. groupby: Takes an iterable and groups values based on a key function.

import itertools

# Groups list of words by their first letter
words = ['apple', 'bat', 'bar', 'atom', 'book']
key_func = lambda x: x[0]
for key, group in itertools.groupby(sorted(words), key_func):
    print(key + ":", list(group))

8. islice: Performs slicing on iterators like a list slice operation but on iterator objects.

import itertools

# Slice an iterator from the 2nd to the 4th element
list(itertools.islice(range(10), 1, 5))  # [1, 2, 3, 4]

itertools functions are designed to be used in combination with each other and with other Python features to construct efficient and elegant solutions for a variety of complex problems.

4. My solution

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        before = 0
        max_alt = 0
        for i in gain:
            before = i + before
            max_alt = max(max_alt, before)

        return max_alt

80/80 cases passed (48 ms)
Your runtime beats 15.7 % of python3 submissions
Your memory usage beats 35 % of python3 submissions (16.2 MB)

5. AI Solution and Improvements

Your code is already quite clean and Pythonic, but we can make a few improvements for clarity and Pythonic style:

1. Use a list comprehension to create the list of altitudes, which can be more readable and Pythonic.
2. Use the built-in max function directly on the list of altitudes instead of updating it in every iteration.

Here's a revised version of your code with these improvements:

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        altitudes = [0] + list(itertools.accumulate(gain))
        return max(altitudes)

In this code:

• We use itertools.accumulate to create a running total of the gains, which gives us the altitude at each point.
• We start our altitudes list with a 0 to represent the starting altitude.
• We then find the maximum value in the altitudes list with max.

This approach is both more succinct and more in line with functional programming paradigms that are often considered Pythonic. It avoids manual loop-based accumulation and conditional updating of the max_alt variable.