Maximal Range That Each Element Is Maximum In It
01 · Problem
You are given a 0-indexed array nums of distinct integers. For each index i, find the longest contiguous subarray that contains index i and in which nums[i] is the largest element.
Return an array ans of the same length where ans[i] is the length of that subarray. Since each element is trivially the maximum of the subarray consisting of itself, every ans[i] is at least 1.
02 · Examples
nums = [2,8,1,6,3]
[1,5,1,3,1]
2 is blocked by 8 on its right, so only [2]. 8 is the largest, so it covers all 5 elements. 6 is blocked by 8 on its left and reaches the end: [1,6,3] has length 3. 1 and 3 are alone.
nums = [9,6,3]
[3,2,1]
The array is strictly decreasing, so each element extends right to the end but never left: ans[i] = n - i.
nums = [7,3,9]
[2,1,3]
7 extends right over 3 to give length 2, 3 is alone, and 9 covers the whole array.
03 · Constraints
- 011 <= nums.length <= 105
- 021 <= nums[i] <= 105
- 03All values in nums are distinct
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.