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 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.1/5 (29 votes cast)
A Distance Maximizing Problem, 4.1 out of 5 based on 29 ratings

117 responses to A Distance Maximizing Problem

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

    VA:F [1.9.22_1171]
    +2
    • NO that is the maximum a[j]-a[i] such that j>i it is different

      VN:F [1.9.22_1171]
      0
      • 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
        • 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. 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. 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. 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
    • Obviously, it’s not correct. The array isn’t sorted.

      VN:F [1.9.22_1171]
      0
    • 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. 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
    • 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
      • Try again to format the code:

        VA:F [1.9.22_1171]
        0
  6. 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
  7. 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. Would it work…I guess it will :)

    VA:F [1.9.22_1171]
    0
    • 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
      • You could change the else statement as follows to significantly save the comparisons:

        VN:F [1.9.22_1171]
        0
  9. 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
    • 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. 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. 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
    • 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
      • 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. 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
    • 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
      • 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. 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. 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. Can u please elaborate your second solution. I could not follow

    1. how you construct the table
    2.how you compute the max distance

    VN:F [1.9.22_1171]
    0
  16. 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).

    VN:F [1.9.22_1171]
    0
  17. 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
    • 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
  18. 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
  19. 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
  20. 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
  21. The solution posted here works and is easier to understand than the one suggested in the article :

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

    VN:F [1.9.22_1171]
    0
    • 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
  22. 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
  23. please ignore my last reply.

    VN:F [1.9.22_1171]
    +1
  24. 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
  25. Sorry got the solution

    VA:F [1.9.22_1171]
    0
  26. #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
  27. 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
  28. 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.

    VN:F [1.9.22_1171]
    0
    • 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
  29. 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
  30. got it, much complex then I thought…

    VN:F [1.9.22_1171]
    0
  31. 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
  32. <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
    • 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
  33. 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
  34. 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
  35. 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
  36. 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
  37. //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
  38. 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
  39. VA:F [1.9.22_1171]
    0
  40. 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

    VN:F [1.9.22_1171]
    0
  41. 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
  42. This uses O(N) extra space, isn’t it?to keep the record of possible start-points..?

    VN:F [1.9.22_1171]
    0
  43. 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
  44. 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;
    }

    VN:F [1.9.22_1171]
    0
  45. Use stack to solve this problem is much easier:

    VN:F [1.9.22_1171]
    0
  46. Use stack to solve this problem is much easier:

    VN:F [1.9.22_1171]
    0
  47. VN:F [1.9.22_1171]
    0
    • the code is messed up by the tag. Re-post it.

      VN:F [1.9.22_1171]
      0
      • 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
        • Retry…

          VN:F [1.9.22_1171]
          0
          • while statement is still messed up. I gave up to post it again.

            VN:F [1.9.22_1171]
            0
  48. 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
    • 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
  49. 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
    • 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.

      VN:F [1.9.22_1171]
      0

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

  51. 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
  52. 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
  53. Really nice explanation. Specially proving that is will bound within O(n) is really cool !

    VA:F [1.9.22_1171]
    +1
  54. 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
  55. 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
  56. VA:F [1.9.22_1171]
    0
  57. 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?

    VN:F [1.9.22_1171]
    0
  58. Plz let me know my understanding about the problem is correct or not?

    VN:F [1.9.22_1171]
    0
    • VN:F [1.9.22_1171]
      0
  59. This is so smart.

    VA:F [1.9.22_1171]
    0
  60. VN:F [1.9.22_1171]
    0
  61. “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
  62. que1 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.

    VN:F [1.9.22_1171]
    0
  63. huz said on May 17, 2014

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

    VA:F [1.9.22_1171]
    0
  64. I think this can also be a solution. Please correct me if I am worng..

    VA:F [1.9.22_1171]
    0
  65. I think it also be a solution. Please correct me if it is wrong.

    VA:F [1.9.22_1171]
    0
  66. 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;
    }

    VA:F [1.9.22_1171]
    0
  67. Could someone check my code?

    VA:F [1.9.22_1171]
    0
    • Why my code looks not like I typed?

      VA:F [1.9.22_1171]
      0
      • VA:F [1.9.22_1171]
        0
  68. This should do it, right? https://ideone.com/AolfKL

    VA:F [1.9.22_1171]
    0
    • The overall complexity should be O(n) as we can achieve this in a single pass of the array.

      VA:F [1.9.22_1171]
      0

  69. 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
  70. 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
  71. 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
    • This is the complete code …

      VA:F [1.9.22_1171]
      0
  72. VA:F [1.9.22_1171]
    0
  73. Can you image a world without any exercise? If the world without any movement, what the world will be like nike tn Pas Cher ? It will be a boring, dull, lifeless world. It is awful and horrible. Walking is an essential exercise in our daily life, even driving cars to go everywhere, we still need walk to working places. Today, in order to relieve their burden in the competitive society, persons are doing more exercise. As a result, people are paying more and more attention to their sports shoes. They need excellent sports shoes to protect their feet and provide the greatest comfort to their feet. In the past, most persons have a wrong idea that doing sports can reach the effect of exercise, do not need to consider the sports shoes.

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

1 trackback