47

Given an unsorted array, find the max j - i difference between indices such that j > i and a[j] > a[i] in O(n). I am able to find j and i using trivial methods in O(n^2) complexity but would like to know how to do this in O(n)?

Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}

Output: 8 ( j = 8, i = 0)

Input: {1, 2, 3, 4, 5, 6}

Output: 5 (j = 5, i = 0)

23
  • 4
    I can think of two ways to do it in O(NlogN). Gonna have to think awhile to see if O(N) is possible.
    – WhozCraig
    Aug 16, 2013 at 20:34
  • 3
    What happens if the array is sorted in a decreasing order? No solution?
    – liori
    Aug 16, 2013 at 20:46
  • 1
    I don't see what sorting or binary search or any algorithm that has a lg N factor in its big-O complexity, might have to do with the solution? The array is unsorted. The question asks for two elements in it that are farthest apart which satisfy an inequality. Aug 16, 2013 at 21:20
  • 14
    This is known as the 'stock-market problem', and is a pretty standard homework assignment for undergraduate algorithms courses. Aug 18, 2013 at 20:29
  • 1
    @PhilMiller Are you talking about the problem in the question ?
    – rainyday
    Jan 22, 2019 at 16:05

15 Answers 15

40
+50

For brevity's sake I am going to assume all the elements are unique. The algorithm can be extended to handle non-unique element case.

First, observe that if x and y are your desired max and min locations respectively, then there can not be any a[i] > a[x] and i > x, and similarly, no a[j] < a[y] and j < y.

So we scan along the array a and build an array S such that S[i] holds the index of the minimum element in a[0:i]. Similarly an array T which holds the index of the maximum element in a[n-1:i] (i.e., backwards).

Now we can see that a[S[i]] and a[T[i]] are necessarily decreasing sequences, since they were the minimum till i and maximum from n till i respectively.

So now we try to do a merge-sort like procedure. At each step, if a[S[head]] < a[T[head]], we pop off an element from T, otherwise we pop off an element from S. At each such step, we record the difference in the head of S and T if a[S[head]] < a[T[head]]. The maximum such difference gives you your answer.

EDIT: Here is a simple code in Python implementing the algorithm.

def getMaxDist(arr):

    # get minima going forward
    minimum = float("inf")
    minima = collections.deque()
    for i in range(len(arr)):
        if arr[i] < minimum:
            minimum = arr[i]
            minima.append((arr[i], i))

    # get maxima going back
    maximum = float("-inf")
    maxima = collections.deque()
    for i in range(len(arr)-1,0,-1):
        if arr[i] > maximum:
            maximum = arr[i]
            maxima.appendleft((arr[i], i))

    # do merge between maxima and minima
    maxdist = 0
    while len(maxima) and len(minima):
        if maxima[0][0] > minima[0][0]:
            if maxima[0][1] - minima[0][1] > maxdist:
                maxdist = maxima[0][1] - minima[0][1]
            maxima.popleft()
        else:
            minima.popleft()

    return maxdist
4
  • Remember that popleft takes linear time Aug 22, 2013 at 18:32
  • 2
    @ThomasAhle This is a deque implemented as a linked list (hopefully), so should not be linear time, docs.python.org/release/2.5.2/lib/deque-objects.html Aug 22, 2013 at 18:35
  • Sorry, didn't see you weren't using a list :-) Aug 23, 2013 at 8:12
  • You got the popleft wrong. if maxima[0][0] > minima[0][0]: minima.popleft() else: maxima.popleft() Oct 2, 2017 at 15:34
4

