## A Distance Maximizing Problem

May 19, 2011 in Uncategorized

Given an array A of integers, find the maximum of j-i subjected to the constraint of A[i] < A[j].

**Hint:**

This problem seemed easy, maybe because it is easy to understand. But is it straightforward to solve? If you are thinking of a straightforward solution, think again. Try to come up with a solution with run time complexity of O(n log n). Can you do better than that?

**Solution:**

Visualization of the problem using *n* vertical lines. The i^{th} line’s height is represented by A[i], assuming A[i] is positive.

We are able to visualize the above problem better by drawing *n* vertical lines, where the height of i^{th} line corresponds to the i^{th} element in A. We first assume that all elements in A are positive integers, but later it can be expanded to non-positive integers as well. Now, unless the elements in A forms a strictly non-increasing order, there must exist a pair of (i, j) such that A[i] < A[j], and i < j. Therefore, the above problem is equivalent of finding the maximum distance between two vertical lines, where the left line must be shorter than the right line.

**Brute Force O(N ^{2})**

The straightforward brute force way is to find the shortest line (the starting index, i), then try to look toward the right side (the ending index, j) and find a taller line with the furthest distance. Record the distance (j-i)and repeat with the next shortest line. Clearly, this is an O(N

^{2}) algorithm and we can do better.

**Sorting O(N log N)**

Above diagram shows *n* lines sorted according its heights. Lines with same heights are sorted using its original index. We will also need to keep track of each line’s original index in order to calculate the distance later. Finally, we build a table by scanning the lines’ original index from right to left once.

By sorting the lines according to its height, we can achieve better run time complexity. Notice that once we sorted the lines, we are able to find the maximum distance in O(N) time. For each possible original starting index i, we find the original ending index j, which is the maximum among all j’s where A[j] > A[i]. To enable the quick search for the maximum, we can build a look up table in O(N) time by scanning from right to left once. For example, we start with index i = 4, which is the shortest line. We know the maximum of all original indices to the right is 7, therefore max distance = 7 – 4 = 3. For the next line which original index is 3, the max distance = 7 – 3 = 4. Now, we must skip over the duplicates and reach the line with its original index 1. Here, we must be careful to skip over all duplicate heights which are not part of the solution because not satisfying the constraint A[j] > A[i]. Therefore, the max distance for this case = 2 – 1 = 1.

**Best Solution O(N)**

Given two indices a and b, where would you rather choose as a potential starting point?

Credits for the best O(N) solution goes to **darksteel**, which I first learned this neat method from him. Anonymous is the only reader who is able to solve this correctly using the same idea, great job!

Solving this problem efficiently requires some clever observations to eliminate all unnecessary comparisons. It is non obvious to me at first if there exists an O(N) algorithm for this problem.

Please look at the above diagram carefully, and ask yourself if you would choose index a or b as a potential starting point. Clearly, you would never choose index b as the starting point. Why?

Assume that choosing index b as the starting point, the max distance is j-b, where A[j] > A[b]. Now, since a < b and A[a] is not taller than A[b] which implies that A[j] > A[a], we can form a farther distance by choosing a as the starting index. Therefore, we cannot choose b as the starting point as this forms a contradiction.

Generally, we want to choose only starting points with no such lines that are shorter to its left side. From the diagram above, only lines of index 0, 1, 3, 4 are valid starting points.

Once we gather all valid starting points by scanning once from left to right, we are able to obtain the maximum distance by scanning backwards.

It is obvious that if the ending point is less than the shortest starting point, then it won’t be a valid solution for all other starting points. Therefore, we scan from right to left until we meet the first ending point that satisfies the condition. Then, we proceed to the next shortest starting point, and continue on from the previous ending point. Using this strategy, we would guarantee that we are able to find the maximum distance in O(N) running time.

**To be continued…**

airfang said on May 19, 2011

Hmmm, is this the stocking buying problem appears on the MIT’s hack a google interview slides?

+2Geek said on January 15, 2013

NO that is the maximum a[j]-a[i] such that j>i it is different

0zyfo2 said on January 25, 2013

yet you can convert it to the original one: converted[a[i]]=i

if these values are consecutive numbers. otherwise you’ll use much more memory than needed if one value>> some value

+3theOtherWC said on February 17, 2014

Great observation.

But it won’t work for non-integer inputs, also it won’t work for array with duplicated items.

0polynomial said on May 19, 2011

Can we build up a max-heap based on pair and sorted by ‘value’ ? Then each time check the top’s position in the original array , we can tell the maximum length before that position( of course, with subtracting the previous number of “maximum” poped up).

0Onlogn said on May 19, 2011

1 def val_cmp(x,y):

2 if x[0] == y[0]:

3 return 0

4 return -(x[0]-y[0])/abs(x[0]-y[0])

5

6 def MaxDistance(array):

7 print array

8 llist = []

9 for idx in xrange(0,len(array)):

10 llist.append((array[idx], idx))

11 llist.sort(val_cmp)

12 print llist

