Count Occurrences of Each Suffix Maximum
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Given an integer array `nums` and query indices, return for each query index `i`
how many times the maximum value of suffix `nums[i:]` occurs within that suffix.
### Constraints & Assumptions
- `1 <= len(nums) <= 500,000`.
- There are at most 500,000 queries.
- Every query index is valid.
- Array values are 32-bit signed integers and may repeat.
### Clarifications
- The maximum is recomputed conceptually for each suffix, not for the entire array.
- Repeated query indices should return repeated answers.
- Preprocessing the array once is allowed.
### Examples
```text
nums = [7, 5, 7, 2, 7]
queries = [0, 1, 2, 3, 4]
output = [3, 2, 2, 1, 1]
```
### Hints
```hint Scan from the end
The suffix maximum changes only when a larger value is encountered while moving right to left.
```
```hint Carry both value and count
When the next value equals the current suffix maximum, increment its occurrence count.
```
Quick Answer: Preprocess an integer array from right to left so each suffix query returns how many times that suffix's maximum value occurs, including repeated query indices.
Given a nonempty integer array nums and a list of valid query indices, return for every query index i how many times the maximum value of suffix nums[i:] occurs within that suffix. Return answers in query order. Repeated query indices must produce repeated answers, and array values may repeat.
Constraints
- 1 <= len(nums) <= 500000.
- 0 <= len(queries) <= 500000.
- Every query index is valid for nums.
- Every array value is a signed 32-bit integer.
- Repeated values and repeated query indices are allowed.
Examples
Input: ([7, 5, 7, 2, 7], [0, 1, 2, 3, 4])
Expected Output: [3, 2, 2, 1, 1]
Explanation: Each answer counts the maximum value within that query's suffix.
Input: ([42], [0, 0])
Expected Output: [1, 1]
Explanation: The one-element suffix has one maximum, and repeated queries repeat the answer.
Hints
- Scan from right to left because every step extends the next suffix by one value.
- Carry both the current suffix maximum and how many times it has appeared.