CODEWITHSUNDEEP
javamaxtime-complexity
Stephany
Stephany

Reputation: 29

Maximum increasing difference

I need to find the maximum increasing distance or difference between numbers in a vector. For example, in the vector [10, 5, 20, 45, 5, 5, 7] on first pass it looks that the difference between 10 and 45 is maximum. But on the second iteration the difference between 5 and 45 is larger, so it should be chosen by the algorithm.

I have a solution but it is O(n^2) and for the life of me I can't figure out if there is a solution with lower computational complexity.

public void maxDistance(int inputArray[]) {
    int trueMaxValue = 0,   trueMinIndex = 0,   trueMaxIndex = 0,  tempMaxValue;

    for (int i = 0; i < inputArray.length - 1; ++i) {
        for (int j = i + 1; j < inputArray.length; ++j) {
            tempMaxValue = inputArray[j] - inputArray[i];
            if (tempMaxValue > trueMaxValue) {
                trueMaxValue = tempMaxValue;
                trueMinIndex = i;
                trueMaxIndex = j;
            }
        }
    }
}

I also need to know which two numbers in the array were used in the max. Can you please help? I just don't know if I should continue to think about it or O(n^2) is the best that you can do?

Upvotes: 0

Views: 144

Answers (4)

anomeric
anomeric

Reputation: 698

You've definitely got better options. I'm not sure why a nested loop was even necessary here. I'll edit to include the indices, but I'm not sure why that's helpful in the case scenario considering your array can have duplicate numbers.

int[] inputArray = new int[] {10,5,20,5,5,46,7};
int max = 0;
int min = Integer.MAX_VALUE;
for (int i = 0; i < inputArray.length; i++) {
    max = inputArray[i] > max ? inputArray[i] : max;
    min = inputArray[i] < min ? inputArray[i] : min;
}
int delta = max - min;

I'll edit to include the indices, but I'm not sure why that's helpful in the case scenario considering your array can have duplicate numbers.

int[] inputArray = new int[] {10,5,20,5,5,46,7};
int max = 0;
int min = Integer.MAX_VALUE;
int maxIndex = -1;
int minIndex = -1;
for (int i = 0; i < inputArray.length; i++) {
    if (inputArray[i] > max) {
        max = inputArray[i];
        maxIndex = i;
    } 
    if (inputArray[i] < min) {
        min = inputArray[i];
        minIndex = i;
    }
}
int delta = max - min;

Upvotes: 1

Rahav
Rahav

Reputation: 1875

You can do it in O(n) Stephany. You need to add a few variables to remember what is the current best solution. Using your current naming convention you can do the following:

    public void maxDistance(int inputArray[]) {
        int currentMin = inputArray[0],     currentMinIndex = 0;
        int trueMaxValue = 0,   trueMinIndex = 0,   trueMaxIndex = 0;
        int tempMaxValue;

        int i = 1;
        while (i < inputArray.length) {
            tempMaxValue = inputArray[i] - inputArray[currentMinIndex];
            if (tempMaxValue > trueMaxValue) {
                trueMaxValue = tempMaxValue;
                trueMinIndex = currentMinIndex;
                trueMaxIndex = i;
            }

            if (inputArray[i] < currentMin) {
                currentMinIndex = i;
                currentMin = inputArray[i];
            }

            ++i;
        }

Upvotes: 4

NPE
NPE

Reputation: 500693

This can be done in linear time.

Here is an outline:

  1. Iterate over the array, keeping track of the smallest number seen thus far.

  2. Compute the difference between the smallest number seen thus far and the current number, and keep track of the largest such difference.

Voilà.

Upvotes: 3

GhostCat
GhostCat

Reputation: 140523

Maybe I am missing something but:

  • iterate the array
  • determine the smallest entry
  • determine the biggest entry
  • compute the delta (max - min)

All of that can be done in one iteration. This would find 5 and 45 and give a difference of 40. And as said - one pass only.

Upvotes: 3

Related Questions