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…**

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

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

0yet 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

+3Great observation.

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

0Can 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).

01 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.

0Ops… sorry for the ugly format :/

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

the final value of imin and imax will be the answer

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

0I think no, because u are assuming that min will be in first half and max will be in second half

of the arry, it need not be always tru, min and max both can be in first half of the array

then wat will you do

0Build 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;

}

+1Got 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.

0Try again to format the code:

0O(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.

0Code 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;

}

]]>

0CDATA 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;

}

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

0use

http://ideone.com

u can paste your code here

0@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.

0can’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)

0i 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 = 2

I hope I am clear…0Would it work…I guess it will

0Ignore the previous code…here is the correct version

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

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

0Is 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

0TheArray = [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)

+1On 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?

+3import 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));

}

}

0Your 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?

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

Very clean code. Good job!

0O(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)

0Sorry, 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

0Correct 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..

0Let 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;

}

0For 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.

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

1. how you construct the table

2.how you compute the max distance

0I’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).

0I 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.

0I 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..

0The 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/

0Hi,

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).

+1int 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];

}

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

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

0Yep, 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!

0Time – 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;

}

0please ignore my last reply.

+1How 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

0Sorry got the solution

0#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;

}

0Hi, 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.

0what 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.

0why?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…

0really 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?

0got it, much complex then I thought…

0I 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.

0<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>

0sees 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;

}

0Is 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))

}

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

+111 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 }

011

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 }

0O(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;

}

0//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;

}

0sorry 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;

}

00Agree 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

0Oh 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)

0I 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.

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

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

0We 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;

}

0Use stack to solve this problem is much easier:

0Use stack to solve this problem is much easier:

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

0public 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;

}

0Retry…

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

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

Time complexity: O(n)

Space complexity: O(1)

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

Time complexity: O(n)

Space complexity: O(1)

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

0I 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.

0A 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.

0def 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))`

0def 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))

0I 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?

+1elements 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

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

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

0I 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)

00public 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?

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

00This is so smart.

00“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….

0The starting points are automatically stored in a descending order.

0+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.

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

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

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

0Could 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;

}

0Could someone check my code?

0Why my code looks not like I typed?

00Cannot display my code normally !! Even I used “

”

0Exactly, the website is so weird.

0Pingback: A Distance Maximizing Problem | more water

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

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

0public 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);`

}

0still 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)

0This 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

0This is the complete code …

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

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

001. start from Min->A[0],Max-> A[n-1];

2. if Min A[n-2]-A[n-1]) then Min->A[1], else Max->A[n-2];

5. repeat step2,3,4.

n steps at most!

0Holy,why were two lines missing?

Try again:

1. start from Min->A[0],Max-> A[n-1];

2. If MinMax, then….do step4

4. if Min A[n-2]-A[n-1]) then Min->A[1], else Max->A[n-2];

5. repeat step2,3,4.

n steps at most!

0Drive me crazy, the website changes my words randomly.

But the my solution still looks sort of make sense. Hope someone can give me some comment.

0Can anyone tells me if the above code is correct what the time complexity is?

0What is the time complexity of the algorithm stated at the last part when the input array is { 1,2,3,4,5,6,7,…..,n}?

0