Find longest segment with dominant ends
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
##### Question
Given an integer array nums, find and return the length of the longest contiguous subarray such that the first and last elements of the subarray are strictly greater than every element that appears between them. Brute-force enumeration of all subarrays is not acceptable; design an algorithm that avoids TLE on large inputs.
Quick Answer: This question evaluates algorithmic problem-solving with arrays and complexity-aware design, testing skills in efficient subarray identification, boundary reasoning, and performance analysis within the Coding & Algorithms domain.
Given an integer array `nums`, return the length of the longest contiguous subarray such that its first and last elements are both strictly greater than every element that appears strictly between them.
Formally, a subarray `nums[i..j]` is valid when `min(nums[i], nums[j]) > max(nums[i+1..j-1])`. Subarrays of length 1 or 2 have no interior elements and are always valid. Return the length of the longest valid subarray (0 for an empty array).
Brute-force enumeration of all subarrays is not acceptable — design an algorithm that runs in linear or near-linear time and avoids TLE on large inputs.
Example 1:
Input: nums = [3, 1, 1, 3]
Output: 4
Explanation: The whole array is valid — both ends are 3 and the interior max is 1 < 3.
Example 2:
Input: nums = [7, 7, 7, 7]
Output: 2
Explanation: Any length-3 window has an interior 7 which is not < 7, so only adjacent pairs are valid.
Example 3:
Input: nums = [10, 5, 6, 8, 10, 2, 9]
Output: 5
Explanation: nums[0..4] = [10,5,6,8,10] has ends 10,10 and interior max 8 < 10.
Constraints
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- Return 0 for an empty array.
- Brute-force O(n^2) / O(n^3) enumeration will TLE on large inputs.
Examples
Input: ([2, 1, 4, 7, 3, 5],)
Expected Output: 3
Explanation: [7, 3, 5] has ends 7 and 5 with interior 3 < 5; length 3 is the longest valid window.
Input: ([1, 2, 3, 4, 5],)
Expected Output: 2
Explanation: Strictly increasing: no interior element is smaller than both ends, so only adjacent pairs (length 2) are valid.
Hints
- A subarray is valid iff min(firstElement, lastElement) > max(interiorElements). Length-1 and length-2 subarrays are always valid.
- Think about a monotonic (non-increasing) stack of indices. When you process index j, every element strictly smaller than nums[j] that is currently on the stack can serve as a left end paired with j.
- When you pop a strictly smaller element i for the current j, everything between i and j was already popped, so it is strictly less than both nums[i] and nums[j] — the pair (i, j) is valid.
- After popping, the new stack top (>= nums[j]) also forms a valid pair with j. For equal values, keep only the rightmost occurrence so a later element can't pair across an equal element sitting in the interior.