We are given an integer array (Arr) and an array of queries. ↵
↵
A query will be one of the two types below. ↵
↵
Type 1, format: [1, idx, val], where you are to update Arr[idx]=val, and we do not need to return anything↵
↵
Type 2, format [2, left_idx, right_idx], where you are to count the number of elements with odd frequency within the left_idx and right_idx inclusive, and we return the count. The index is 1-based indexing↵
↵
Examples:↵
↵
Arr = [1,3,5,5]↵
↵
queries = [[2,1,4], [1,4,2], [2,1,4]] ↵
↵
The output should be [2, 4]↵
↵
For queries[0], which is [2,1,4], the frequency of the elements is {1:1, 3:1, 5:2} so there are 2 elements (1,3) with odd frequency and the output for this query is 2.↵
↵
queries[1] changes Arr from [1,3,5,5] to [1,3,5,4], and there will be no output.↵
↵
queries[2], which is [2,1,4], the frequency of the elements is {1:1, 3:1, 5:1, 4:1}, and there are 4 elements (1,3,5,4) with odd frequency and the output will be 4.↵
↵
Hence the overall output is [2,4].↵
↵
I tried solving this question by doing Type 1 query in O(1) (just updating the array) time and Type 2 query in O(n) time (iterating from left to right to get the answer), but this failed the time limit given.↵
↵
I was wondering if there is any solution with a better time complexity.↵
↵
A query will be one of the two types below. ↵
↵
Type 1, format: [1, idx, val], where you are to update Arr[idx]=val, and we do not need to return anything↵
↵
Type 2, format [2, left_idx, right_idx], where you are to count the number of elements with odd frequency within the left_idx and right_idx inclusive, and we return the count. The index is 1-based indexing↵
↵
Examples:↵
↵
Arr = [1,3,5,5]↵
↵
queries = [[2,1,4], [1,4,2], [2,1,4]] ↵
↵
The output should be [2, 4]↵
↵
For queries[0], which is [2,1,4], the frequency of the elements is {1:1, 3:1, 5:2} so there are 2 elements (1,3) with odd frequency and the output for this query is 2.↵
↵
queries[1] changes Arr from [1,3,5,5] to [1,3,5,4], and there will be no output.↵
↵
queries[2], which is [2,1,4], the frequency of the elements is {1:1, 3:1, 5:1, 4:1}, and there are 4 elements (1,3,5,4) with odd frequency and the output will be 4.↵
↵
Hence the overall output is [2,4].↵
↵
I tried solving this question by doing Type 1 query in O(1) (just updating the array) time and Type 2 query in O(n) time (iterating from left to right to get the answer), but this failed the time limit given.↵
↵
I was wondering if there is any solution with a better time complexity.↵
