Question

Given an array arr[], find the maximum j i such that arr[j] > arr[i]

Answer 1

Explanation:

Given an array arr[], find the maximum j – i such that arr[j] > arr[i].

Examples :

Input: {34, 8, 10, 3, 2, 80, 30, 33, 1}

Output: 6 (j = 7, i = 1)

Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}

Output: 8 ( j = 8, i = 0)

Input: {1, 2, 3, 4, 5, 6}

Output: 5 (j = 5, i = 0)

Input: {6, 5, 4, 3, 2, 1}

Output: -1

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

Method 1 (Simple but Inefficient)

Run two loops. In the outer loop, pick elements one by one from left. In the inner loop, compare the picked element with the elements starting from right side. Stop the inner loop when you see an element greater than the picked element and keep updating the maximum j-i so far.