A Distance Maximizing Problem

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 ith 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 ith line corresponds to the ith 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(N2)
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(N2) 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…

VN:F [1.9.22_1171]
Rating: 4.0/5 (34 votes cast)
A Distance Maximizing Problem, 4.0 out of 5 based on 34 ratings

122 thoughts on “A Distance Maximizing Problem

  1. airfang

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

    VA:F [1.9.22_1171]
    +3
      1. zyfo2

        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

        VA:F [1.9.22_1171]
        +3
        1. theOtherWC

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

          VA:F [1.9.22_1171]
          0
  2. polynomial

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

    VA:F [1.9.22_1171]
    0
  3. Onlogn

    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.

    VA:F [1.9.22_1171]
    0
  4. bpin

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

    the final value of imin and imax will be the answer

    VA:F [1.9.22_1171]
    0
    1. Bond

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

      VA:F [1.9.22_1171]
      0
  5. Jagdish

    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;
    }

    VA:F [1.9.22_1171]
    +1
    1. bluesun

      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.

      VA:F [1.9.22_1171]
      0
      1. bluesun

        Try again to format the code:

        VA:F [1.9.22_1171]
        0
  6. Anonymous

    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.

    VA:F [1.9.22_1171]
    0
    1. Anonymous

      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;
      }
      ]]>

      VA:F [1.9.22_1171]
      0
      1. Anonymous

        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;
        }

        VA:F [1.9.22_1171]
        0
        1. Anonymous

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

          VA:F [1.9.22_1171]
          0
          1. aimless

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

            VA:F [1.9.22_1171]
            0
          2. GameSeven

            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)

            VA:F [1.9.22_1171]
            0
  7. DaRkLoRd

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

    I hope I am clear…

    VA:F [1.9.22_1171]
    0
  8. anothergeek

    Would it work…I guess it will :)

    VA:F [1.9.22_1171]
    0
    1. anothergeek

      Ignore the previous code…here is the correct version
      (An improved version of the code at geeksforgeeks in terms of extra memory)

      VA:F [1.9.22_1171]
      0
      1. Profile photo of Brady FangBrady Fang

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

        VN:F [1.9.22_1171]
        0
  9. bpin

    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

    VA:F [1.9.22_1171]
    0
    1. bpin

      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)

      VA:F [1.9.22_1171]
      +1
  10. Omri

    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?

    VA:F [1.9.22_1171]
    +2
  11. Manish Agarwal

    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));
    }
    }

    VA:F [1.9.22_1171]
    0
    1. Sean

      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?

      VA:F [1.9.22_1171]
      0
      1. Sean

        Ok, I added the code to get values for lMin, now I think your code is working fine.
        Very clean code. Good job!

        VA:F [1.9.22_1171]
        0
  12. fzzh24

    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)

    VA:F [1.9.22_1171]
    0
    1. fzzh24

      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

      VA:F [1.9.22_1171]
      0
      1. Prateek Caire

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

        VA:F [1.9.22_1171]
        0
  13. hbs

    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;
    }

    VA:F [1.9.22_1171]
    0
  14. maxq

    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.

    VA:F [1.9.22_1171]
    0
  15. David Roid

    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.

    VA:F [1.9.22_1171]
    0
    1. David Roid

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

      VA:F [1.9.22_1171]
      0
  16. Profile photo of Kumar AbhishekKumar Abhishek

    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/

    VN:F [1.9.22_1171]
    0
  17. Coby

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

    VA:F [1.9.22_1171]
    +1
  18. Lao Ye

    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];
    }

    VA:F [1.9.22_1171]
    0
    1. Bala

      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!

      VA:F [1.9.22_1171]
      0
  19. Profile photo of infiniteloopinfiniteloop

    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;
    }

    VN:F [1.9.22_1171]
    0
  20. Rahul

    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

    VA:F [1.9.22_1171]
    0
  21. Profile photo of liuskateliuskate

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

    VN:F [1.9.22_1171]
    0
  22. Profile photo of Krishna TejaKrishna Teja

    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.

    VN:F [1.9.22_1171]
    0
    1. Profile photo of EugeneEugene

      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…

      VN:F [1.9.22_1171]
      0
  23. Profile photo of EugeneEugene

    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?

    VN:F [1.9.22_1171]
    0
  24. jjlights

    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.

    VA:F [1.9.22_1171]
    0
  25. xindice

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

    VA:F [1.9.22_1171]
    0
    1. xindice

      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;
      }

      VA:F [1.9.22_1171]
      0
  26. Profile photo of BETTERMANBETTERMAN

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

    VN:F [1.9.22_1171]
    0
  27. Encoder

    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 }

    VA:F [1.9.22_1171]
    0
  28. Encoder

    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 }

    VA:F [1.9.22_1171]
    0
  29. Encoder

    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;
    }

    VA:F [1.9.22_1171]
    0
  30. jakileti vamshi krishna rao

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

    VA:F [1.9.22_1171]
    0
  31. jakileti vamshi krishna rao

    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;
    }

    VA:F [1.9.22_1171]
    0
  32. jakileti vamshi krishna rao

    VA:F [1.9.22_1171]
    0
  33. ehorse

    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.

    VA:F [1.9.22_1171]
    0
  34. BalaSravan

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

    VA:F [1.9.22_1171]
    0
  35. Profile photo of newbienewbie

    Use stack to solve this problem is much easier:

    VN:F [1.9.22_1171]
    0
  36. Profile photo of newbienewbie

    Use stack to solve this problem is much easier:

    VN:F [1.9.22_1171]
    0
  37. Profile photo of puzzle7kpuzzle7k

    VN:F [1.9.22_1171]
    0
    1. Profile photo of puzzle7kpuzzle7k

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

      VN:F [1.9.22_1171]
      0
      1. Profile photo of puzzle7kpuzzle7k

        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;
        }

        VN:F [1.9.22_1171]
        0
        1. Profile photo of puzzle7kpuzzle7k

          Retry…

          VN:F [1.9.22_1171]
          0
  38. Profile photo of puzzle7kpuzzle7k

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

    Time complexity: O(n)
    Space complexity: O(1)

    VN:F [1.9.22_1171]
    0
    1. Profile photo of puzzle7kpuzzle7k

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

      Time complexity: O(n)
      Space complexity: O(1)

      VN:F [1.9.22_1171]
      0
  39. Sumit

    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.

    VA:F [1.9.22_1171]
    0
  40. Profile photo of HengZhangHengZhang


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

    VN:F [1.9.22_1171]
    0
  41. Profile photo of HengZhangHengZhang


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

    VN:F [1.9.22_1171]
    0
  42. Profile photo of DiDi

    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?

    VN:F [1.9.22_1171]
    +1
  43. Profile photo of luncilunci

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

    VN:F [1.9.22_1171]
    0
  44. Profile photo of MaxMax

    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)

    VN:F [1.9.22_1171]
    0
  45. Zheng Xu

    VA:F [1.9.22_1171]
    0
  46. Profile photo of leetrvleetrv

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

    VN:F [1.9.22_1171]
    0
    1. Profile photo of leetrvleetrv

      VN:F [1.9.22_1171]
      0
  47. Profile photo of Emacs ZhangEmacs Zhang

    VN:F [1.9.22_1171]
    0
  48. Abhinav

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

    VA:F [1.9.22_1171]
    0
  49. Profile photo of que1que1

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

    VN:F [1.9.22_1171]
    0
  50. huz

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

    VA:F [1.9.22_1171]
    0
  51. Bhaskar Bagchi

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

    VA:F [1.9.22_1171]
    0
  52. Bhaskar

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

    VA:F [1.9.22_1171]
    0
  53. rong

    Could someone check my code?

    VA:F [1.9.22_1171]
    0
      1. rong

        VA:F [1.9.22_1171]
        0
  54. Pingback: A Distance Maximizing Problem | more water

  55. robinzou


    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);
    }

    VA:F [1.9.22_1171]
    0
  56. fei

    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)

    VA:F [1.9.22_1171]
    0
  57. Jianbo Ye

    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

    VA:F [1.9.22_1171]
    0
    1. Jianbo Ye

      This is the complete code …

      VA:F [1.9.22_1171]
      0
  58. bluenosetiger

    VA:F [1.9.22_1171]
    0
    1. Profile photo of beiyebeiye

      Holy,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!

      VN:F [1.9.22_1171]
      0
  59. Nameless

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

    VA:F [1.9.22_1171]
    0
  60. haha

    What 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}?

    VA:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.