Difference Between Indices

Hard

0/120

Average time to solve is 40m

Contributed by

13 upvotes

Asked in company

Problem statement

You are given an array ‘arr’ of size ‘N’. You have to find two indices, ‘i’ and ‘j’, such that arr[j] > arr[i] and the difference between ‘j’ and ‘i’ is maximized. If there are no two indices such that arr[j] > arr[i] then return -1.

For example:

Consider arr =[1, 2, 3, 4, 5], we can take indices i = 0, and j = 4, so difference is 4 - 0 = 4, and arr[4] > arr[0]. Hence the answer is 4.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer 'T' which denotes the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the size of the array ‘arr’.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the array ‘arr’.

Output Format:

For each test case, print a single integer representing the maximum difference between ‘j’ and ‘i’ such that arr[j] > arr[i].

The output of each test case will be printed in a separate line.

Note:

You do not need to input or print anything, as it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10 
1 <= N <= 10 ^ 6
1<= arr[i] <= 10 ^ 9 

Time limit: 1 sec

Sample Input 1:

Sample Output 1:

4
-1

Explanation of Sample Input 1:

Test case 1:
We can take indices i = 0, and j = 4, so difference is 4 - 0 = 4, and arr[4] > arr[0]. Hence the answer is 4.

Test case 2:
There doesnot exist two indices such that j - i > 0 and arr[j] > arr[i]. Hence the answer is -1.

Sample Input 2:

2
5
4 2 3 1 5
6
1 4 6 2 3 1

Sample Output 2:

4
4

Hint 1

Hint 2

Try to check for every index ‘i’, whether an index ‘j’ exists to meet the required conditions.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

We will run two for loops to check whether there exist two indices, such that the difference of indexes is maximized and arr[j] > arr[i].

Algorithm:

Run a for loop from index ‘i’ = 0 to n - 1
- Run another for loop from index ‘j’ = i + 1 to n - 1
  - Check if arr[j] > arr[i] :
    - If yes, then update maximum answer.
    - Otherwise, do not update.

Time Complexity

O(N^2), where 'N' is the number of elements in the array.

Since we are using two nested loops, both in the range of 1 to ‘N’, the time complexity is O(N^2). Hence the overall time complexity is O(N^2)

Space Complexity

O(1).

Since constant space is used, hence the overall space complexity is O(1).

(100% EXP penalty)

Difference Between Indices

Console