13 idx_position = set(range(0,len(array)))

14 print idx_position

15 dist = 0

16 for x in llist:

17 idx_position.remove(x[1])

18 try:

19 if x[1] – min(idx_position) > dist:

20 dist = x[1] – min(idx_position)

21 except:

22 break

23 return dist

24

25 if __name__ == “__main__”:

26 print MaxDistance([3,2,1,4,5,9])

27 print “————————-”

28 print MaxDistance([9,2,1,4,5,3])

29 print “————————-”

30 print MaxDistance([3,2,1,0])

31 print “————————-”

32 print MaxDistance([7,6,9,15,1,2,4,6])

Looking forward to O(n) solution.

0Onlogn said on May 19, 2011

Ops… sorry for the ugly format :/

0bpin said on May 20, 2011

Please tell if my understanding and my solution is correct or not

the final value of imin and imax will be the answer

0Ivan said on November 27, 2012

Obviously, it’s not correct. The array isn’t sorted.

0Jagdish said on May 20, 2011

Build up the Binary tree using the array value

Node.Value = array element

Node.Index = array element index

Traverse Tree

{

if( current node has right child)

{

compare current node.Index value WITH index of all the leaf node of right sub tree

maintain the max diff

}

currentnode = currentnode.left;

}

+1bluesun said on May 21, 2011

Got my idea from Jagdish’s post. However, a little improvement can allow us to get the answer during the tree building process.

BST has the following node structure:

When we insert array element into the tree, for the first time we go to the right child, we save the current node’s index. When the element eventually is inserted into its place, we get the difference between its index and the previous index we saved, that is the max length of the current element that satisfies A[i] < A[j]. Save the max of this length, and by the time we finish with all the elements in the array, we have the answer right in our hand.

0bluesun said on May 21, 2011

Try again to format the code:

0Anonymous said on May 22, 2011

O(n) solution:

Observations:

1: if A (0 based, size N) is partioned into non-decreasing local max segments [i0, i1), [i1, i2), ... [ik, N), where A[i[x-1]] > A[i[x]], then the max sequence must start with one of the i[x].

2. We can traverse A and build array of i[x] in O(n) time and O(n) space. Add i[k+1] = N. Then max value of each segment starting at i[x] is get_max_value(x)=A[i[x+1]-1].

3. Then we can traverse i backwards, for each segment j from k to 0, find the left most i[min_i(j)] where A[i[min_i(j)]] =x] for later segments, thus each element in i only needs to be looked at once for the purpose of finding min_i(j). The reason is that if for s= min_i(j), then the candidate sequence [min_i(s), i[s+1]-1] is definitely shorter than [min_i(j), i[j+1]-1] and can be safely ignored. During this scan, we only need to remember the result(s) corresponding to the longest candidate (i[j+1]-1-i[min_i(j)]) scaned so far, and min_i(last_j), so space is O(1). We can stop when min_i(j) reaches 0. Because j moves at most k times, and min_i(j) moves at most k times. Time is O(k) <= O(N).

int find_max_sequence_length_minus_1(int* A, int size_A)

{

if(size_A <= 1)

return -1;

int* i = new int[size_A+1];

k = 0;

i[k] = 0;

for(int j = 1; j < size_A; j++)

if(A[j] =0 && right_most_next_candidate >= 0; j–)

{

int max_value_j = A[i[j+1]-1]; // get_max_value(j)

if(A[i[right_most_next_candidate]] < max_value_j)

{

while(A[i[right_most_next_candidate]] =0)

right_most_next_candidate–; // this line executes at most k times in total

int min_i_of_j = right_most_next_candidate+1;

result_of_j = i[j+1]-1-i[min_i_of_j];

if(result_of_j > max_candidate_result)

max_candidate_result = result_of_j; // and store i[min_i_of_j] and i[j+1]-1 if required by the question

}

}

delete[] i;

return max_candidate_result;

}

Please correct me if you see any problem.

0Anonymous said on May 22, 2011

Code was messed up being intepretted as html. Repost with CDATA:

<![CDATA[

int find_max_sequence_length_minus_1(int* A, int size_A)

{

if(size_A <= 1)

return -1;

int* i = new int[size_A+1];

k = 0;

i[k] = 0;

for(int j = 1; j < size_A; j++)

if(A[j] =0 && right_most_next_candidate >= 0; j–)

{

int max_value_j = A[i[j+1]-1]; // get_max_value(j)

if(A[i[right_most_next_candidate]] < max_value_j)

{

while(A[i[right_most_next_candidate]] =0)

right_most_next_candidate–; // this line executes at most k times in total

int min_i_of_j = right_most_next_candidate+1;

result_of_j = i[j+1]-1-i[min_i_of_j];

if(result_of_j > max_candidate_result)

max_candidate_result = result_of_j; // and store i[min_i_of_j] and i[j+1]-1 if required by the question

}

}

delete[] i;

return max_candidate_result;

}

]]>

0Anonymous said on May 22, 2011

