Range Longest Consecutive Identical Subarray
As a senior engineer at Freshworks, you're tasked with optimizing a critical monitoring dashboard. This dashboard displays event streams from various services, and users often need to identify periods of sustained, identical activity (e.g., a long sequence of 'ServiceA_Healthy' events, or 'Resource_X_HighUsage' alerts). Detecting such patterns quickly can signify system stability, resource contention, or even anomalies.
Your goal is to implement a data structure that efficiently answers queries about the longest consecutive sequence of identical elements within any given range of the event stream, while also supporting real-time updates to individual event entries.
Implement a SegmentAnalyzer class that supports the following operations:
initialArray representing the current state of the event stream.update(index, value): Changes the event at a specific index in the stream to a new value.query(left, right): Returns the length of the longest consecutive subarray containing identical elements within the inclusive range [left, right].SegmentAnalyzer(initialArray: number[]):
initialArray: An array of numbers representing the initial event stream. Each number signifies an event type or status.update(index: number, value: number): void:
index: The 0-based index of the element to update.value: The new numerical value for the element at index.query(left: number, right: number): number:
left: The 0-based starting index of the query range (inclusive).right: The 0-based ending index of the query range (inclusive).[left, right] range.initialArray will always be non-empty.index, left, right) will be valid and within the bounds [0, N-1], where N is the length of the initialArray.left will always be less than or equal to right in query operations.value can be any integer, including negative numbers.Examples
Example 1
Input:
operations = ["SegmentAnalyzer","query","update","query","query"], params = [[[1,1,2,2,2,3,3,1]],[0,7],[7,3],[5,7],[0,7]]
Output:
[null,3,null,3,3]
Note:
[1,1,2,2,2,3,3,1]. Longest is '2,2,2' (length 3).query(0,7) returns 3.update(7,3) changes array to [1,1,2,2,2,3,3,3]. Longest is now '2,2,2' or '3,3,3' (length 3).query(5,7) for [3,3,3] returns 3.query(0,7) for [1,1,2,2,2,3,3,3] returns 3.Example 2
Input:
operations = ["SegmentAnalyzer","update","query","update","query"], params = [[[5,5,5,5,1,1,1]],[4,5],[0,6],[0,1],[0,6]]
Output:
[null,null,4,null,3]
Note:
[5,5,5,5,1,1,1]. Longest is '5,5,5,5' (length 4).update(4,5) changes array to [5,5,5,5,5,1,1]. Longest is '5,5,5,5,5' (length 5).query(0,6) for [5,5,5,5,5,1,1] returns 5.update(0,1) changes array to [1,5,5,5,5,1,1]. Longest is '5,5,5,5' (length 4).query(0,6) for [1,5,5,5,5,1,1] returns 4.Example 3
Input:
operations = ["SegmentAnalyzer","query","update","query"], params = [[[10]],[0,0],[0,20],[0,0]]
Output:
[null,1,null,1]
Note:
[10].query(0,0) returns 1.update(0,20) changes array to [20].query(0,0) returns 1.Constraints
N: Length of initialArray, 1 <= N <= 10^5Q: Total number of update and query operations, 1 <= Q <= 10^5initialArray[i], value: -10^9 <= initialArray[i], value <= 10^9O((N + Q) log N) for all operations combined.O(N) for the segment tree.update and query operations, including tricky merge cases.Loading editor...