First Climb in Elevation Samples, Strict and With a Tolerated Partial Descent

Elevation is sampled at regular intervals along a route. Given the samples as a list of integers, find the first climb and return its start and end indices as [start, end], or [] if the samples contain no climb.

The function supports two versions of the climb rules, chosen by a flag:

• tolerate_descent = False, the strict climb (Part 1): once a climb starts, the elevation may rise or stay flat but may not go down.
• tolerate_descent = True, the climb with partial descent (Part 2): a climb may dip temporarily and then continue, as long as the dip is small relative to the elevation gained so far and the route later rises above the climb's previous high point.

Function Signature

def first_climb(elevations: list[int], tolerate_descent: bool) -> list[int]:

Rules

Start (both versions). The first climb starts at the smallest index s such that elevations[s + 1] > elevations[s], that is, at the sample immediately before the first increase. Flat samples before that increase are not part of the climb. If no such index exists, return [].

End (both versions). Let P be the highest elevation reached so far in the climb. The climb ends at the index where its final highest elevation is first reached; flat samples at that same elevation after it are not included. A climb always contains at least one increase, so start < end.

Strict climb. From s, the climb continues through every sample that is greater than or equal to the previous sample. It stops at the first sample that is lower than the previous one, or at the end of the list.

Climb with partial descent. The climb proceeds as in the strict version until a sample is lower than P. That sample starts a descent. The descent consists of that sample and every following sample up to, but not including, the first later sample whose elevation is strictly greater than P. Inside the descent the elevation may move up and down, and may return to exactly P, without ending the descent.

Let gain = P - elevations[s] be the net elevation gained so far, and loss = P - m, where m is the lowest elevation inside the descent. The descent is tolerated only if both conditions hold:

1. some sample after the start of the descent is strictly greater than P (the route eventually rises above the previous maximum); and
2. loss is at most 20% of gain, evaluated exactly with integers as 5 * loss <= gain.

If the descent is tolerated, the climb continues from the first sample above P, which becomes the new high point; any later descent is judged the same way against the updated P and gain. If the descent is not tolerated, the climb ends at the index where P was first reached.

Constraints

• 0 <= len(elevations) <= 100000
• -100000 <= elevations[i] <= 100000 for every i
• The result is either [] or [start, end] with 0 <= start < end < len(elevations).

Examples

Example 1

Input:  elevations = [3, 2, 1, 0, 0, 1, 2, 2, 3, 5, 10, 10, 7, 15], tolerate_descent = False
Output: [4, 10]

The first increase is from index 4 (elevation 0) to index 5 (elevation 1), so the climb starts at index 4; index 3 has the same elevation but is not immediately before the rise. The elevation never decreases until index 12, and the highest elevation, 10, is first reached at index 10. With tolerate_descent = True the output is also [4, 10]: the drop from 10 to 7 has loss = 3 against gain = 10 - 0 = 10, and 5 * 3 = 15 > 10, so the descent is not tolerated even though the route later rises to 15.

Example 2

Input:  elevations = [5, 5, 6, 10, 20, 25, 24, 26, 30, 28], tolerate_descent = True
Output: [1, 8]

The climb starts at index 1. The high point 25 is reached at index 5, with gain = 25 - 5 = 20. The dip to 24 has loss = 1, and 5 * 1 = 5 <= 20; index 7 (elevation 26) rises above 25, so the descent is tolerated. The new high point 30 is reached at index 8. The drop to 28 at index 9 is never followed by a sample above 30, so that descent is not tolerated and the climb ends at index 8. With tolerate_descent = False the output is [1, 5].

Example 3

Input:  elevations = [0, 10, 8, 11, 11, 9, 10], tolerate_descent = True
Output: [0, 3]

The dip from 10 to 8 loses exactly 20% of the gain (5 * 2 = 10 <= 10), and index 3 (elevation 11) rises above 10, so it is tolerated. The high point 11 is first reached at index 3; the flat sample at index 4 is not included. The later dip to 9 is small enough (5 * 2 = 10 <= 11), but the route only returns to 10 and never rises above 11, so it is not tolerated and the climb ends at index 3. With tolerate_descent = False the output is [0, 1].

First Climb on an Elevation Route with Optional Tolerated Dips

Hints

1. The start does not depend on the flag: it is decided by the first pair of adjacent samples where the elevation strictly increases.
2. Keep track of the highest elevation reached so far and the index where it was first reached; flat samples at that height never change the end.
3. In the tolerant version a descent is judged as a whole: it lasts until the first sample strictly above the current high point, so its lowest sample can come after the route has returned to exactly that high point.

Approach

Single left-to-right scan. First find s, the smallest index with elevations[s + 1] > elevations[s]; if none exists (fewer than two samples, all flat, or never increasing) return []. Keep base = elevations[s], the current high point P (initially base) and pIdx, the index where P was first reached. Walk i from s + 1: a sample above P becomes the new P at index i; a sample equal to P changes nothing, so flat samples at the peak never move the end. Invariant: while climbing, the previous sample always equals P (the climb only continues through samples that are >= P, and after a tolerated descent it resumes exactly at the new high point), so 'lower than the previous sample' and 'lower than P' are the same test. In the strict version that test stops the climb. In the tolerant version it opens a descent: scan j forward while elevations[j] <= P, tracking the minimum m over the whole descent, including rebounds that return exactly to P. If j runs off the end, no sample exceeds P and the descent is rejected. Otherwise it is tolerated iff 5 * (P - m) <= P - base, using the current P and gain; on success elevations[j] becomes the new P at index j and scanning resumes at j + 1, on failure the climb ends. The answer is [s, pIdx]: pIdx is always the first index at which the final high point was reached, which is exactly the source's end rule. Each index is visited once by either i or j, so the scan is linear. Edge cases: empty or single-sample input, all-flat or non-increasing input, a climb running non-decreasing to the last index with a flat final peak, a descent that only returns to P, the exact boundary 5 * loss == gain (tolerated), and a large dip followed by a higher later climb (rejected, so the first climb's end is kept). All values fit in 32-bit integers (gain <= 200000, 5 * loss <= 1000000).

• Time complexity: O(n)
• Space complexity: O(1)