Let's make this simple observation: If we have 2 elements a[i], a[j] with i < j and a[i] < a[j] then we can be sure that j won't be part of the solution as the first element (he can be the second but that's a second story) because i would be a better alternative.

What this tells us is that if we build greedily a decreasing sequence from the elements of a the left part of the answer will surely come from there.

For example for : 12 3 61 23 51 2 the greedily decreasing sequence is built like this:

12 -> 12 3 -> we ignore 61 because it's worse than 3 -> we ignore 23 because it's worse than 3 -> we ignore 51 because it's worse than 3 -> 12 3 2.

So the answer would contain on the left side 12 3 or 2.

Now on a random case this has O(log N) length so you can binary search on it for each element as the right part of the answer and you would get O(N log log N) which is good, and if you apply the same logic on the right part of the string on a random case you could get O(log^2 N + N(from the reading)) which is O(N). But we can do O(N) on a non-random case too.

Suppose we have this decreasing sequence. We start from the right of the string and do the following while we can pair the last of the decreasing sequence with the current number

1) If we found a better solution by taking the last of the decreasing sequence and the current number than we update the answer

2) Even if we updated the answer or not we pop the last element of the decreasing sequence because we are it's perfect match (any other match would be to the left and would give an answer with smaller j - i)

3) Repeat while we can pair these 2

Example Code:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N; cin >> N;

    vector<int> A(N + 1);
    for (int i = 1; i <= N; ++i)
        cin >> A[i];

    // let's solve the problem
    vector<int> decreasing; 

    pair<int, int> answer;

    // build the decreasing sequence
    decreasing.push_back(1);
    for (int i = 1; i <= N; ++i)
        if (A[i] < A[decreasing.back()])
            decreasing.push_back(i); // we work with indexes because we might have equal values

    for (int i = N; i > 0; --i) {
        while (decreasing.size() and A[decreasing.back()] < A[i]) { // while we can pair these 2
            pair<int, int> current_pair(decreasing.back(), i);
            if (current_pair.second - current_pair.first > answer.second - answer.first)
                answer = current_pair;
            decreasing.pop_back();
        }
    }

    cout << "Best pair found: (" << answer.first << ", " << answer.second << ") with values (" << A[answer.first] << ", " << A[answer.second] << ")\n";
}

Later Edit: I see you gave an example: I indexed from 1 to make it clearer and I print (i, j) instead of (j, i). You can alter it as you see fit.

1
  • 2
    your words after "Suppose we have this decreasing sequence." is impossible to understand
    – windchime
    Nov 7, 2018 at 22:19
3

We can avoid checking the whole array by starting from the maximum difference of j-i and comparing arr[j]>arr[i] for all the possible combinations j and i for that particular maximum difference Whenever we get a combination of (j,i) with arr[j]>arr[i] we can exit the loop

Example : In an array of {2,3,4,5,8,1} first code will check for maximum difference 5(5-0) i.e (arr[0],arr[5]), if arr[5]>arr[0] function will exit else will take combinations of max diff 4 (5,1) and (4,0) i.e arr[5],arr[1] and arr[4],arr[0]

