Frontend School

Range Longest Consecutive Identical Subarray

DSA
hard

Range Longest Consecutive Identical Subarray

Hard
Segment Tree
Data Structures
Arrays
Range Query
Point Update

Overview

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.

What you need to do / Task

Implement a SegmentAnalyzer class that supports the following operations:

  1. Constructor: Initializes the analyzer with an initialArray representing the current state of the event stream.
  2. update(index, value): Changes the event at a specific index in the stream to a new value.
  3. query(left, right): Returns the length of the longest consecutive subarray containing identical elements within the inclusive range [left, right].

Input & output

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).
  • Returns: An integer representing the maximum length of a consecutive subarray of identical elements within the specified [left, right] range.

Clarifications

  • The initialArray will always be non-empty.
  • All indices (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

1

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. Initialize with [1,1,2,2,2,3,3,1]. Longest is '2,2,2' (length 3).
  2. query(0,7) returns 3.
  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).
  4. query(5,7) for [3,3,3] returns 3.
  5. query(0,7) for [1,1,2,2,2,3,3,3] returns 3.
2

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:

  1. Initialize with [5,5,5,5,1,1,1]. Longest is '5,5,5,5' (length 4).
  2. update(4,5) changes array to [5,5,5,5,5,1,1]. Longest is '5,5,5,5,5' (length 5).
  3. query(0,6) for [5,5,5,5,5,1,1] returns 5.
  4. update(0,1) changes array to [1,5,5,5,5,1,1]. Longest is '5,5,5,5' (length 4).
  5. query(0,6) for [1,5,5,5,5,1,1] returns 4.
3

Example 3

Input:

operations = ["SegmentAnalyzer","query","update","query"], params = [[[10]],[0,0],[0,20],[0,0]]

Output:

[null,1,null,1]

Note:

  1. Initialize with [10].
  2. query(0,0) returns 1.
  3. update(0,20) changes array to [20].
  4. query(0,0) returns 1.

Constraints

Constraints & assumptions

  • N: Length of initialArray, 1 <= N <= 10^5
  • Q: Total number of update and query operations, 1 <= Q <= 10^5
  • initialArray[i], value: -10^9 <= initialArray[i], value <= 10^9
  • Time Complexity: O((N + Q) log N) for all operations combined.
  • Space Complexity: O(N) for the segment tree.

What interviewers evaluate

  • Correctness: The solution must correctly handle all update and query operations, including tricky merge cases.
  • Efficiency: Adherence to the specified time and space complexity requirements, leveraging the Segment Tree data structure effectively.
  • Code Structure & Readability: Clear and modular code, appropriate use of helper functions (e.g., for merging segment tree nodes).
  • Edge Case Handling: Correctly managing base cases for segment tree leaves and handling queries that span across node boundaries.

Loading editor...