Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute-Force Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Optimized Approach
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
Frequently Asked Questions
4.1.
What does the brute-force approach do in this problem?
4.2.
What does sizeof() return?
4.3.
Why would you use an array to hold a tree instead of tree nodes?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

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

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

This blog covers one of the many exciting array problems. Arrays are among the most important and often asked data structures in programming contests and technical interviews. There are various standard array problems and techniques. This blog tackles a coding task that involves finding the maximum j – i such that arr[j] > arr[i] in the array.

Also See, Array Implementation of Queue and  Rabin Karp Algorithm.

Problem Statement

Ninja is on holiday, but his college professor has given him an assignment. He has been given an array and is asked to find the maximum j – i value such that arr[j] > arr[i]. Can you help him to enjoy his holiday by solving this problem?

Sample Examples

Example 1

Input

Output

4

 

Explanation: Out of all the value pairs for which arr[j] > arr[i], condition is true, the maximum value of j-i is 4.

 

Example 2

Input

Output

6

 

Explanation: Out of all the value pairs for which arr[j] > arr[i], condition is true, the maximum value of j-i is 6.

Brute-Force Approach

We run two loops from left and right, respectively. We compare the two values on loops, and if we find an element such that arr[j] > arr[i], we update the maximum value of j-i maintained throughout the loop run.

Algorithm

1. We start two loops through the array.

2. Pick elements from the left one by one by the outer loop.

3. Compare the selected element to the items starting from the right side in the inner loop.

4. When you see an element larger than the selected element, stop the inner loop and update the maximum j-i value till now.

5. Return the maximum value maintained till now.

Implementation

// Brute-force approach
#include <bits/stdc++.h>
using namespace std;

int valCalculator(int nums[], int n)
{
	int m = -1;
	int i, j;
	// initiate two loops to compare array values from left and right
	for (i = 0; i < n; ++i)
	{
		for (j = n - 1; j > i; --j)
		{
			if (nums[j] > nums[i] && m < (j - i))
			m = j - i;
		}
	}
	// Return the maximum j-i value
	return m;
}


int main()
{
	int nums[] = {5, 3, 8, 6, 7};
	int n = sizeof(nums) / sizeof(nums[0]);
	int m = valCalculator(nums, n);
	cout << "The array is: " << endl;
	for (size_t i = 0; i < n; i++)
	{
	cout << nums[i] << " ";
	}
	cout << endl
	<< "The maximum j-i value is: ";
	cout << "\n" << m;
	return 0;
}

 

Output

Time Complexity

The time complexity for the given approach is O(n2) as we run two loops to check for the maximum j-i value in the array in cases where arr[j] > arr[i].

Space Complexity

The Space Complexity of the above approach is O(1) as no other data structures are used for memory in the described solution.

Array in Javascript

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

We want to find two optimal arr[] indexes, left(i) and right(j). If there is an element less than arr[i] on the left side of arr[i], we will not need to consider arr[i] for the left index. We have a similar situation on the right side. So we create two arrays, leftMin[] and rightMax[], with leftMin[i] holding the lowest member on the left side of arr[i], and rightMax[j] holding the maximum element on the right side. Both of these arrays are traversed from left to right. If we notice that leftMin[i] is bigger than rightMax[j] when traversing leftMin[] and rightMax[], we must move ahead in leftMin[]. Otherwise, we must move ahead in rightMax[j] to find a higher j – I value.

Algorithm

1. Declare two arrays leftMin[] and rightMax[].

2. Create leftMin[] so that leftMin[i] holds the smallest value from (arr[0], arr[1], ... arr[i]).

3. Create rightMax[] such that it holds the maximum value from (arr[j], arr[j+1],...arr[n-1]). 

4. From left to right, traverse both arrays to get the optimal j - I and save it in a variable. If leftMin[i] = rightMax[j], we update the variable with the maximum j-i value.

5. Return the maximum value.

Implementation

#include <bits/stdc++.h>
using namespace std;
int differenceCalc(int nums[], int n)
{
    int diffMax;
    int i, j;
    int *leftMin = new int[(sizeof(int) * n)];
    int *rightMax = new int[(sizeof(int) * n)];
 
    /* Construct leftMin[] so that
    leftMin[i] has minimum value till i-th index*/
 
    leftMin[0] = nums[0];
 
    for (i = 1; i < n; ++i)
        leftMin[i] = min(nums[i], leftMin[i - 1]);
 
    /* Construct rightMax[] such that
    rightMax[j] has the maximum value from j-th index */
 
    rightMax[n - 1] = nums[n - 1];
 
    for (j = n - 2; j >= 0; --j)
        rightMax[j] = max(nums[j], rightMax[j + 1]);
 
    /* Traverse both arrays from left to right
    to find the maximum value of j - i where arr[j] >= arr[i].*/
 
    i = 0, j = 0, diffMax = -1;
 
    while (j < n && i < n)
    {
        if (leftMin[i] <= rightMax[j])
        {
            diffMax = max(diffMax, j - i);
            j = j + 1;
        }
        else
            i = i + 1;
    }
 
    return diffMax;
}
// Driver Code
 
int main()
{
    int nums[] = {7, 1, 3, 6, 2, 4, 9};
 
    int n = sizeof(nums) / sizeof(nums[0]);
 
    cout << "The array is: " << endl;
 
    for (size_t i = 0; i < n; i++)
    {
        cout << nums[i] << " ";
    }
    cout << endl
         << "The maximum j-i value is: " << endl;
    int diffMax = differenceCalc(nums, n);
 
    cout << diffMax;
 
    return 0;
}


Output

Time Complexity

The Time complexity of the above approach is O(n) as there are only single loop traversals of the arrays in the entire solution.

Space Complexity

The Space complexity of the above approach is O(n) as it includes using two arrays for left minimum and right maximum values storage.

Frequently Asked Questions

What does the brute-force approach do in this problem?

We run two loops from left and right, respectively. We compare the two values on loops, and if we find an element such that arr[j] > arr[i], we update the maximum value of j-i maintained throughout the loop run.

What does sizeof() return?

It returns the variable's size. It may be used for any data type, including float and pointer variables.

Why would you use an array to hold a tree instead of tree nodes?

It takes less time to search. You may easily convert the array into a binary tree for a faster search time. The most significant benefit of using an array format for a tree is that you save memory by keeping fewer pointers.

Conclusion

This article extensively discussed the problem of finding the maximum value of j-i indexes of the array such that arr[j] > arr[i] in a given array and the time and space complexities of the solution presented.
Cheers, you have reached the end. Hope you liked the blog and it has added some knowledge to your life. Please look at these similar topics to learn more: Array IntroductionArray Interview QuestionsBook Allocation Problem2-D Array, and 1-D Array.

Recommended problems -

 

Refer to our Coding Ninjas Studio Guided Path to learn Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and even more! You can also check out the mock test series and participate in the contests hosted by Coding Ninjas Studio! But say you're just starting and want to learn about questions posed by tech titans like Amazon, Microsoft, Uber, and so on. In such a case, for placement preparations, you can also look at the problemsinterview experiences, and interview bundle.

You should also consider our premium courses to offer your career advantage over others!

Please upvote our blogs if you find them useful and exciting!

 

Happy Coding!

Previous article
Maximum difference between two elements such that larger element appears after the smaller number
Next article
K-th Largest Sum Contiguous Subarray
Live masterclass