Given an array V, we need to find two indices (i,j) such that V[j] > V[i] and (j - i) is maximum

Question

Given an array V, we need to find two indices (i,j) such that V[j] > V[i] and (j - i) is maximum.

The brute force approach is pretty straight forward wherein for each value at index i (ranging from 1 to n), we compare value at index j (ranging from i+1 to n). We keep track of maximum (j-i) so far to find the final answer.

This approach has the time complexity of O(n^2). Does anybody have any suggestions on improving the time complexity?

Answer 1

Java implementation runs in linear time.

public class MaxIndexDifference {

public static void main(String[] args) {
     System.out.println(betweenTwoElements(2, 3, 6, 10, 4));
}

private static int betweenTwoElements(int... nums) {
    int numberOfElements = nums.length;
    int maxDifference = -1, minIndex = 0, maxIndex = 0;

    int[] lMin = new int[numberOfElements];
    int[] rMax = new int[numberOfElements];

    /* Construct lMin such that stores the minimum value (to the left)  from (nums[0], nums[1], ... nums[i])*/

    lMin[0] = nums[0];
    for (int i = 1; i < numberOfElements; i++) {
        lMin[i] = Math.min(nums[i], lMin[i -1]);
    }
    /* Construct RMax[] such that RMax[j] stores the maximum value (to the right) from (arr[j], arr[j+1], ..arr[n-1]) */
    rMax[numberOfElements - 1] = nums[numberOfElements - 1];
    for (int i = numberOfElements-2; i >= 0; i--) {
        rMax[i] =  Math.max(nums[i], rMax[i + 1]);
    }
    /* Traverse both arrays from left to right to find optimum maxIndex - minIndex This process is similar to merge() of MergeSort */
    while (minIndex < numberOfElements && maxIndex < numberOfElements) {
        if (lMin[minIndex] < rMax[maxIndex]) {
            maxDifference = Math.max(maxDifference, maxIndex - minIndex);
            maxIndex = maxIndex +1;
        } else {
            minIndex = minIndex +1;
        }           
    }   
    return maxDifference;
}
}

Answer 2

Algorithm with O(N) complexity:

#!/usr/bin/perl

use strict;
use warnings;

sub dump_list { print join(", ", map sprintf("%2d", $_), @_), "\n" }

for (0..20) {
    # generate a random list of integers with some convenient bias:
    my @l = (map int(rand(20) + 20 - $_), 0..19);

    my $max = $l[-1];
    my $min = $l[0];

    my @max;
    for my $l (reverse @l) {
        $max = $l if $l > $max;
        push @max, $max;
    }
    @max = reverse @max;

    my @min;
    for my $l (@l) {
        $min = $l if $l < $min;
        push @min, $min;
    }

    my $best_i = 0;
    my $best_j = -1;
    my $best   = -1;

    my $j = 0;
    for my $i (0..$#l) {
        while ($j < @l) {
            last unless $max[$j] > $min[$i];
            $j++;
            if ($j - $i > $best) {
                $best = $j - 1 - $i;
                $best_i = $i;
                $best_j = $j - 1;
            }
        }
    }

    print "list: "; dump_list @l;
    print "idxs: "; dump_list 0..$#l;
    print "best: $best, i: $best_i, j: $best_j\n\n";
}

update: in response to Nohsib request:

Say you have a random list of numbers (a[0], a[1], a[2], a[3]..., a[N-1])

First step is to find for every number the maximum to the left as mas max[i] = maximum(a[0], a[1], ..., a[i]) and the minimum to the right min[i] = minimum(a[i], a[i+1], ..., a[N-1]).

Once you have those arrays finding the interval where a[j] < a[k] that maximizes k-j is almost trivial.

Try doing it in paper with some random lists and you will easily find out the logic behind.

Answer 3

Here's an approach that will solve the problem in linear time.

1. Compute the stack S of increasing positions i such that min A[1..i-1] > i with a simple forwards scan over the array.
2. Iterate over the list backwards.
3. While the current element is greater than the value given by the top of the stack S: check if we have a new record and pop the top of the stack.

A quick implementation in python:

def notsurewhattonamethis(A):
    assert(A)
    S = [0]
    for i,v in enumerate(A):
        if v<A[S[-1]]:
            S.append(i)
    best = (-1,-1)
    for i,v in reversed(list(enumerate(A))):
        while v>A[S[-1]]:
            j = S.pop()
            d = i - j
            if d > best[1]-best[0]:
                best = (j,i)
            if not S: return best
    return best

Answer 4

If you have known limitation of array elements (else see update below) I can suggest you algorithm with time complexity O(n*log(MaxN)) and space complexity O(MaxN) where MaxN = Max(V[i]). For this algorithm we need structure that can get minimum in array between 1 and N with time complexity O(log(N)) and update array element with time complexity O(log(N)). Fenwick tree can do those tricks. Let's call this structure minimizator. Then we need to:

