Find the maximum element in the array after update operations.

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in companies
Morgan StanleyMicrosoftAmazon

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
2 2
1 2
1 1  
2 1
2 2
Sample Output 1:
2
1

Sample Output 1 Explanation:

Test case 1:

Initial array/list ‘A’ is [0,0]
Array/list ‘A’ after each operation:-
[1,1] → Elements with index in range of [1,2] gets incremented by 1.
[2,1] → Elements with index in range of [1,1] gets incremented by 1.  

Therefore the maximum element in array/list ‘A’ is 2.

Test case 2:

Initial array/list 'A' is [0,0]
Array/list ‘A’ after each operation:-
[0,1] → Elements with index in range of [2,2] gets incremented by 1.

Therefore the maximum element in array/list ‘A’ is 1.
Sample Input 2:
2
5 5
5 5
2 4
1 2
2 2
2 3
2 3
1 2
1 1
2 2
Sample Output 2:
4
2
Hint

Naively increase each element in the range. 

Approaches (2)
Brute Force

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’.
Time Complexity

O(N * M), where ‘N’ denotes the size of array/list and ‘M’ denotes the number of operations.

 

As we are performing each operation in O(N) by updating each index in the range of that operation and calculating the maximum element in array/list after ‘M’ operations in O(N).

Space Complexity

O(N), where ‘N’ denotes the size of the array/list.

 

As we need to create an array of size ‘N’.

Code Solution
(100% EXP penalty)
Find the maximum element in the array after update operations.
Full screen
Console