CDATA didn’t work. Try pre tag this time:

int find_max_sequence_length_minus_1(int* A, int size_A)

{

if(size_A <= 1)

return -1;

int* i = new int[size_A+1];

k = 0;

i[k] = 0;

for(int j = 1; j < size_A; j++)

if(A[j] =0 && right_most_next_candidate >= 0; j–)

{

int max_value_j = A[i[j+1]-1]; // get_max_value(j)

if(A[i[right_most_next_candidate]] < max_value_j)

{

while(A[i[right_most_next_candidate]] =0)

right_most_next_candidate–; // this line executes at most k times in total

int min_i_of_j = right_most_next_candidate+1;

result_of_j = i[j+1]-1-i[min_i_of_j];

if(result_of_j > max_candidate_result)

max_candidate_result = result_of_j; // and store i[min_i_of_j] and i[j+1]-1 if required by the question

}

}

delete[] i;

return max_candidate_result;

}

0Anonymous said on May 22, 2011

Still doesn’t work. Anyone know how to post code correctly? Meanwhile you can use View Source to find and decypher the code:(

0aimless said on May 30, 2011

use

http://ideone.com

u can paste your code here

0aimless said on May 30, 2011

@Anonymous:

point 3 is one of the most confusing things i have ever read. either i don’t have enough head to understand things or you don’t know how to explain things(i am not sure which is the case). and please don’t write things which don’t help explaining the situation e.g. get_max_value(x) and if possible support your points by example.

0GameSeven said on June 16, 2011

can’t understand the third part is O(k), what if it is the worst case like

10, 9, 8, 7, 6, 5, 4, where your steps 1/2 don’t do anything… in this case there is no solution anyway. Or it is close to the worst case:

9, 10, 8, 7, 6, 5, 4, your k = n-1… don’t understand how you can do the third step in O(k)

0DaRkLoRd said on May 24, 2011

i think the following algo would also work.

Let the array be A[].

We can keep two arrays B[] and C[] which will do the following work..

B[i] will store the minimum value in A[] till ith index

C[i] will store the maximum value (starting from the end) in A[i] till ith index.

Lets say taking amit’s example…

A[] = { 5 3 4 5 3 3 }

then B[] = {5,3,3,3,3,3}; //starting from the beginning.

and C[] = {5,5,5,5,3,3}; //starting from the end

the we can take two pointers i and j and a max_diff (all initialised to 0) and run the following loop

while(j<(sizeof(A)/sizeof(A[0])))

{

while(B[i]<C[j] && j<(sizeof(A)/sizeof(A[0])))

j++;

if(max_diff<j-i-1)

max_diff = j-i-1;

i++;

j++;

}

the code for creating B[] and C[] can be as follows…

let N = (sizeof(A)/sizeof(A[0]))

B[0] = A[0];

for(i=1;i<N;i++)

{

B[i] = ((A[i]

=0;i–){

C[i] = ((A[i]>B[i+1])?A[i]:B[i+1]);

}

For the given example, answer is coming to be j = 4,i=1,max_diff = 4-1-1 = 2I hope I am clear…0anothergeek said on May 27, 2011

Would it work…I guess it will

0anothergeek said on May 28, 2011

Ignore the previous code…here is the correct version

(An improved version of the code at geeksforgeeks in terms of extra memory)

0Brady Fang said on October 22, 2013

You could change the else statement as follows to significantly save the comparisons:

0bpin said on June 2, 2011

Is the answer for the example [4,3,5,2,1,3,2,3] is 4?

Since 2 at index 3, and 3 at index 7 has the max index distance 7-3 = 4

0bpin said on June 2, 2011

TheArray = [4,3,5,2,1,3,2,3]

def FindDistMax(A):

for u in xrange(len(A)-1, -1, -1):

for i in xrange(0,len(A)):

if A[u] > A[i]:

return u-i

if __name__ == ‘__main__’:

print FindDistMax(TheArray)

+1Omri said on June 5, 2011

On your solution of O(N) isn’t there a hidden sort that takes O(NLogN) when you keep on taking the next starting point ordered by height?

+2Manish Agarwal said on June 6, 2011

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.Stack;

/* Given an array A of integers, find the maximum of j-i subjected to the constraint of A[i] < A[j] */

public class DistanceMaximizing {

static int getMaximumDistance(int [] distance, int n) {

int [] lMin = new int[n];

int [] rMax = new int[n];

lMin[0] = distance[0];

rMax[n-1] = distance[n-1];

for(int i=1;i=0;i–)

rMax[i] = Math.max(distance[i], rMax[i+1]);

int i=0, j=0, maxIndexDiff=-1;

while(i < n && j < n) {

if(lMin[i] < rMax[j]) {

maxIndexDiff = Math.max(maxIndexDiff, j-i);

j++;

}

else i++;

}

return maxIndexDiff;

}

public static void main(String[] args) throws NumberFormatException, IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int n = Integer.parseInt(br.readLine());

int [] distance = new int[n];

for(int i=0;i<n;i++)

distance[i] = Integer.parseInt(br.readLine());

System.out.println(getMaximumDistance(distance, n));

}

}

0Sean said on July 10, 2011

Your code does not give correct answer to the following input:

{34,26,26,32,33,24,5,23,12,23}

should be 3, but it gives 8.

and I never see array lMin’s elements get initialized anywhere, was the code get truncated during copy and paste?

0Sean said on July 10, 2011

Ok, I added the code to get values for lMin, now I think your code is working fine.

Very clean code. Good job!

0fzzh24 said on August 29, 2011

O(N)solution is not a real O(N)

Correct me if I am wrong:

n,n-1,n-2,n-3,..,1+n/2,n/2, n/2-1,n/2-2,…1 (total n numbers)

In O(N) time, you can find out all n starting points(from n to 1)

for n , you need to scan n-1 numbers from 1 to n-1, there is no valid j

for n-1, you need to scan n-2 numbers from 1 to n-2, there is no valid j

…

for n/2, you need to scan n/2-1 numbers from 1 to n/2-1, there is no valid j

…

for 2, you need to scan 1 number from 1 to 1, there is no valid j

Do you still think this is a O(N) solution?

If you say this is the worst case, check this counter example:

n,n-1,n-2,n-3,..,1+n/2,n/2, 1+n/2, n/2-1,n/2-2,…1(n is even)

0fzzh24 said on August 29, 2011

Sorry, skip my previous post

It’s a O(N) solution. I got your points here:

Scan the starting points from right to left, scan the ending points from right to left

when scan the next start point, scan the ending point from the previous index+1

0Prateek Caire said on August 15, 2012

Correct me if i am wrong. Solution is not O(N)

For eg. take array as {100, 99, 98, 97, 4, 5, 4, 3, 2,1}

List of potential starting numbers are {100, 99, 98, 97, 4} say i, array1

List of potential ending numbers are {5, 4, 3, 2, 1} say j; array2. Compare i and j; that is 100 and 1. Not a solution. Now you have 2 options; increment i and check the validity . If solution does not come, decrement j. Both needs to be checked. size of array 1 is n/2 and size of array 2 is N/2. Thus overall complexity is O(n^2). But only in worst case. In most cases, solution is damn smart..

0hbs said on November 7, 2011

Let me know if any issue with following code ..

int distanceMax(int a[], int len)

{

int i;

int curLval = 0, curRval = 0;

int lval = 0, Rval = 0;

for (i=1; i a[i-1])

{

curRval = i;

}

else

{

if ((Rval – lval) < (curRval – curLval))

{

Rval = curRval;

lval = curLval;

}

curLval = i;

curRval = i;

}

}

if ((Rval – lval) < (curRval – curLval))

{

Rval = curRval;

lval = curLval;

}

return (Rval – lval) + 1;

}

0maxq said on November 14, 2011

For the O(nlgn) solution, no need to actually store a table, just use a variable j

to maintain the maximum index to the right when scaning through the sorted

array from right to left.

0Ashok Koyi said on November 20, 2011

Can u please elaborate your second solution. I could not follow

1. how you construct the table

2.how you compute the max distance

0Grace Chen said on December 12, 2011

I’m a little confused on the O(N) solution. Since the original array has been divided into k segments, I think the real time complexity is O(k*k).

0David Roid said on December 14, 2011

I can understand the third solution but it’s not an O(n) one:

1. first (forward) scan, select eligible starting points, that is: elements smaller than any one on its left side.

2. second (backward) scan, select eligible stopping points, that is: elements larger than any one on its right side.

3. final answer:

let’s say we got vector1 from #1 and vector2 from #2, storing indexes.

int max_diff=0;

while ( iter1 != vecteor1.end() ) {

while ( iter2 != vector2.end() ) {

if ( array[*iter2] > array[*iter1] ) {

int diff = *iter2 – *iter1;

max_diff = max( max_diff, diff );

break; // note this

}

iter2++;

}

iter1++;

}

As mentioned already, in worse case like int array[] = { 9,8,7,6,5,4,3,2,1}, the solution yields an O(n^2) complexity.

0David Roid said on December 15, 2011

I think the break within inside loop should be a goto to get out both loops. But I cannot do the math of evaluating the time complexity of this, some body help me out..

0Kumar Abhishek said on December 25, 2011

The original article seems pretty hard to follow. Small code snippets will really help. I will request 1337c0d3r to put a few code snippets and being more specific about the algorithm, pseudocode/snippets will be really helpful.

Thanks/

0Coby said on January 4, 2012

Hi,

Here is another approach to solve this problem.

To begin with, we construct an array R s.t.

R[0] = 0

For every i > 0 :

R[i] = A[i] – A[i-1]

The key observation is that now the solution for the problem is equivalent to finding longest sequence with positive sum in R, which comprise of negative and positive real numbers and can be done in O(N).

+1Lao Ye said on February 3, 2012

int dist_max(int *array, int len)

{

int i, j, *flag, m=99999, minidx=0;

flag = (int *)calloc(len, sizeof(int));

// first pass, find potential starting points

for(i=0; i<len; i++)

if(array[i]=0 && j>=0; )

{

while(array[i]flag[m]) m = j;

while((–j)>=0 && !flag[j]);

}

return flag[m];

}

0Coyote said on February 27, 2012

The solution posted here works and is easier to understand than the one suggested in the article :

http://www.geeksforgeeks.org/archives/12450

0Bala said on June 4, 2012

Yep, the solution posted in geeksforgeeks.org is more easier to understand. To quickly understand the solution, go through the code posted there and work it with an example. Its a fairly complex problem!

0infiniteloop said on April 1, 2012

Time – O(N)

Space – O(1)

int maxDist(int* A, int n) {

int start = 0, end = n – 1;

while (start < end) {

if (A[start] < A[end]) {

return end – start;

} else if (A[start] < A[end - 1] || A[start + 1] < end) {

return end – 1 – start;

}

++start;

–end;

}

return -1;

}

0infiniteloop said on April 1, 2012

please ignore my last reply.

+1Rahul said on April 29, 2012

How come this is O(n) solution.

Last para says “Then, we proceed to the next shortest starting point” To find the next shortest each time we have to sort the list of start point which is o(nlogn) or you have to use extra space if you want to use count sort

0Rahul said on April 29, 2012

Sorry got the solution

0liuskate said on May 10, 2012

#include

#include

#include

#include

#include

using namespace std;

int maxDiff(int array[], unsigned int len)

{

assert(NULL != array && len > 0);

int maxDiff = INT_MIN;

int minLeft = array[0];

for(int i=1; i<len; ++i)

{

int diff = array[i] – minLeft;

maxDiff = max(maxDiff, diff);

minLeft = min(minLeft, array[i]);

}

return maxDiff;

}

int main()

{

int array[] = {4,3,5,2,1,3,2,3};

cout << maxDiff(array, sizeof(array)/sizeof(int)) << endl;

getchar();

return 0;

}

0Krishna Teja said on May 22, 2012

Hi, for th O(nlogn) approach, after sorting the array, for every element we need to find the maximum index in the right hand side that takes O(n2) time, so the complexity should be O(n2) isnt it ?

correct me if i am wrong.

0Krishna Teja said on May 22, 2012

what is the complexity of the above mentioned O(n) solution if the elements are in decreasing order? i believe it comes down to O(n2), because we will have n starting points.

0Eugene said on May 26, 2012

why?if the array is decreasing, you just know it is impossible to find the pair after the first scan because you can’t find the proper starting point and your function should return immediately…

0Eugene said on May 26, 2012

really can’t figure out this sentence “Then, we proceed to the next shortest starting point, and continue on from the previous ending point. ” Suppose the 6th element is 10(originally 2), how does it work?

0Eugene said on May 26, 2012

got it, much complex then I thought…

0jjlights said on January 29, 2013

I think the last solution is not O(n), it is O(n(n-k)) where k is the number of possible start points so is O(n^2) for worst case.

0xindice said on February 5, 2013

<pre

public static int GetMaxDistance(int []input)

{

if (input == null || input.Length == 0) return 0;

bool[] validstart = new bool[input.Length];

int min = input[0];

validstart[0] = true;

int i=1;

while(i<input.Length)

{

if (input[i] = 0)

{

if (validstart[i])

{

while (j > i && input[j] i)

{

int distance = j – i;

if (distance > max) max = distance;

}

}

i–;

}

return max;

}

/pre>

0xindice said on February 5, 2013

sees the html tag doesn’t work…

public static int GetMaxDistance(int []input)

{

if (input == null || input.Length == 0) return 0;

bool[] validstart = new bool[input.Length];

int min = input[0];

validstart[0] = true;

int i=1;

while(i<input.Length)

{

if (input[i] = 0)

{

if (validstart[i])

{

while (j > i && input[j] i)

{

int distance = j – i;

if (distance > max) max = distance;

}

}

i–;

}

return max;

}

0BETTERMAN said on February 10, 2013

Is it able to be solved using a recursive version?

def MaxDistance(array, length)

{

if (array[length - 1] > array[0])

return length;

else

return max(MaxDistance(array[1:], length – 1), MaxDistance(array[0:-1], length – 1))

}

0Yunsong Wu said on May 26, 2014

Yes, you can, but the time complexity will be exponential…

+1Encoder said on March 2, 2013

11 pair max_lower_dis(const vector& arr, const int MAX)

12 {

13 int beg = 0 , end = MAX;

14 int pos = beg;

15

16 while(arr[pos+1] < arr[pos])

17 pos++;

18

19 int count = 0, cur_max = 0, cur_end = 0, cur_start = 0;

20 for(int i = pos + 2; i arr[i-1])

22 {

23 count++ ;

24

25 if(count > cur_max){

26 cur_max = count;

27 cur_end = i;

28 cur_start = beg;

29 }

30

31 }

32 else

33 {

34 beg = i;

35 count = 0;

36 }

37 }

38 return make_pair(cur_start, cur_end);

39 }

40

42 int main()

43 {

44 cout <<"Enter The array number" << endl;

45 vector arr;

46

47 copy(istream_iterator(cin), istream_iterator(), back_inserter(arr));

48 pair indexPair = max_lower_dis(arr, arr.size());

49 cout << "Start = " << indexPair.first << " " << "End = " << indexPair.second << endl;

50 cout.flush();

51 copy(arr.begin() + indexPair.first, arr.begin() + indexPair.second, stream_iterator (cout,” “));

52

53 return 0;

54 }

0Encoder said on March 2, 2013

11

pair max_lower_dis(const vector& arr, const int MAX)

12 {

13 int beg = 0 , end = MAX;

14 int pos = beg;

15

16 while(arr[pos+1] < arr[pos])

17 pos++;

18

19 int count = 0, cur_max = 0, cur_end = 0, cur_start = 0;

20 for(int i = pos + 2; i arr[i-1])

22 {

23 count++ ;

24

25 if(count > cur_max){

26 cur_max = count;

27 cur_end = i;

28 cur_start = beg;

29 }

30

31 }

32 else

33 {

34 beg = i;

35 count = 0;

36 }

37 }

38 return make_pair(cur_start, cur_end);

39 }

40

42 int main()

43 {

44 cout <<"Enter The array number" << endl;

45 vector arr;

46

47 copy(istream_iterator(cin), istream_iterator(), back_inserter(arr));

48 pair indexPair = max_lower_dis(arr, arr.size());

49 cout << "Start = " << indexPair.first << " " << "End = " << indexPair.second << endl;

50 cout.flush();

51 copy(arr.begin() + indexPair.first, arr.begin() + indexPair.second, stream_iterator (cout,” “));

52

53 return 0;

54 }

0Encoder said on March 2, 2013

O(N) Solution ————–

#include

#include

#include

#include

#include

#include

using namespace std;

pair max_lower_dis(const vector& arr, const int MAX)

{

int beg = 0 , end = MAX;

int pos = beg;

while(arr[pos+1] < arr[pos])

pos++;

int count = 0, cur_max = 0, cur_end = 0, cur_start = 0;

for(int i = pos + 2; i arr[i-1])

{

count++ ;

if(count > cur_max){

cur_max = count;

cur_end = i;

cur_start = beg;

}

}

else

{

beg = i;

count = 0;

}

}

return make_pair(cur_start, cur_end);

}

