Find longest segment with endpoints > interior
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
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.
Quick Answer: This question evaluates algorithmic design and array-processing skills, specifically reasoning about subarray endpoint vs interior relationships, range comparisons, and designing solutions with subquadratic time and space complexity.
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).
Examples
Input: [1, 3, 2, 4, 1]
Expected Output: 3
Explanation: The segment [3, 2, 4] has interior max 2 < min(3, 4) = 3, so it is valid with length 3. No valid segment is longer.
Input: [4, 2, 6]
Expected Output: 3
Explanation: The whole array [4, 2, 6] has interior max 2 < min(4, 6) = 4, so length 3.
Hints
- 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.
- 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.
- 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.
- 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).