CODEWITHSUNDEEP
javacarraysalgorithm
Algorithmist
Algorithmist

Reputation: 6695

Given an unsorted Array find maximum value of A[j] - A[i] where j>i..in O(n) time

This is an Amazon interview Question.I have solved this problem in O(n) using dynamic programming.But I want to know can there be more optimization than O(n)

for e.g. suppose below is the array 

3 7 1 4 2 4 returns 4

5 4 3 2 1 returns Nothing

4 3 2 2 3 returns 1

This is the code i have written Code

Upvotes: 10

Views: 4715

Answers (4)

kasavbere
kasavbere

Reputation: 6003

public static int maxOrderedDiff(int[] A){
    //A[x]-A[y] | x>y
    int min = 0, max = 0;
    int less = 0;
    for(int i=1; i<A.length; i++){
        if(A[less]>A[i]){
            less = i;
        }
        if(A[i]-A[min]>A[max]-A[min] || A[i]-A[less] >A[max]-A[min]){
            max=i;
            if(A[less]<A[min])
                min = less;
        }
    }

    return max>min? A[max]-A[min]: -1;
}//maxOrderedDiff

TEST WITH:

public static void main(String[] args){
    int[][] A = {{3, 7, 1, 4, 2, 4},{5, 4, 3, 2,1},{4, 3, 2, 2, 3}};

    for(int[] B: A)
        System.out.format("%s :: %d%n", Arrays.toString(B), maxOrderedDiff(B));
}

Upvotes: 0

Jarosław Gomułka
Jarosław Gomułka

Reputation: 4995

Lets say you've got int A[N].

int res = -1;
int min_value = A[0];
for(int i=1; i<N; i++) {
    // A[i] - A[j] is maximal, when A[j] is minimal value from {A[0], A[1],.., A[i-1]}
    res = max(res, A[i] - min_value);
    min_value = min(min_value, A[i]);
}
return res;

Complexity O(N).

You need to examine N elements so O(N) is best what you can get.

Upvotes: 16

MoveFast
MoveFast

Reputation: 3015

It can't be done better than O(n) because whatever approach you use, you will have to iterate over the array atleast once and that step in itself is O(n). Rest the fight remains only to minimize the constants.

Upvotes: 4

NPE
NPE

Reputation: 500317

But I want to know can there be more optimization then O(n)

Any of the n elements can be part of the solution, and therefore each needs to be examined. Thus, O(n) cannot be improved upon.

For completeness, here is a solution that takes O(n) time and requires O(1) memory:

A = [1, 10, 20, -10, 3, 4, 18, 42, 15]

smallest = A[0]
maxdiff = float('-inf')
for x in A[1:]:
  maxdiff = max(maxdiff, x - smallest)
  smallest = min(smallest, x)
print maxdiff

Upvotes: 7

Related Questions