int main()

{

cout <<"Enter The array number" << endl;

vector arr;

copy(istream_iterator(cin), istream_iterator(), back_inserter(arr));

pair indexPair = max_lower_dis(arr, arr.size());

cout << "Start = " << indexPair.first << " " << "End = " << indexPair.second << endl;

cout.flush();

copy(arr.begin() + indexPair.first, arr.begin() + indexPair.second, ostream_iterator(cout,” “));

return 0;

}

0jakileti vamshi krishna rao said on March 15, 2013

//i am calculating the max possible bredth for each rectangle with the height a[i]

// using the stack to find out “no of bars with ht >=a[i] both on left and right side of a[i]”

// it is O(2n) solution

int maxarea(int a[],int n) //calculates the max possible area of a rectangle in a histogram

{

stack<pair > s; // i am storing the index of a bar and also the no of bars with height>=curr bar

int max1=0,area;

pair curr,prev;

for(int i=0;ia[(s.top()).first] )

{

curr.first=i;

curr.second=0;

s.push(curr);

}

else if(a[i]<a[(s.top()).first])

{

while(!s.empty() && a[i]ht of ith bar

area=a[prev.first]*(prev.second+(i-prev.first));//area = ht* breadth

max1=max(area,max1);

}

curr.first=i;

s.push(curr);

}

}

