Katkat
Back

Count Occurrences of Each Suffix Maximum

MicrosoftSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to use a monotonic stack and a hash map (or frequency array) to efficiently answer suffix queries about the occurrences of the maximum value.

Problem Statement

Given an array nums of n integers, we define a "suffix maximum" for any index i as the maximum value found in the subarray nums[i...n-1]. Your goal is to process the array such that you can answer queries in O(1) time. A query consists of an index i, and the result should be the number of times that specific suffix maximum appears within the subarray nums[i...n-1].

Function Signature

def get_suffix_max_counts(nums: List[int]) -> List[int]:
    # Returns an array where the i-th element is the count 
    # of the maximum value in nums[i...n-1].

Examples

Example 1: Input: nums = [3, 1, 3, 2, 3] Output: [3, 1, 2, 1, 1] Explanation:

  • Index 0: Suffix [3, 1, 3, 2, 3], max is 3, occurs 3 times.
  • Index 1: Suffix [1, 3, 2, 3], max is 3, occurs 2 times.
  • Index 2: Suffix [3, 2, 3], max is 3, occurs 2 times.
  • Index 3: Suffix [2, 3], max is 3, occurs 1 time.
  • Index 4: Suffix [3], max is 3, occurs 1 time.

Constraints

  • 1 <= n <= 10^5
  • -10^9 <= nums[i] <= 10^9

Edge Cases

  • Array with all identical elements.
  • Array with strictly increasing or decreasing elements.
  • Single element array.

Hints

Hint 1

Iterate through the array from right to left to keep track of the current maximum and its frequency seen so far.

Hint 2

When you encounter a value greater than the current maximum, reset the frequency count to 1 and update the maximum.

Hint 3

If the current value equals the current maximum, increment the frequency count.

Follow-up questions

  • How would you modify your solution if the queries were dynamic, meaning the array values could change after some queries?
  • What is the space complexity of your solution, and can it be optimized if we don't need to store all results upfront?
  • How would you handle the case where the values in the array are extremely large, potentially exceeding standard integer limits?