Compute subarray span for each element
Problem Description
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 indexi), and- the maximum element in
nums[l..r]is exactlynums[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
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
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.
AI interview prep
Core dilemma
The central engineering conflict is efficiently determining the maximum valid expansion boundaries (leftmost and rightmost indices) for each element `nums[i]` such that `nums[i]` remains the maximum within that segment, across a large array, and then extending this logic to a circular array while maintaining optimal time and space complexity.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Compute subarray span for each element
Problem Description
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 indexi), and- the maximum element in
nums[l..r]is exactlynums[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
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
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.