Reign of Every Element
Updated
Problem statement
You are given an integer array nums of length n. Positions are 1-based, so the first element is at position 1.
The reign of the element at position i is the longest run of neighbouring positions [L, R] with L <= i <= R in which no element is larger than nums[i]. Equal elements do not end a reign; only a strictly larger element does.
Return an array of n pairs, where the pair at index i - 1 is [L, R], the reign of the element at position i.
Function
reignOfEachElement(nums: int[]) → int[][]Examples
Example 1
nums = [8,9,5,4,2,6,7,1,5]return = [[1,1],[1,9],[3,5],[4,5],[5,5],[3,6],[3,9],[8,8],[8,9]]Positions are 1-based. The 9 at position 2 is the largest value, so it reigns over the whole array, [1, 9]. The 7 at position 7 can reach left to position 3, because the 9 at position 2 is larger, and right to the end, so its reign is [3, 9]. The 5 at position 3 stops at the 9 on its left and at the 6 on its right, so its reign is [3, 5]. The 5 at position 9 stops at the 7 on its left, so its reign is [8, 9].
Example 2
nums = [1,5,4,3,6]return = [[1,1],[1,4],[3,4],[4,4],[1,5]]The 5 at position 2 is larger than everything before the 6, so its reign is [1, 4]. The 4 at position 3 stops at the 5 on its left and the 6 on its right, giving [3, 4]. The 6 is the largest value, so its reign is [1, 5].
Example 3
nums = [2,7,7,1]return = [[1,1],[1,4],[1,4],[4,4]]An equal value does not end a reign. The 7 at position 2 can include the other 7 and the 1 after it, so its reign is [1, 4]. The 7 at position 3 can include the first 7 and the 2 before it, so its reign is also [1, 4].
Constraints
1 <= nums.length <= 2000-10^9 <= nums[i] <= 10^9
More Nutanix Onsite Interview questions
- Design Hit CounterONSITE INTERVIEW · Seen Oct 2026
- Peak Process MemoryONSITE INTERVIEW · Seen Aug 2026
- Minimum Operations to Transform ArrayONSITE INTERVIEW · Seen Jun 2026
- Count Connected Components in an Undirected GraphONSITE INTERVIEW · Seen Aug 2025
- LRU CacheONSITE INTERVIEW · Seen Aug 2025
- Running Median of a Multilevel Linked List in Level OrderONSITE INTERVIEW · Seen Aug 2025
- Custom Array IteratorONSITE INTERVIEW · Seen Dec 2024
- Collapse Runs of Repeated CharactersONSITE INTERVIEW · Seen Nov 2022
- Anagram Words in a SentenceONSITE INTERVIEW · Seen Apr 2022
- Sudoku SolverONSITE INTERVIEW · Seen Feb 2022
Similar questions at other companies
- Compress Editor Actions into Operational Transform OperationsReplit · OA · PHONE SCREEN · ONSITE INTERVIEW
- Flatten a Mixed JSON ListNike, Inc. · ONSITE INTERVIEWNike, Inc. interview questions
- Fountain SafetyGoogle · ONSITE INTERVIEWGoogle interview questions
- Trace Events from Stable Whole-Stack StatesAnthropic · ONSITE INTERVIEWAnthropic interview questions
- Next Smaller Ticket PriceAmazon · ONSITE INTERVIEW
- Next Greater Element to the RightTekion · ONSITE INTERVIEWTekion interview questions
- Surviving Balls after Directional CollisionsSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Daily TemperatureseBay · ONSITE INTERVIEWeBay interview questions
- Asteroid CollisionAdobe · ONSITE INTERVIEWAdobe interview questions
- Most Frequent Call Path in Interleaved LogsRoblox · ONSITE INTERVIEWRoblox interview questions