Compute subarray span for each element
Company: Molocoads
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given an integer array `nums` of length `n`.
For each index `i` (`0 <= i < n`), define `ans[i]` as the **maximum possible length** of a contiguous subarray `nums[l..r]` such that:
- `l <= i <= r` (the subarray contains index `i`), and
- the **maximum element** in `nums[l..r]` is **exactly** `nums[i]`.
In other words, starting from position `i`, you can expand to the left and right as long as you do not include any element strictly greater than `nums[i]`. Among all such subarrays that still contain index `i`, `ans[i]` is the maximum possible length.
Return the array `ans` of length `n`.
You may assume `n` can be large (e.g., up to around `2 * 10^5`), so you should design an efficient algorithm.
**Example 1**
```text
Input: nums = [1, 5, 4, 3, 6]
Output: ans = [1, 4, 2, 1, 5]
Explanation:
- i = 0, nums[0] = 1:
Any subarray containing index 0 that goes past index 0 includes an element > 1, so only [1] works ⇒ ans[0] = 1.
- i = 1, nums[1] = 5:
We can take subarray [1, 5, 4, 3]. Its max = 5 and includes index 1 ⇒ length 4.
- i = 2, nums[2] = 4:
If we extend left to index 1, max becomes 5, which is > 4 (not allowed). Right we can go to index 3.
So best subarray is [4, 3] ⇒ length 2.
- i = 3, nums[3] = 3:
Any extension left/right hits a value > 3, so only [3] ⇒ length 1.
- i = 4, nums[4] = 6:
We can take the whole array [1, 5, 4, 3, 6]; its max is 6 ⇒ length 5.
```
**Example 2**
```text
Input: nums = [1, 2, 3, 4, 5]
Output: ans = [1, 2, 3, 4, 5]
Explanation:
For each i, we can expand from index 0 up to i, since the array is strictly increasing.
Thus ans[i] = i + 1.
```
---
**Follow-up (circular array):**
Now suppose `nums` is **circular**: index `0` comes after index `n - 1`. A contiguous subarray on this circle may wrap around the end of the array (e.g., `[nums[3], nums[4], nums[0], nums[1]]` when `n = 5`).
For each index `i`, compute the maximum possible length of a **circular contiguous segment** such that:
- the segment contains index `i`, and
- the maximum element on that segment is exactly `nums[i]`.
Return the resulting array for the circular case as well, or describe how to modify your algorithm to handle the circular version.
Quick Answer: This question evaluates array reasoning and competency in determining span-like influence regions under maximum-value constraints for each element, including handling circular-array extensions and scalability considerations.
For each index, return the longest subarray containing it with no element greater than nums[i].
Examples
Input: ([1, 5, 4, 3, 6],)
Expected Output: [1, 4, 2, 1, 5]
Explanation: Prompt example.
Input: ([1, 2, 3, 4, 5],)
Expected Output: [1, 2, 3, 4, 5]
Explanation: Increasing array.
Input: ([2, 2, 2],)
Expected Output: [3, 3, 3]
Explanation: Equal values can be included.
Input: ([],)
Expected Output: []
Explanation: Empty array.
Hints
- Find previous and next strictly greater elements with monotonic stacks.