while(!s.empty())

{

curr=s.top();

s.pop();

area=a[curr.first]*(curr.second+n-curr.first);

max1=max(area,max1);

}

return max1;

}

0jakileti vamshi krishna rao said on March 15, 2013

sorry the previous code is messed up

int maxarea(int a[],int n) //calculates the max possible area of a rectangle in a histogram

{

stack<pair > s; // i am storing the index of a bar and also the no of bars with height>=curr bar

int max1=0,area;

pair curr,prev;

for(int i=0;ia[(s.top()).first] )

{

curr.first=i;

curr.second=0;

s.push(curr);

}

else if(a[i]<a[(s.top()).first])

{

while(!s.empty() && a[i]ht of ith bar

area=a[prev.first]*(prev.second+(i-prev.first));//area = ht* breadth

max1=max(area,max1);

}

curr.first=i;

s.push(curr);

}

}

while(!s.empty())

{

curr=s.top();

s.pop();

area=a[curr.first]*(curr.second+n-curr.first);

max1=max(area,max1);

}

return max1;

}

0jakileti vamshi krishna rao said on March 15, 2013

0Gordon said on April 6, 2013

Agree with everyone else that there is no O(n) solution. For example:

[5, 4, 3, 2, 1, 4]

And the O(nlogn) is a typical Dynamic programming case I think http://en.wikipedia.org/wiki/Dynamic_programming#Algorithms_that_use_dynamic_programming

