Last Updated: 27 Feb, 2021
Find the maximum element in the array after update operations.
Moderate
Asked in companies
You have been given an array/list ‘A’ consisting of ‘N’ integers all of which are ‘0’ initially. You are given an array/list ‘ARR’ consisting of ‘M’ pairs of integers which are ‘M’ operations you need to perform on ‘A’. In each operation, you are given a range and you need to increase each element whose index lies in that range by ‘1’. Your task is to return the maximum element of array/list ‘A’ after all ‘M’ operations are performed.
Example:
Let’s assume ‘N’ is 5. Initially, all the elements are initialized to zero. we need to perform 2 operations 1 5 and 2 4. In operation 1 5, we will increase all the elements from index 1 to 5 by 1 i.e it becomes [1,1,1,1,1].
In operation 2 4, we will increase all the elements from index 2 to 4 by 1 i.e it becomes [1,2,2,2,1]. So answer in this case will be 2 as 2 is the maximum element of the array/list.
Note:
In the above question array/list is assumed to have ‘1’ - based indexing i.e. array/list starts from index 1.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case contains two single space-separated integers ‘N’ and ‘M’ representing the size of the array/list and number of operations.
Next ‘M’ lines contain operations that have to be performed on ‘A’. Each operation contains two single space-separated integers representing a range of indices on which you need to perform the operation.
Output Format:
For each test case, return the maximum element of array/list ‘A’ after all ‘M’ operations are performed.
Note:
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
1 <= N <= 10^3
1 <= M <= 10^3
1 <= L <= N
L <= R <= N
Time Limit: 1 sec
Approaches
We will declare an array/list ‘A’ of size ‘N’+1 and initialize all its elements to 0.
- For each operation, we will do as follows:-
- We will iterate from L[ i ] to R[ i ] and increase the element at these indices by 1.
- We will iterate through the array/list ‘A’ after ‘M’ operations to find the maximum element and store it in ‘ANS’.
- Return ‘ANS’.
We will declare an array/list 'A' of size ‘N’+1 and initialize all its elements to 0. We will use the fact that each element that lies between L[ i ] and R[ i ] (inclusive) gets incremented by ‘1’ so we increase the element at L[ i ] by ‘1’. When we take prefix sum after all the operations it will increase all the indices greater than it by ‘1’ also. But we want it to increase only till R[ i ], therefore we decrease ‘A[R[ i ] + 1]’ by ‘1’ before taking prefix sum.
- For each operation, we will do as follows:-
- We will increase ‘A[ L[ i ] ]’ by ‘1’.
- We will decrease ‘A[ R[ i ] + 1]’ by ‘1’ if ‘R[ i ] + 1’
is <= ‘N’.
- After all the operations perform prefix sum i.e ‘A[ i ] = A[ i ] + a
A[ i - 1 ]’ by iterating through the array/list.
- We will iterate through the array/list 'A' after ‘M’ operations to find the maximum element and store it in ‘ANS’.
- Return ‘ANS’.
Similar problems