Detect runs and answer suffix queries

Given an array of comparable elements a[0..m-1] and an integer N:

1. Write a function that returns the maximum length of any run of consecutive equal elements in a.
2. Follow-up: return true if there exists a run whose length is at least N. Provide time and space complexities.
3. Follow-up: extend the design to support many online suffix-only queries: for each query index i, determine whether the suffix a[i..m-1] contains a run of length at least N. Describe preprocessing, data structures (e.g., prefix/suffix run lengths, segment tree, sparse table), and query/update complexities, and discuss trade-offs.

Part 1: Maximum Length of a Consecutive Equal Run

Given a list of integers nums, a run is a sequence of one or more equal values that appear consecutively. Return the maximum length of any run in the list. If the list is empty, return 0.

Although the original interview prompt referred to comparable elements, this coding version uses integers. Only equality matters.

Constraints

• 0 <= len(nums) <= 2 * 10^5
• -10^9 <= nums[i] <= 10^9
• Only equality comparisons are needed

Examples

Example 1

Input: ([1, 1, 2, 2, 2, 3],)
Output: 3

Explanation: The longest run is [2, 2, 2], which has length 3.

Example 2

Input: ([5],)
Output: 1

Explanation: A single element forms a run of length 1.

Hints

1. Scan from left to right while tracking the current run length and the best run seen so far.
2. When the value changes, reset the current run to 1. Do not forget to account for the final run.

Part 2: Does Any Run Reach Length N?

Given a list of integers nums and an integer n, return True if there exists at least one run of consecutive equal values whose length is at least n. Otherwise return False.

A run is a sequence of equal values appearing next to each other. For example, in [3, 3, 3, 1, 2, 2], the runs have lengths 3, 1, and 2.

Constraints

• 0 <= len(nums) <= 2 * 10^5
• 1 <= n <= 2 * 10^5
• -10^9 <= nums[i] <= 10^9

Examples

Example 1

Input: ([1, 1, 2, 2, 2, 3], 3)
Output: True

Explanation: There is a run [2, 2, 2] of length 3.

Example 2

Input: ([1, 2, 2, 3], 3)
Output: False

Explanation: The longest run has length 2, which is less than 3.

Hints

1. Use the same idea as Part 1, but you can stop early as soon as the current run reaches n.
2. Handle the small boundary case n == 1 separately.

Part 3: Suffix Queries for Runs of Length at Least N

You are given a fixed list of integers nums, a fixed threshold n, and many query indices queries. For each query index i, determine whether the suffix nums[i:] contains a run of consecutive equal values of length at least n.

A run is measured inside the suffix. For example, with nums = [5, 5, 5, 5] and n = 3, query i = 1 should return True because the suffix [5, 5, 5] contains a run of length 3.

Because there can be many queries, you should preprocess once and answer each query quickly. In this fixed-array, fixed-n, suffix-only setting, a simple suffix-based preprocessing is optimal: compute the run length starting at each index, then build a suffix boolean array. This gives O(m) preprocessing and O(1) per query. More general structures like segment trees or sparse tables are useful when queries are more general, and a segment tree is the better choice if updates must be supported, but they are more complex than necessary here.

Constraints

• 0 <= len(nums) <= 2 * 10^5
• 1 <= n <= 2 * 10^5
• 0 <= len(queries) <= 2 * 10^5
• If nums is non-empty, each query index is typically in the range 0 <= queries[i] < len(nums)
• -10^9 <= nums[i] <= 10^9

Examples

Example 1

Input: ([1, 1, 2, 2, 2, 3, 3], 3, [0, 1, 2, 3, 4, 5])
Output: [True, True, True, False, False, False]

Explanation: Only suffixes starting at indices 0, 1, and 2 still contain a run of length at least 3.

Example 2

Input: ([5, 5, 5, 5], 3, [0, 1, 2])
Output: [True, True, False]

Explanation: The suffix at index 1 is [5, 5, 5], which still has a run of length 3.

Hints

1. Compute start_len[i]: the length of the equal-valued run starting at index i. This is easiest to build from right to left.
2. Then compute suffix_has[i]: whether any run of length at least n starts at or after i. Each query becomes a constant-time lookup.