0Gordon said on April 7, 2013

Oh I cannot delete stupid comments I made? I mistaken this with the longest increasing subsequence problem http://en.wikipedia.org/wiki/Longest_increasing_subsequence

Which can also be solved in O(n)

0ehorse said on May 11, 2013

I have to be honest. This is one of most confusing posts I read on leetcode. I should have read the post by Coyote (the solution and the code on geeskforgeeks is very easy to understand) before I wasted >2hrs trying to understand it.

0Sumit said on May 27, 2013

This uses O(N) extra space, isn’t it?to keep the record of possible start-points..?

0BalaSravan said on June 17, 2013

I have solved just by placing some extra conditions in normal merge sort algorithm here is my code,, please report any erros

0newbie said on June 18, 2013

We can use a stack to solve this problem, it’s O(n) too:

public int maxDistance(int[] A) {

Stack stk = new Stack();

for (int i = 0; i A[i])

stk.push(i);

}

int maxLen = 0;

for (int i = A.length – 1; i >= maxLen; i–) {

while (!stk.empty() && A[stk.peek()] < A[i]) {

maxLen = Math.max(maxLen, i – stk.peek());

stk.pop();

}

}

return maxLen;

}

0newbie said on June 18, 2013

Use stack to solve this problem is much easier:

0newbie said on June 18, 2013

