Find the maximum index difference in the given array of integers, as per below conditions-
a) 'i' is left index in the given array & 'j' is the right index.
b) i < j
c) Array[i] < Array[j]
Can assume the array size as about 1 to 10000
and numbers in the array can be 1 to 10000000
E.g. : If the given array is [5, 3, 2, 1, 1, 4]
then answer will be 5, Array[1] < Array[5]
Explanation : if we pick i as 1 & j as 5 then it satisfies all the above given conditions.
If no such answer is possible then return 0.
Below is one possible way, which I got while discussing with one colleague, though we both agreed that it doesn't seem to be optimal one as it has O(n*n) run time complexity & it is not the correct one also.
So request you guys to provide the optimal solution for this below in comment section, so that all get benefited.
a) 'i' is left index in the given array & 'j' is the right index.
b) i < j
c) Array[i] < Array[j]
Can assume the array size as about 1 to 10000
and numbers in the array can be 1 to 10000000
E.g. : If the given array is [5, 3, 2, 1, 1, 4]
then answer will be 5, Array[1] < Array[5]
Explanation : if we pick i as 1 & j as 5 then it satisfies all the above given conditions.
If no such answer is possible then return 0.
Below is one possible way, which I got while discussing with one colleague, though we both agreed that it doesn't seem to be optimal one as it has O(n*n) run time complexity & it is not the correct one also.
So request you guys to provide the optimal solution for this below in comment section, so that all get benefited.