# Find the maximum element in the array after update operations.

Posted: 27 Feb, 2021

Difficulty: Moderate

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

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

SIMILAR PROBLEMS

# Lexicographic Permutation Rank

Posted: 13 Jul, 2021

Difficulty: Moderate

# Zero Pair Sum

Posted: 22 Jul, 2021

Difficulty: Moderate

# Implement a Queue

Posted: 27 Jul, 2021

Difficulty: Easy

# Remove K Corner Elements

Posted: 31 Jul, 2021

Difficulty: Easy

# Connecting Ropes

Posted: 12 Nov, 2021

Difficulty: Hard