Use stack to solve this problem is much easier:

0puzzle7k said on July 21, 2013

0puzzle7k said on July 21, 2013

the code is messed up by the tag. Re-post it.

0puzzle7k said on July 21, 2013

public static int maxDistance(int[] array)

{

if(array.length<=1 || array==null)

return 0;

int i=0;

int j=1;

int distance = 0;

while(i=array[j])

{

i=j;

}

int tmp = j-i;

distance = tmp>distance?tmp:distance;

j++;

if(j==array.length)

break;

}

return distance;

}

0puzzle7k said on July 21, 2013

Retry…

0puzzle7k said on July 21, 2013

while statement is still messed up. I gave up to post it again.

0puzzle7k said on July 21, 2013

change to code to avoid the format issue i had just now.

Time complexity: O(n)

Space complexity: O(1)

0puzzle7k said on July 21, 2013

change to code to avoid the format issue i had just now.

Time complexity: O(n)

Space complexity: O(1)

0Noligz said on September 11, 2013

This will fail if the array is {5,4,6}

0Sumit said on September 21, 2013

I think we can use a BST to solve the problem as well.

The data would store both the element and its index in the original array.

When inserting a node in the right half of the tree, we just need to take care of one thing,

If the node already has a right child, overwrite it with new data.

Then, when we need to find the max difference(j-i), we just need to traverse via root and see which node has a right child first and return (node->right->data->index) – (node->data->index).

off course this will require extra space but seems more simpler to me.

o(n) solution.

0Sumit said on September 21, 2013

A slight correction. You will have to traverse down a BST and find the largest diff between (node->right->data->index) – (node->data->index) and return those indexes.

0HengZhang said on September 21, 2013

def max_distance(a):

lena=len(a)

starting_points=[0]

max=a[0]

`#finding starting points which has no greater elements on the left`

for i in range(1,lena):

if a[i] > max:

max=a[i]

starting_points.append(i)

`#traverse from right to left to calculate the distance of each starting point`

maxdis=-1

maxi=maxj=-1

for j in range(lena-1,-1,-1):

for i in starting_points:

if a[j] > a[i]:

dis=j-i

if dis>maxdis:

maxdis=dis

maxi=i

maxj=j

`print('max='+str(maxdis)+'-i='+str(maxi)+'j='+str(maxj))`

0HengZhang said on September 21, 2013

def max_distance(a):

lena=len(a)

starting_points=[0]

max=a[0]

`#finding starting points which has no greater elements on the left`

for i in range(1,lena):

if a[i] > max:

max=a[i]

starting_points.append(i)

`#traverse from right to left to calculate the distance of each starting point`

maxdis=-1

maxi=maxj=-1

for j in range(lena-1,-1,-1):

for i in starting_points:

if a[j] > a[i]:

dis=j-i

if dis>maxdis:

maxdis=dis

maxi=i

maxj=j

`print('max='+str(maxdis)+'-i='+str(maxi)+'j='+str(maxj))`

0Di said on October 28, 2013

I am not sure about the O(n) complexity. I understand the first step of finding local min points as the starting points, which together cover the whole sequence. But I think we still may need O(nlogn) operation after that. Thinking about the follwing input:

10 8 6 4 2 0 9 7 5 3 1

