New update is available. Click here to update.

Find the maximum element in the array after update operations.

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.

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

Approach 2

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

Try Problem

Find the maximum element in the array after update operations.

PROBLEM STATEMENT

Example:

Note:

Input Format:

Output Format:

Note:

Constraints:

Approach 1

Approach 2

Interested in Coding Ninjas Flagship Courses?