Find Maximum

Last Updated on December 13, 2022 by Prepbytes

CONCEPTS USED:

Arrays

DIFFICULTY LEVEL:

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(N²).

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.