A scan would be enough to find out 10 8 6 4 2 0 as the min points, but how could we decide which min point 9, 7, 5 , 3 , 1 should pair up with respecitively? Doesn’t this take at least a binary seach for each number?

Did I miss anything?

Thanks?

+1forever said on December 25, 2013

elements in LMin:{10,8,6,4,2,0}, in RMax:{10,9,7,5,3,1}

traverse distance pair (i,j) goes through like:

10,10

8,9

6,7

4,5,

3,3

0,1

Basically query time for any element in LMin is O(1). totally worst running time is O(N).

from Coyote’s refer http://www.geeksforgeeks.org/archives/12450

0Mukit said on November 28, 2013

Really nice explanation. Specially proving that is will bound within O(n) is really cool !

+1lunci said on December 10, 2013

This is my solution. Simply divide the array into several segments, and calculate max distance for each segment.

0Max said on January 13, 2014

I don’t think the O(nlgn) solution is right, may be my understanding is wrong.

For example, we have array

idx 0 1 2 3 4 5 6 7 8

val 4 3 5 2 3 2 1 3 2 so the sorted array will be====>

val 1 2 2 2 3 3 3 4 5

idx 6 3 5 8 1 4 7 0 2

8 8 8 8 7 7 7 2 2 so how can we find out the longest distance (original i is 3, original j is 7)

0Zheng Xu said on January 17, 2014

0leetrv said on January 26, 2014

public int distanceMaxIndex(int[] a){

int len = a.length;

int i=0;

int j=len-1;

while(i=0){

while(ia[i+1])

i++;

while(j>0 && a[j]=0) j–;

if( j-i >0 ) return j-i ;

return -1;

}

return -1;

}

Plz let me know my understanding about the problem is correct or not?

0leetrv said on January 26, 2014

Plz let me know my understanding about the problem is correct or not?

0leetrv said on January 26, 2014

0theOtherWC said on March 5, 2014

This is so smart.

0Emacs Zhang said on April 27, 2014

0Abhinav said on May 5, 2014

“Then, we proceed to the next shortest starting point, and continue on from the previous ending point. ”

How do we move to the next shortest starting point ?? what is the time complexity for doing this….

0Yunsong Wu said on May 26, 2014

The starting points are automatically stored in a descending order.

0que1 said on May 8, 2014

+1 same question here. If we have O(N) starting points and in the worst case we need to sort the array of starting points in order to get the next shortest starting point, the next next shortest one, … , the O(N)-th shortest one, which costs O(NlogN) instead of O(N). Hope my question is not stupid.

0huz said on May 17, 2014

not sure if the distance equal case was handled correctly, will need some more thoughts on it

0Bhaskar Bagchi said on May 22, 2014

I think this can also be a solution. Please correct me if I am worng..

0Bhaskar said on May 22, 2014

I think it also be a solution. Please correct me if it is wrong.

0rong said on July 16, 2014

Could some check my code?

int maxDist(int A[], int n) {

if (n == 0 || n == 1) return -1;

stack desc;

desc.push(0);

for (int i = 1; i < n; i++) {

if (A[i] = 0 && A[end] <= A[desc.top()]) {

end–;

}

result = max(result, end – desc.top());

desc.pop();

}

return result;

}

0rong said on July 16, 2014

Could someone check my code?

0rong said on July 16, 2014

Why my code looks not like I typed?

0rong said on July 16, 2014

0rong said on July 16, 2014

Cannot display my code normally !! Even I used “

“

0Jianbo Ye said on November 13, 2014

Exactly, the website is so weird.

0Girish said on August 23, 2014

This should do it, right? https://ideone.com/AolfKL

0Girish said on August 23, 2014

The overall complexity should be O(n) as we can achieve this in a single pass of the array.

0robinzou said on October 31, 2014

public void find(int[] array) {

int[] indexes = new int[array.length];

int offset = -1;

int min = Integer.MAX_VALUE;

for(int i = 0; i < array.length; i ++)

if(array[i] 0; i --) {

int bigger = array[i];

int smaller = array[indexes[offset]];

while(bigger > smaller) {

int offsetDiff = i - indexes[offset];

maxDiff = offsetDiff;

maxDiffBigIndex = i;

maxDiffSmallIndex = indexes[offset];

`offset --;`

smaller = array[indexes[offset]];

}

}

`System.out.println("bigger index: " + maxDiffBigIndex + ", smaller index: " + maxDiffSmallIndex + ", Max index diff: " + maxDiff);`

}

0fei said on November 5, 2014

still not convinced solution 2 is O(n). the worst case is every element could be starting point, so the time is still O(n^2)

0Jianbo Ye said on November 13, 2014

This is a REAL O(n) solution, which of course is different from what has been described in the original post.

Enjoy.

https://gist.github.com/4b2da9d0e9ab58194ac2.git

0Jianbo Ye said on November 13, 2014

This is the complete code …

0Jianbo Ye said on November 13, 2014

This website can not display my code normally … please checkout the gist version

https://gist.github.com/4b2da9d0e9ab58194ac2.git

0