Introduction

This problem asks for the longest contiguous range whose two endpoints are also the maximum values inside that range. That means the endpoints must be equal, and nothing between them can be larger. A brute-force search is easy to write, but it is too slow for large arrays. The interesting part is that you can get to near-linear behavior by combining a monotonic stack with per-value grouping.

Rewrite the Condition in a More Useful Form

For a range from index i to j to be valid:

• 'a[i] == a[j]'
• every value in a[i..j] is less than or equal to a[i]

That second statement means there is no element greater than the endpoint value anywhere inside the interval. So if the endpoint value is v, the valid range must live entirely inside a maximal segment bounded by elements greater than v.

That observation is the key to the faster solution.

A Quadratic Baseline Helps Clarify Correctness

Before optimizing, it is useful to keep a simple baseline implementation for testing.

1def longest_range_quadratic(arr):
2    best = (-1, -1, 0)
3    n = len(arr)
4
5    for i in range(n):
6        current_max = arr[i]
7        for j in range(i, n):
8            current_max = max(current_max, arr[j])
9            if arr[i] == arr[j] and current_max == arr[i]:
10                length = j - i + 1
11                if length > best[2]:
12                    best = (i, j, length)
13
14    return best

This is easy to trust, but it is O(n^2) and too slow when n grows.

Find the Maximal Segment for Each Position

Now switch to the faster view. For each index, compute the nearest position to the left with a strictly greater value, and the nearest position to the right with a strictly greater value. Inside those boundaries, the current value is never exceeded.

You can compute both arrays with monotonic decreasing stacks in linear time.

1def greater_boundaries(arr):
2    n = len(arr)
3    left = [-1] * n
4    right = [n] * n
5
6    stack = []
7    for i, value in enumerate(arr):
8        while stack and arr[stack[-1]] <= value:
9            stack.pop()
10        left[i] = stack[-1] if stack else -1
11        stack.append(i)
12
13    stack.clear()
14    for i in range(n - 1, -1, -1):
15        value = arr[i]
16        while stack and arr[stack[-1]] < value:
17            stack.pop()
18        right[i] = stack[-1] if stack else n
19        stack.append(i)
20
21    return left, right

The exact stack condition matters because we want boundaries formed by strictly greater values, not by equal values.

Group Equal Values by Their Valid Segment

If two equal endpoints share the same greater-value boundaries, then the whole stretch between them is safe: nothing inside is larger than that value. So the problem reduces to finding, for each pair of boundaries and each value, the first and last occurrence inside that segment.

1def longest_endpoint_max_range(arr):
2    if not arr:
3        return (-1, -1, 0)
4
5    left, right = greater_boundaries(arr)
6    first_seen = {}
7    best = (0, 0, 1)
8
9    for i, value in enumerate(arr):
10        key = (value, left[i], right[i])
11
12        if key not in first_seen:
13            first_seen[key] = i
14        else:
15            start = first_seen[key]
16            length = i - start + 1
17            if length > best[2]:
18                best = (start, i, length)
19
20    return best
21
22
23print(longest_endpoint_max_range([5, 1, 3, 5, 2, 5, 4]))

This works in linear time after the boundary computation because each index is processed a constant number of times.

Why the Grouping Logic Works

Suppose an index with value v has nearest greater boundaries L and R. Then every position between L + 1 and R - 1 has value less than or equal to v. If two occurrences of v lie in that same open interval, the range between them automatically satisfies the maximum-endpoint rule.

So the longest valid range for that value inside that segment is simply from the first occurrence to the last occurrence. That is why the hash key uses:

• the value itself
• the left greater boundary
• the right greater boundary

Without the boundaries, equal values from different segments would be merged incorrectly.

Keep the Quadratic Version for Tests

When you optimize array logic, a slow correctness oracle is incredibly useful. Randomized testing makes it easy to compare the fast implementation with the simple one.

1import random
2
3for _ in range(200):
4    arr = [random.randint(1, 6) for _ in range(20)]
5    assert longest_endpoint_max_range(arr)[2] == longest_range_quadratic(arr)[2]

That kind of test catches the subtle boundary mistakes that are common with monotonic-stack algorithms.

Common Pitfalls

The most common mistake is forgetting that the endpoints must be equal. Another is using greater-or-equal boundaries instead of strictly greater boundaries and accidentally splitting valid segments. Teams also often optimize without keeping a brute-force oracle, which makes stack-condition bugs much harder to detect.

Summary

• A valid range needs equal endpoints and no larger value inside.
• The nearest strictly greater elements define the maximal safe segment for each value.
• A monotonic stack can compute those boundaries in linear time.
• Grouping equal values by shared boundaries yields a near-linear full solution.
• Keep a quadratic version for testing, because boundary logic is easy to get subtly wrong.