Find longest segment with endpoints > interior

Given an integer array nums, find the length of the longest contiguous segment [i..j] (j−i+1 ≥ 2) such that both endpoints are strictly greater than every element strictly between them; i.e., max(nums[i+1..j−1]) < min(nums[i], nums[j]). Return only the length. Examples: nums=[1,3,2,4,1] → longest is [3,2,4], length 3; nums=[4,2,6] → [4,2,6], length 3. Brute force is not allowed—design an algorithm faster than O(n^ 2) and provide complexity analysis.

Longest Segment With Endpoints Greater Than Interior

Given an integer array nums, find the length of the longest contiguous segment [i..j] (with j - i + 1 >= 2) such that BOTH endpoints are strictly greater than every element strictly between them. Formally, the segment is valid when max(nums[i+1..j-1]) < min(nums[i], nums[j]) (an empty interior is treated as having maximum -infinity, so every adjacent pair of length 2 is valid). Return only the length of the longest valid segment, or 0 if no segment of length >= 2 exists.

Examples:

• nums = [1, 3, 2, 4, 1] -> the segment [3, 2, 4] is valid (interior max 2 < min(3, 4) = 3), length 3.
• nums = [4, 2, 6] -> the whole array is valid (interior max 2 < min(4, 6) = 4), length 3.

Brute force is not allowed: design an algorithm faster than O(n^2) and analyze its complexity.

Constraints

• 2 <= nums.length is typical, but the function must also handle length 0 and 1 by returning 0.
• Elements may be negative, zero, or positive integers, and duplicates are allowed.
• A valid segment requires j - i + 1 >= 2; adjacent pairs (empty interior) are always valid.
• Required time complexity is strictly better than O(n^2); the reference is O(n).

Hints

1. Any adjacent pair (length 2) is always valid because its interior is empty, so the answer is at least 2 whenever the array has >= 2 elements. The interesting work is extending past adjacent pairs.
2. A pair (i, j) is valid exactly when no element strictly between them is >= min(nums[i], nums[j]). This 'nothing taller in between' condition is the classic signature of a monotonic stack of strictly decreasing values.
3. Sweep j left to right with a strictly decreasing stack. While the top is smaller than nums[j], pop it and record the segment length to j (those are valid because everything between was already smaller than the popped value). Then the surviving top (>= nums[j]) also pairs with j.
4. Watch ties: when the surviving top equals nums[j], pop it after recording, otherwise a later larger element could form an invalid segment whose interior contains an equal-valued element (the inequality must be strict).