Maximum Subarray Sum Queries - ll

Hard
0/120
Average time to solve is 30m
profile
Contributed by
8 upvotes
Asked in company
Walmart

Problem statement

You are given an array “Arr” of size ‘N’. You are given ‘Q’ queries. There are two types of queries and they are defined as follows:

1.  “index” “value” in this query, set the value of arr[index] to value.
2.  ‘L’ ‘R’ in this query, you must find i and j such that L is less than or equal to i, and j is less than or equal to R, and i is not equal to j, such that the sum of arr[i] and arr[j] is maximized. Then, print the sum of arr[i] and arr[j].
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘Q’ denoting the number of elements in the array and number of queries respectively.

The second line of each test case contains ‘N’ space-separated integers, denoting the elements in the array “Arr”.

The next ‘Q’ lines contain three space-separated integers.
If the first integer is 1, Denote type 1 query, next 2 space-separated integers denote “index” and “value”.
If the first integer is 2, Denote type 2 query, next 2 space-separated integers denote ‘L’ and ‘R’.
Output Format : 
For each test case, return the list of integers, where the ith of them denotes the answer of the ith type 2 query.

Output for each test case will be printed in a new line.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= N <= 100000
1 <= Q <= 100000    
1 <= Arr[i], value < 10^9
1 <= index, L < R <= N

Where ‘T’ denotes the number of test cases,
‘N’ denotes the number of elements in the array,
‘Q’ denotes the number of queries,
“value” and “index” denote index and value in the query of type 1,
‘L’ and ‘R’ denote the range limits in the query of type 2.

Time Limit: 1 sec
Sample Input 1 :
2
5 3
1 2 3 4 5
2 2 4
1 2 6
2 2 4
4 3
3 2 3 1
2 2 4
1 3 1
2 2 4
Sample Output 1:
7
10
5
3

Explanation for Sample 1:

For the 1st test case:
In the first query, in the range [2, 4], i = 3 and j = 4 gives the maximum value that is 7.
In the second query we will set value at index 2 (1 based index) in the “Arr” to 6.
In the third query, in the range [2, 4], i = 2 and j = 4 gives the maximum value that is 10.

For the second test case:
In the first query, in the range [2, 4], i = 2 and j = 3 gives the maximum value that is 5.
In the second query we will set value at index 3 (1 based index) in the “Arr” to 1.
In the third query, in the range [2, 4], i = 2 and j = 3 gives the maximum value that is 3.
Sample Input 2 :
2
3 3
48 71 44 
1 3 27
2 2 3
2 1 3
4 3
20 36 26 12 
1 2 14
2 1 3
1 4 68
Sample Output 2 :
98
119
46
Hint

Can you find the two highest values in the range between ‘L’ and ‘R’?

Approaches (2)
Brute Force

For each query of type 1, we can simply set Arr[index] = value.

 

For each query of type 2, we can simply iterate between ‘L’ and ‘R’ and store first highest in “maximum1” and second highest in “maximum2”. If the value Arr[i] is greater or equal to “maximum1” then do “maximum2” = “maximum1” and “maximum1” = Arr[i]. 

 

Algorithm:

 

  • Create an array “answer” to store the result of a query of type 2.
  • Iterate over the queries
  • If type is equal to 1:
    • Do Arr[index] = value
  • If type is equal to 2:
    • Iterate on the range from L to R and maintain two highest values in maximum1 and maximum2.
    • If Arr[i] is greater or equal to maximum1:
      • Set “maximum2” = “maximum1”
      • Set “maximum1” = Arr[i]
    • Else if Arr[i] is greater than maximum2:
      • Set “maximum2” = Arr[i]
    • Store the sum of “maximum1” and “maximum2” in the array “answer”.
    • Return the array “answer”.
Time Complexity

O(N * Q), where ‘N’ denotes the number of elements in the array and ‘Q’ denotes the number of queries.

 

Note that for each of the ‘Q’ queries, in the worst case we iterate through ‘N’ elements. Therefore the time complexity for each query is O(N), therefore an overall time complexity of O(N * Q).

Space Complexity

O(Q), where ‘Q’ denotes the number of queries.

 

Since we are storing answers to each query of type 2, therefore overall space complexity is O(Q)

Code Solution
(100% EXP penalty)
Maximum Subarray Sum Queries - ll
Full screen
Console