Katkat
Back

Answer suffix maximum-frequency queries

MicrosoftSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to optimize range frequency queries using precomputation and efficient data structures, specifically focusing on suffix-based constraints.

Problem Statement

Given an integer array nums of length n, you need to answer q queries. Each query is provided as a pair (i, k), where i is the starting index (0 <= i < n) and k is a threshold frequency. For each query, return the smallest value x such that the frequency of x in the suffix nums[i...n-1] is at least k. If no such value exists, return -1.

Function Signature

def solve_suffix_queries(nums: List[int], queries: List[Tuple[int, int]]) -> List[int]:

Constraints

  • 1 <= n <= 10^5
  • 1 <= q <= 10^5
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= n

Example

Input: nums = [1, 2, 1, 3, 2, 1] queries = [(0, 3), (2, 2), (4, 1)]

Output: [1, 1, 2]

Explanation:

  • Query (0, 3): In suffix [1, 2, 1, 3, 2, 1], 1 appears 3 times. Smallest value with freq >= 3 is 1.
  • Query (2, 2): In suffix [1, 3, 2, 1], 1 appears 2 times. Smallest value with freq >= 2 is 1.
  • Query (4, 1): In suffix [2, 1], 2 appears 1 time and 1 appears 1 time. Smallest value with freq >= 1 is 1. Wait, looking at the suffix [2, 1], both 1 and 2 have freq 1. Smallest is 1. (Correction: If nums[4:] is [2, 1], both 1 and 2 appear. Smallest is 1.)

Hints

Hint 1

Consider storing the indices of every occurrence for each unique number in a dictionary or list of lists.

Hint 2

For a suffix starting at `i`, the frequency of a number `v` is the count of its occurrences at indices greater than or equal to `i`.

Hint 3

Use binary search (specifically `bisect_right` or `bisect_left`) on the stored index lists to quickly calculate the frequency of any number `v` in the suffix starting at `i`.

Follow-up questions

  • How would you optimize the search if the value range of `nums` is significantly larger than `n`?
  • Can you solve this offline if queries arrive in a different order, and would that improve performance?
  • What is the time complexity of your solution, and how would you modify the data structures if the array `nums` was updated dynamically (e.g., changing an element at index `i`)?