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

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

Expected Output: 2

Explanation: Strictly decreasing: only adjacent pairs are valid, giving length 2.

Input: ([3, 1, 1, 3],)

Expected Output: 4

Explanation: Both ends are 3 and the interior max is 1 < 3, so the entire array is valid.

Input: ([],)

Expected Output: 0

Explanation: Empty array has no subarray; answer is 0.

Input: ([42],)

Expected Output: 1

Explanation: A single element is a valid length-1 subarray.

Input: ([-4, -4, 3, -2],)

Expected Output: 2

Explanation: [-4, -4] cannot extend through the second -4 (equal, not strictly smaller); longest valid window is an adjacent pair of length 2.

Input: ([10, 5, 6, 8, 10, 2, 9],)

Expected Output: 5

Explanation: [10, 5, 6, 8, 10] has ends 10, 10 and interior max 8 < 10, giving length 5.

Input: ([7, 7, 7, 7],)

Expected Output: 2

Explanation: Any length-3 window contains an interior 7 which is not strictly less than the 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.

Quick Overview

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.