How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

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.

Input: []

Expected Output: 0

Explanation: An empty array has no segment of length >= 2, so the answer is 0.

Input: [5]

Expected Output: 0

Explanation: A single element cannot form a segment of length >= 2.

Input: [5, 7]

Expected Output: 2

Explanation: An adjacent pair has an empty interior and is always valid, giving length 2.

Input: [1, 2, 3, 4, 5]

Expected Output: 2

Explanation: Strictly increasing: any segment longer than 2 has an interior element >= the left endpoint, so only adjacent pairs qualify, length 2.

Input: [2, 2, 2, 2]

Expected Output: 2

Explanation: All equal: only adjacent pairs are valid (any longer segment has an interior 2 that is not strictly less than the endpoint 2), so length 2.

Input: [5, 1, 1, 1, 5]

Expected Output: 5

Explanation: Interior max 1 < min(5, 5) = 5, so the entire length-5 array is one valid segment.

Input: [-5, -9, -9, -1]

Expected Output: 4

Explanation: Interior elements are -9 and -9, so interior max -9 < min(-5, -1) = -5; the whole array of length 4 is valid.

Input: [-1, -1, 1, 3, 1]

Expected Output: 2

Explanation: Edge case for ties: [-1, -1, 1] is invalid because interior -1 is not strictly less than the endpoint -1; the longest valid segment is just an adjacent pair, length 2.

Input: [10, 3, 7, 2, 9, 1, 8]

Expected Output: 5

Explanation: The segment [10, 3, 7, 2, 9] has interior max 7 < min(10, 9) = 9, giving length 5; no valid segment is longer.

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).

Quick Overview

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.