Hello Everyone
In continuation with last post, this is the most efficient method.
Efficient Method
To solve this problem, we need to get two optimum indexes of arr: left index i and right index j. For an element arr[i], we do not need to consider arr[i] for left index if there is an element smaller than arr[i] on left side of arr[i]. Similarly, if there is a greater element on right side of arr[j] then we do not need to consider this j for right index. So we construct two auxiliary arrays LMin and RMax such that LMin[i] holds the smallest element on left side of arr[i] including arr[i], and RMax[j] holds the greatest element on right side of arr[j] including arr[j]. After constructing these two auxiliary arrays, we traverse both of these arrays from left to right. While traversing LMin and RMa if we see that LMin[i] is greater than RMax[j], then we must move ahead in LMin (or do i++) because all elements on left of LMin[i] are greater than or equal to LMin[i]. Otherwise we must move ahead in RMax[j] to look for a greater j – i value.
Working Example:
Lets consider any example [7 3 1 8 9 10 4 5 6]
what is maxRight ?
Filling from right side 6 is first element now 6 > 5 so again we fill 6 till we reach 10 > 6 :
[10 10 10 10 10 10 6 6 6] this is maxR
[7 3 1 1 1 1 1 1 1 ] this is minL
now we see that how to reach answer from these to and its proof !!!
lets compare first elements of the arrays now we see 10 > 7,
now we increase maxR by 1 till it becomes lesser than 7 i.e at index 5
hence answer till now is. 5-0 = 5
now we will increase minL we get 3 which is lesser than 6 so we increase maxR till it reaches last index and the answer becomes 8-1= 7
so we see how we are getting correct answer.
As we need the max difference j – i such that A[i]<= A[j], hence we do not need to consider element after the index j and element before index i.
in previous hint, make 2 arrays,
First, will store smallest occurring element before the element
Second, will store largest occurring element after the element
Traverse the Second array, till the element in second array is larger than or equal to First array, and store the index difference. And if it becomes smaller, traverse the first array till it again becomes larger.
And store the max difference of this index difference.
#include <stdio.h>
/* Utility Functions to get max and minimum of two integers */
int
max(
int
x,
int
y)
{
return
x > y ? x : y;
}
int
min(
int
x,
int
y)
{
return
x < y ? x : y;
}
/* For a given array arr[], returns the maximum j – i such that
arr[j] > arr[i] */
int
maxIndexDiff(
int
arr[],
int
n)
{
int
maxDiff;
int
i, j;
int
* LMin = (
int
*)
malloc
(
sizeof
(
int
) * n);
int
* RMax = (
int
*)
malloc
(
sizeof
(
int
) * n);
/* Construct LMin[] such that LMin[i] stores the minimum value
from (arr[0], arr[1], ... arr[i]) */
LMin[0] = arr[0];
for
(i = 1; i < n; ++i)
LMin[i] = min(arr[i], LMin[i - 1]);
/* Construct RMax[] such that RMax[j] stores the maximum value
from (arr[j], arr[j+1], ..arr[n-1]) */
RMax[n - 1] = arr[n - 1];
for
(j = n - 2; j >= 0; --j)
RMax[j] = max(arr[j], RMax[j + 1]);
/* Traverse both arrays from left to right to find optimum j - i
This process is similar to merge() of MergeSort */
i = 0, j = 0, maxDiff = -1;
while
(j < n && i < n) {
if
(LMin[i] < RMax[j]) {
maxDiff = max(maxDiff, j - i);
j = j + 1;
}
else
i = i + 1;
}
return
maxDiff;
}
/* Driver program to test above functions */
int
main()
{
int
arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 };
int
n =
sizeof
(arr) /
sizeof
(arr[0]);
int
maxDiff = maxIndexDiff(arr, n);
printf
(
"\n %d"
, maxDiff);
getchar
();
return
0;
}
Output
8
Time Complexity: O(n)
Auxiliary Space: O(n)