FastPrepFastPrep
Problem Brief

Segment Queries

INTERNNEW GRADOA
See Tiktok online assessment and hiring insights

There are 4 arrays of data. The arrays cat[n] and cnt[n] are each of n integers, and cat[i] relates to cnt[i]. These represent a category and count at each index. There are also two arrays of integers that represent q queries. The arrays l[q] and r[q] contain 1-based indices for the left and right ends of subarrays to consider in cat and cnt.

Process the queries in order. Create an array of q values where answer i relates to query i.

For each query i:

  • Within the subarrays in cat and cnt, determine the maximum cnt for each cat.
  • Store the sum of these maxima as the answer to the query.
  • Clear the cnt values in the range.

After all queries are processed, return the answer array.

1Example 1

Input
cat = [1, 2, 1, 1, 3], cnt = [5, 3, 4, 5, 2], l = [1, 1], r = [3, 5]
Output
[8, 7]
Explanation
For the first query, the subarrays are cat[1..3] = [1, 2, 1] and cnt[1..3] = [5, 3, 4]. The maximum count for each category is 5 for category 1 and 3 for category 2. The sum of these maxima is 5 + 3 = 8. The cnt values in the range are cleared to [0, 0, 0, 5, 2]. For the second query, the subarrays are cat[1..5] = [1, 2, 1, 1, 3] and cnt[1..5] = [0, 0, 0, 5, 2]. The maximum count for each category is 5 for category 1 and 2 for category 3. The sum of these maxima is 5 + 2 = 7. The cnt values in the range are cleared to [0, 0, 0, 0, 0]. The answer array is [8, 7]. I am not 100% sure about the output and explanation. If you find anything wrong, pls don't hesitate to tell Groot in our Discord server. Many thanks in advance~ Cheers, Groot 🛵
public int[] segmentQueries(int[] cat, int[] cnt, int[] l, int[] r) {
    // write your code here
}
Input

cat

[1, 2, 1, 1, 3]

cnt

[5, 3, 4, 5, 2]

l

[1, 1]

r

[3, 5]

Output

[8, 7]

Sign in to submit your solution.