FastPrep
Problem · Array

Suffix Maximum Frequency Queries

Learn this problem
● EasyMicrosoft logoMicrosoftFULLTIMEPHONE SCREEN
See Microsoft hiring insights

Problem statement

You are given a nonempty integer array nums and an array of zero-based query indices queries.

For each query index i, consider the suffix nums[i..nums.length - 1]. Find the maximum value in that suffix and count how many times that maximum occurs within the same suffix.

Return the counts in the original order of queries. Repeated query indices are answered independently.

Function

suffixMaximumFrequencies(nums: int[], queries: int[]) → int[]

Examples

Example 1

nums = [7,5,7,2,7]queries = [0,1,2,3,4]return = [3,2,2,1,1]

At index 0, the suffix maximum 7 appears three times. At indices 1 and 2, it appears twice. The final two suffixes each contain their maximum once.

Example 2

nums = [4,4,1,4]queries = [1,2,3]return = [2,1,1]

The suffix beginning at 1 contains two copies of its maximum 4. The suffixes beginning at 2 and 3 contain only one copy of their respective maxima.

Example 3

nums = [-3,-1,-1,-2]queries = [0,1,3]return = [2,2,1]

Negative values follow the same rule. The maximum of the first two queried suffixes is -1, which occurs twice; the last suffix contains only -2.

Constraints

  • 1 ≤ nums.length ≤ 200000.
  • 1 ≤ queries.length ≤ 200000.
  • -10^9 ≤ nums[i] ≤ 10^9.
  • 0 ≤ queries[i] < nums.length.

More Microsoft problems

drafts saved locally
public int[] suffixMaximumFrequencies(int[] nums, int[] queries) {
    // Write your code here.
}
nums[7,5,7,2,7]
queries[0,1,2,3,4]
expected[3,2,2,1,1]
checking account