FastPrepSuffix Maximum Frequency Queries

Suffix Maximum Frequency Queries

Microsoft logoMicrosoft● EasyFULLTIMEPHONE SCREEN
Learn

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

See Microsoft hiring insights
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…