int maxIndexDiff(int arr[], int n)
{
    int maxDiff = n-1;
    int i, j;

    while (maxDiff>0)
    {
        j=n-1;
        while(j>=maxDiff)
        {
            i=j - maxDiff;
            if(arr[j]>arr[i])
            { 
                return maxDiff;  
            }
            j=j-1;
        }
        maxDiff=maxDiff-1;
    }
    return -1;  
}`

https://ide.geeksforgeeks.org/cjCW3wXjcj

2

Here is a very simple O(n) Python implementation of the merged down-sequence idea. The implementation works even in the case of duplicate values:

downs = [0]
for i in range(N):
    if ar[i] < ar[downs[-1]]:
        downs.append(i)

best = 0
i, j = len(downs)-1, N-1
while i >= 0:
    if ar[downs[i]] <= ar[j]:
        best = max(best, j-downs[i])
        i -= 1
    else:
        j -= 1
print best
2

To solve this problem, we need to get two optimum indexes of arr[]: left index i and right index j. For an element arr[i], we do not need to consider arr[i] for left index if there is an element smaller than arr[i] on left side of arr[i]. Similarly, if there is a greater element on right side of arr[j] then we do not need to consider this j for right index. So we construct two auxiliary arrays LMin[] and RMax[] such that LMin[i] holds the smallest element on left side of arr[i] including arr[i], and RMax[j] holds the greatest element on right side of arr[j] including arr[j]. After constructing these two auxiliary arrays, we traverse both of these arrays from left to right. While traversing LMin[] and RMa[] if we see that LMin[i] is greater than RMax[j], then we must move ahead in LMin[] (or do i++) because all elements on left of LMin[i] are greater than or equal to LMin[i]. Otherwise we must move ahead in RMax[j] to look for a greater j – i value. Here is the c code running in O(n) time:

#include <stdio.h>
#include <stdlib.h>

/* Utility Functions to get max and minimum of two integers */
int max(int x, int y)
{
    return x > y? x : y;
}

int min(int x, int y)
{
    return x < y? x : y;
}

/* For a given array arr[], returns the maximum j – i such that
    arr[j] > arr[i] */
int maxIndexDiff(int arr[], int n)
{
    int maxDiff;
    int i, j;

    int *LMin = (int *)malloc(sizeof(int)*n);
    int *RMax = (int *)malloc(sizeof(int)*n);

   /* Construct LMin[] such that LMin[i] stores the minimum value
       from (arr[0], arr[1], ... arr[i]) */
    LMin[0] = arr[0];
    for (i = 1; i < n; ++i)
        LMin[i] = min(arr[i], LMin[i-1]);

    /* Construct RMax[] such that RMax[j] stores the maximum value
       from (arr[j], arr[j+1], ..arr[n-1]) */
    RMax[n-1] = arr[n-1];
    for (j = n-2; j >= 0; --j)
        RMax[j] = max(arr[j], RMax[j+1]);

    /* Traverse both arrays from left to right to find optimum j - i
        This process is similar to merge() of MergeSort */
    i = 0, j = 0, maxDiff = -1;
    while (j < n && i < n)
    {
        if (LMin[i] < RMax[j])
        {
            maxDiff = max(maxDiff, j-i);
            j = j + 1;
        }
        else
            i = i+1;
    }

    return maxDiff;
}

/* Driver program to test above functions */
int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int maxDiff = maxIndexDiff(arr, n);
    printf("\n %d", maxDiff);
    getchar();
    return 0;
}
1

Simplified version of Subhasis Das answer using auxiliary arrays.

def maxdistance(nums):
    n = len(nums)
    minima ,maxima = [None]*n, [None]*n
    minima[0],maxima[n-1] = nums[0],nums[n-1]
    for i in range(1,n):
        minima[i] = min(nums[i],minima[i-1])
    for i in range(n-2,-1,-1):
        maxima[i]= max(nums[i],maxima[i+1])

    i,j,maxdist = 0,0,-1
    while(i<n and j<n):
        if minima[i] <maxima[j]:
            maxdist = max(j-i,maxdist)
            j = j+1
        else:
            i += 1
    print maxdist
0

I can think of improvement over O(n^2), but need to verify if this is O(n) in worse case or not.

  • Create a variable BestSoln=0; and traverse the array for first element and store the best solution for first element i.e bestSoln=k;.
  • Now for 2nd element consider only elements which are k distances away from the second element.
  • If BestSoln in this case is better than first iteration then replace it otherwise let it be like that. Keep iterating for other elements.

It can be improved further if we store max element for each subarray starting from i to end. This can be done in O(n) by traversing the array from end. If a particular element is more than it's local max then there is no need to do evaluation for this element.

Input:

{9, 2, 3, 4, 5, 6, 7, 8, 18, 0}

create local max array for this array:

[18,18,18,18,18,18,18,0,0] O(n).

Now, traverse the array for 9 ,here best solution will be i=0,j=8. Now for second element or after it, we don't need to evaluate. and best solution is i=0,j=8.

But suppose array is Input:

{19, 2, 3, 4, 5, 6, 7, 8, 18, 0,4}

Local max array [18,18,18,18,18,18,18,0,0] then in first iteration we don't need to evaluate as local max is less than current elem.

Now for second iteration best solution is, i=1,j=10. Now for other elements we don't need to consider evaluation as they can't give best solution.

Let me know your view your use case to which my solution is not applicable.

0

This is a very simple solution for O(2n) of speed and additional ~O(2n) of space (in addition to the input array). The following implementation is in C:

int findMaxDiff(int array[], int size) {

    int index = 0;
    int maxima[size];
    int indexes[size];

    while (index < size) {
        int max = array[index];
        int i;
        for (i = index; i < size; i++) {
            if (array[i] > max) {
                max = array[i];
                indexes[index] = i;
            }
        }
        maxima[index] = max;
        index++;
    }

    int j;
    int result;
    for (j = 0; j < size; j++) {
        int max2 = 0;
        if (maxima[j] - array[j] > max2) {
            max2 = maxima[j] - array[j];
            result = indexes[j];
        }
    }

    return result;
}

The first loop scan the array once, finding for each element the maximum of the remaining elements to its right. We store also the relative index in a separate array. The second loops finds the maximum between each element and the correspondent right-hand-side maximum, and returns the right index.

0

My Solution with in O(log n) (Please correct me here if I am wrong in calculating this complexity)time ...

Idea is to insert into a BST and then search for node and if the node has a right child then traverse through the right sub tree to calculate the node with maximum index..

    import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{

    public static void main (String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t1 = Integer.parseInt(br.readLine());
        for(int j=0;j<t1;j++){
            int size = Integer.parseInt(br.readLine());
            String input = br.readLine();
            String[] t = input.split(" ");
            Node root = new Node(Integer.parseInt(t[0]),0);
            for(int i=1;i<size;i++){
                Node addNode = new Node(Integer.parseInt(t[i]),i);
                insertIntoBST(root,addNode);                
            }
            for(String s: t){
                Node nd = findNode(root,Integer.parseInt(s));
                if(nd.right != null){
                    int i = nd.index;
                    int j1 = calculate(nd.right);
                    mVal = max(mVal,j1-i);
                }

            }

            System.out.println(mVal);
            mVal=0;
        }
    }

    static int mVal =0;

    public static int calculate (Node root){
        if(root==null){
            return -1;
        }
        int i = max(calculate(root.left),calculate(root.right));
        return max(root.index,i);
    }

    public static Node findNode(Node root,int n){
        if(root==null){
            return null;
        }
        if(root.value == n){
            return root;
        }
        Node result = findNode(root.left,n);
        if(result ==null){
            result = findNode(root.right,n);   
        }
        return result;
    }

    public static int max(int a , int b){
        return a<b?b:a;
    }

    public static class Node{
        Node left;
        Node right;
        int value;
        int index;

        public Node(int value,int index){
            this.value = value;
            this.index = index;
        }
    }

    public static void insertIntoBST(Node root, Node addNode){

        if(root.value< addNode.value){
            if(root.right!=null){
                insertIntoBST(root.right,addNode);              
            }else{
                root.right = addNode;
            }
        }
        if(root.value>=addNode.value){
            if(root.left!=null){
                insertIntoBST(root.left,addNode);               
            }else{
                root.left =addNode;
            }
        }
    }


}
1
  • 1
    You have to access each array element at least once, so the best solution should take Ω(N) time. Also notice that BST will not give you log N automatically, it should be a self-balancing one.
    – Evg
    Feb 21, 2019 at 20:54
0

A simplified algorithm from Subhasis Das's answer:

# assume list is not empty
max_dist = 0
acceptable_min = (0, arr[0])
acceptable_max = (0, arr[0])
min = (0, arr[0])

for i in range(len(arr)):
  if arr[i] < min[1]:
    min = (i, arr[i])
  elif arr[i] - min[1] > max_dist:
    max_dist = arr[i] - min[1]
    acceptable_min = min
    acceptable_max = (i, arr[i])

# acceptable_min[0] is the i
# acceptable_max[0] is the j
# max_dist is the max difference
0

Below is a C++ solution for the condition a[i] <= a[j]. It needs a slight modification to handle the case a[i] < a[j].

template<typename T>
std::size_t max_dist_sorted_pair(const std::vector<T>& seq)
{
    const auto n = seq.size();
    const auto less = [&seq](std::size_t i, std::size_t j)
        { return seq[i] < seq[j]; };

    // max_right[i] is the position of the rightmost
    // largest element in the suffix seq[i..]
    std::vector<std::size_t> max_right(n);

    max_right.back() = n - 1;
    for (auto i = n - 1; i > 0; --i)
        max_right[i - 1] = std::max(max_right[i], i - 1, less);

    std::size_t max_dist = 0;
    for (std::size_t i = 0, j = 0; i < n; ++i)
        while (!less(max_right[j], i))
        {
            j = max_right[j];
            max_dist = std::max(max_dist, j - i);
            if (++j == n)
                return max_dist;
        }

    return max_dist;
}
0

Please review this solution and cases where it might fail:

def maxIndexDiff(arr, n):
    j = n-1
    for i in range(0,n):
        if j > i:
            if arr[j] >= arr[i]:
                return j-i
            elif arr[j-1] >= arr[i]:
                return (j-1) - i
            elif arr[j] >= arr[i+1]:
                return j - (i+1)
        j -= 1
    return -1
0

int maxIndexDiff(int arr[], int n) {

    // Your code here
    vector<int> rightMax(n);
    rightMax[n-1] = arr[n-1];
    for(int i =n-2;i>=0;i--){
        rightMax[i] = max(rightMax[i+1],arr[i]); 
    }
    int i = 0,j=0,maxDis = 0;
    while(i<n &&j<n){
        if(rightMax[j]>=arr[i]){
            maxDis = max(maxDis,j-i);
            j++;
        } else
            i++;
    }
    return maxDis;
}

There is concept of keeping leftMin and rightMax but leftMin is not really required and leftMin will do the work anyways. We are choosing rightMax and traversing from start till we get a smaller value than that!

0

Create Arraylist of pairs where is key is array element and value is the index. Sort this arraylist of pairs. Traverse this arraylist of pairs to get the maximum gap between(maxj-i). Also keep a track of maxj and update when new maxj is found. Please find my java solution which takes O(nlogn) time complexity and O(n) space complexity.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

class MaxDistanceSolution {
    private class Pair implements Comparable<Pair> {
        int key;
        int value;

        public int getKey() {
            return key;
        }

        public int getValue() {
            return value;
        }

        Pair(int key, int value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public int compareTo(Pair o) {
            return this.getKey() - o.getKey();
        }
    }

    public int maximumGap(final ArrayList<Integer> A) {
        int n = A.size();
        ArrayList<Pair> B = new ArrayList<>();
        for (int i = 0 ; i < n; i++)
            B.add(new Pair(A.get(i), i));
        Collections.sort(B);
        int maxJ = B.get(n-1).getValue();
        int gaps = 0;
        for (int i = n - 2; i >= 0; i--) {
            gaps = Math.max(gaps, maxJ - B.get(i).getValue());
            maxJ = Math.max(maxJ, B.get(i).getValue());
        }
        return gaps;
    }
}

public class MaxDistance {
    public static void main(String[] args) {
        MaxDistanceSolution sol = new MaxDistanceSolution();
        ArrayList<Integer> A = new ArrayList<>(Arrays.asList(3, 5, 4, 2));
        int gaps = sol.maximumGap(A);
        System.out.println(gaps);
    }
}
-1

I have solved this question here.

https://github.com/nagendra547/coding-practice/blob/master/src/arrays/FindMaxIndexDifference.java

Putting code here too. Thanks.

private static int findMaxIndexDifferenceOptimal(int[] a) {

        int n = a.length;
        // array containing minimums
        int A[] = new int[n];
        A[0] = a[0];
        for (int i = 1; i < n; i++) {
            A[i] = Math.min(a[i], A[i - 1]);
        }

        // array containing maximums
        int B[] = new int[n];
        B[n - 1] = a[n - 1];
        for (int j = n - 2; j >= 0; j--) {
            B[j] = Math.max(a[j], B[j + 1]);
        }

        int i = 0, maxDiff = -1;
        int j = 0;
        while (i < n && j < n) {
            if (B[j] > A[i]) {
                maxDiff = Math.max(j - i, maxDiff);
                j++;
            } else {
                i++;
            }

        }

        return maxDiff;
    }
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.