1. Iterate all elements in given order v[i] and put at v[i] position at minimizator value i.
2. For each element v[i] find minimum using minimizator between 1 and v[i-1] (this is minimum index of element that less than v[i])
3. Remember maximum difference between i and found minimum index of element that less than v[i].

Ok. I've tried to write some pseudocode:

prepare array (map values)
init minimizator

ansI = -1
ansJ = -1

for i from 0 to v.length-1
  minIndexOfElementLessThanCurrent = get min value from 1 to v[i]-1 (inclusive) using minimizator
  set to minimizator v[i] position value i

  if minIndexOfElementLessThanCurrent is exists
    if ansJ - ansI < i - minIndexOfElementLessThanCurrent 
      ansJ = i
      ansI = minIndexOfElementLessThanCurrent

C++ implementation:

class FenwickTree
{
    vector<int> t;
    int n;

public:

    static const int INF = 1000*1000*1000;

    void Init (int n)
    {
        this->n = n;
        t.assign (n, INF);
    }

    int GetMin (int i)
    {
        int res = INF;
        for (; i >= 0; i = (i & (i+1)) - 1)
            res = min (res, t[i]);
        return res;
    }

    void Update (int i, int value)
    {
        for (; i < n; i = (i | (i+1)))
            t[i] = min (t[i], value);
    }
};

pair<int, int> Solve(const vector<int>& v)
{
    int maxElement = 0;
    for(int i = 0; i < v.size(); i++)
        maxElement = max(maxElement, v[i]);

    FenwickTree minimizator;
    minimizator.Init(maxElement+1);

    int ansI = -1, ansJ = -1;
    for(int i = 0; i < v.size(); i++)
    {
        int minLeftIndex = minimizator.GetMin(v[i]-1);      
        minimizator.Update(v[i], i);

        if(minLeftIndex == FenwickTree::INF) continue; // no left elements less than v[i]

        if(ansJ - ansI < i - minLeftIndex)
        {           
            ansJ = i;
            ansI = minLeftIndex;
        }
    }
    return make_pair(ansI, ansJ);
}

UPDATE: If kind of elements is not int(f.e. double) or if max value of array elements is too big (f.e. 10^9) we can map array values (it will not affect the result) to integer set 1..N and then time complexity should be O(n * log(n))

UPDATE:

If elements is integer - there is O(max(maxN, n)) solution. So if maxN <= n complexity is O(N). We just need to answer for the query 'get minimum from 1 to N' in const time O(1):

1. Create array of size maxN
2. Element m[i] of array is minimum index of i value in source array V.
3. Using dynamic programming create array the same size that element r[i] of array is minimum of m[j], 1 <= j <= i. Recurrence relation is r[i] = min(r[i-1], m[i])

Main idea of this algorithm is the same as above, only use array r to find min from 1 to v[i].

C++ implementation:

pair<int, int> Solve(const vector<int>& v)
{
    int maxElement = 0;
    for(int i = 0; i < v.size(); i++)
        maxElement = max(maxElement, v[i]);

    vector<int> minimum(maxElement + 1, v.size() + 1);
    for(int i = 0; i < v.size(); i++)
        minimum[v[i]] = min(minimum[v[i]], i); // minimum[i] contains minimum index of element i

    for(int i = 1; i < minimum.size(); i++)
        minimum[i] = min(minimum[i-1], minimum[i]); // now minimum[i] contains minimum index between elements 1 and i

    int ansI = -1, ansJ = -1;
    for(int i = 0; i < v.size(); i++)
    {
        int minLeftIndex = minimum[v[i]-1];      

        if(minLeftIndex >= i) continue; // no left elements less than v[i]

        if(ansJ - ansI < i - minLeftIndex)
        {           
            ansJ = i;
            ansI = minLeftIndex;
        }
    }
    return make_pair(ansI, ansJ);
}

If elements are double, or something else (very big integers) we cannot map elements to set 1..N in linear time (or can?). I know only O(n*log(n)) solution (sorting elements, etc)

Answer 5

I'm not sure what you actually want here, the first paragraph of your question conflicts with the second. So I'll give two answers, one for each interpretation that I can think of, although both may not be what you meant.

The first interpretation: searching for a maximal V[j]-V[i], under the constraint that j > i.
This is that it's almost finding the min and max. But in addition, there's also a constraint on the indexes. That in itself doesn't mean that the idea can't be used; for any chosen V[i], you just need the max over V[i+1 .. n], and you don't need to recompute those maxes every time, leading to this algorithm:

• Compute the suffix-max array in O(n)
• Find the pair (V[i],suffixmax[i+1]) with maximal difference in O(n)

The second interpretation: searching for a maximal j-i, under the constraint that V[j] > V[i].
I can't come up with anything good.