Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Find Maximum

Last Updated on December 13, 2022 by Prepbytes

Arrays

Hard

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given an array `A` of `N` positive integers. The task is to find the `maximum` of
`j - i` such that `A[j] > A[i]`, where `j > i`.

See original problem statement here

#### For Example :

``````Input : N = 10, A[] = [5 16 7 3 2 9 10 4 3 4]

Output : 6

Explanation :

16 > 5, diff = 1 - 0 = 1
7 > 5,  diff = 2 - 0 = 2
9 > 5,  diff = 5 - 0 = 5
9 > 7,  diff = 5 - 2 = 3
10 > 5, diff = 6 - 0 = 6
4 > 2,  diff = 7 - 4 = 1
3 > 2,  diff = 8 - 4 = 4
4 > 2,  diff = 9 - 4 = 5

Out of all these differences, 6 was the maximum difference between indexes of 5 and 10 i.e. 6 - 0 = 6``````

### SOLVING APPROACH:

#### BRUTE FORCE METHOD:

1. This method is `Simple` but `Inefficient`.

2. Run two nested loops.

3. In the outer loop, pick elements one by one from left to right.

4. In the inner loop, pick the rest of the elements and keep comparing the `maximum` value of `(j-i)`.

5. `Time complexity` of this approach is O(N2).

#### EFFICIENT METHOD:

1. The problem can be solved by simply finding out two `Optimum Indexes` of the array, `left index` `i` and `right index` `j`.

2. For an element `A[i]`, we need not consider it for the left index if there exists a smaller element than `A[i]` on its left side.

3. Similarly for an element `A[i]`, we need not consider it for the right index if there exits a greater element on its right side.

4. Now construct two arrays : `leftMin[]` and `rightMax[]`,
such that `leftMin[i]` contains the smallest element on its left side including itself and `rightMax[i]` contains the largest element on its right side including itself.

5. Start traversing both the arrays from left to right.

6. While traversing :-

if `leftMin[i]` `>` `rightMax[i]`, then we simply move ahead in `leftMin[]` by `1`, as all elements to the left of `leftMin[i]` are either greater than or equal to `leftMin[i]`

if `leftMin[i]` `<` `rightMax[i]`, then we move ahead in `rightMax[i]` to look for a better value of `j-i`.

### SOLUTIONS:

```
#include<stdio.h>

int maximumGap(int arr[],int n) {
int l[n],r[n];
l[0]=arr[0];
for(int i=1;i<n;i++)
{
if(arr[i]<l[i-1])
l[i] = arr[i];
else
l[i] = l[i-1];
}
r[n-1]=arr[n-1];
for(int i=n-2;i>=0;i--)
{
if(arr[i] > r[i+1])
r[i] = arr[i];
else
r[i] = r[i+1];
}
int i=0,j=0;
int max_dist = -1;
while(i<n && j<n)
{
if(l[i]<r[j])
{
if(j-i > max_dist)
max_dist = j-i;
j++;
}
else
{
i++;
}
}
if(max_dist==-1)
return -1;
return max_dist;
}

int main()
{
int n;
scanf("%d",&n);
int arr[n];
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
printf("%d\n",maximumGap(arr,n));

return 0;
}
```
```#include<bits/stdc++.h>
using namespace std;
#define ll long long
int maximumGap(int arr[],int n) {
int l[n],r[n];
l[0]=arr[0];
for(int i=1;i<n;i++)
{
l[i]=min(arr[i],l[i-1]);
}
r[n-1]=arr[n-1];
for(int i=n-2;i>=0;i--)
{
r[i]=max(arr[i],r[i+1]);
}
int i=0,j=0;
int max_dist = -1;
while(i<n && j<n)
{
if(l[i]<r[j])
{
max_dist = max(max_dist,j-i);
j++;
}
else
{
i++;
}
}
if(max_dist==-1)
return -1;
return max_dist;
}

int main()
{
int n;cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
cout<<maximumGap(arr,n)<<"\n";

return 0;
}

```
```

import java.util.*;
import java.io.*;
import java.lang.Math;

public class Main {

static int maximumGap(int arr[],int n) {
int l[] = new int[n];
int r[] = new int[n];
l[0]=arr[0];
for(int i=1;i<n;i++)
{
l[i]=Math.min(arr[i],l[i-1]);
}
r[n-1]=arr[n-1];
for(int i=n-2;i>=0;i--)
{
r[i]=Math.max(arr[i],r[i+1]);
}
int i=0,j=0;
int max_dist = -1;
while(i<n && j<n)
{
if(l[i]<r[j])
{
max_dist = Math.max(max_dist,j-i);
j++;
}
else
{
i++;
}
}
if(max_dist==-1)
return -1;
return max_dist;
}

public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++)
arr[i] = sc.nextInt();
System.out.println(maximumGap(arr,n));
}
}
```
```
def maximumGap(arr,n):
l=[0 for i in range(n)]
r=[0 for i in range(n)]
l[0]=arr[0]
for i in range(1,n):
l[i]=min(arr[i],l[i-1])
r[n-1]=arr[n-1]
for i in range(n-2,-1,-1):
r[i]=max(arr[i],r[i+1])
i=0
j=0
max_dist=-1
while(i<n and j<n):
if l[i]<r[j]:
max_dist = max(max_dist,j-i)
j+=1
else:
i+=1
if max_dist==-1:
return -1
return max_dist
n=int(input())
arr=list(map(int,input().split()))
print(maximumGap(arr,n))

```

Space Complexity: `O(N)`

[forminator_quiz id="628"]

This article tried to discuss Arrays. Hope this blog helps you understand and solve the problem. To practice more problems on Arrays you can check out MYCODE | Competitive Programming.