Find the maximum element in the array after update operations.

Posted: 27 Feb, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
Approach 1

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’.
Try Problem