Find the maximum element in the array after update operations.
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

Question

Find the maximum element in the array after update operations.

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

Accepted Answer

The brute force approach is to do a linear search. Traverse the array and keep track of maximum and element. And finally return the maximum element.
Time Complexity : O(n)
The efficient approach is to use Binary Search. The standard Binary search algorithm can be modified for the given type of arrays :
i) If the mid element is greater than both of its adjacent elements, then mid is the maximum.
ii) If mid element is greater than its next element and smaller than the previous element then maximum lies on left side of mid. Example array: {3, 50, 10, 9, 7, 6}
iii) If mid element is smaller than its next element and greater than the previous element then maximum lies on right side of mid. Example array: {2, 4, 6, 8, 10, 3, 1}

Algorithm :
maxInBitonic(arr[], l, r)
{

while (l is less than equal to r), do :

declare m = l + (r - l) / 2;

/* If there are two elements and first is greater then the first element is maximum */
if ((r == l + 1) and arr[l] >= arr[r])
return arr[l]

/* If there are two elements and second is greater then the second element is maximum */

if ((r == l + 1) and arr[l] < arr[r])
return arr[r]

/* If we reach a point where arr[mid] is greater than both of its adjacent elements arr[mid-1] and arr[mid+1], then arr[mid] is the maximum element*/
if (arr[m] > arr[m + 1] and arr[m] > arr[m - 1])
return arr[m]

// move to left with l and r=m-1
if (arr[m] > arr[m + 1] and arr[m] < arr[m - 1])
update r to m - 1
else
update l to m + 1 // move to right with l=m+1 and r
}
// if we reach here, then element was not present
return -1
}

Accepted Answer

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

Space Complexity: O(n)Explanation:

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

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

Time Complexity: OtherExplanation:

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

Python (3.5)

'''

    Time Complexity: O(N * M)

    Space Complexity: O(N)



    where 'N' is size of array and 'M' is number of queries.

'''



def findMaxElement(arr,  n,  m):

    a = [0]*(n+1)



    for i in range(m):



        for j in range(arr[i][0], arr[i][1]+1):



            a[j] += 1



    ans = 0



    for i in range(1, n+1):

        ans = max(ans, a[i])



    return ans

C++ (g++ 5.4)

/*
    Time Complexity: O(N * M)
    Space Complexity: O(N)

    where 'N' is size of array and 'M' is number of queries.
*/

int findMaxElement(vector < pair < int, int > > &arr, int n, int m) {
    vector < int > a(n + 1, 0);
    for (int i = 0; i < m; i++) {
        for (int j = arr[i].first; j <= arr[i].second; j++) {
            a[j]++;
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, a[i]);
    }

    return ans;
}

Java (SE 1.8)

/*
    Time Complexity: O(N * M)
    Space Complexity: O(N)

    where 'N' is size of array and 'M' is number of queries.
*/

import java.util.ArrayList;

public class Solution {
    public static int findMaxElement(ArrayList < ArrayList < Integer >> arr, int n, int m) {
        int[] a = new int[n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = arr.get(i).get(0); j <= arr.get(i).get(1); j++) {
                a[j]++;
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, a[i]);
        }

        return ans;
    }
}

Accepted Answer

Using prefix sum.

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

Space Complexity: O(n)Explanation:

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

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

Time Complexity: OtherExplanation:

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(1) by updating only two points and calculating the maximum element in array/list after ‘M’ operations in O(N).

Python (3.5)

'''

    Time Complexity: O(N + M)

    Space Complexity: O(N)

    

    where 'N' is size of array and 'M' is number of queries.

'''



def findMaxElement(arr,  n,  m):



    a = [0]*(n+1)

    for i in range(m):

        a[arr[i][0]] += 1



        if(arr[i][1] < n):

            a[arr[i][1]+1] -= 1



    ans = 0

    for i in range(1, n+1):



        a[i] += a[i-1]

        ans = max(ans, a[i])



    return ans

Java (SE 1.8)

/*
    Time Complexity: O(N + M)
    Space Complexity: O(N)
    
    where 'N' is size of array and 'M' is number of queries.
*/

import java.util.ArrayList;

public class Solution {
    public static int findMaxElement(ArrayList < ArrayList < Integer >> arr, int n, int m) {
        int[] a = new int[n + 1];
        for (int i = 0; i < m; i++) {
            a[arr.get(i).get(0)]++;

            if (arr.get(i).get(1) < n) {
                a[arr.get(i).get(1) + 1]--;
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            a[i] += a[i - 1];
            ans = Math.max(ans, a[i]);
        }

        return ans;
    }
}

C++ (g++ 5.4)

/*
    Time Complexity: O(N + M)
    Space Complexity: O(N)
    
    where 'N' is size of array and 'M' is number of queries.
*/

int findMaxElement(vector < pair < int, int > > &arr, int n, int m) {
    vector < int > a(n + 1, 0);
    for (int i = 0; i < m; i++) {
        a[arr[i].first]++;

        if (arr[i].second < n) {
            a[arr[i].second + 1]--;
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        a[i] += a[i - 1];
        ans = max(ans, a[i]);
    }

    return ans;
}

Example:

Note:

Input Format:

Output Format:

Note:

Constraints:

Top Morgan Stanley Java Developer interview questions & answers

Popular interview questions of Java Developer