CODEWITHSUNDEEP
javaalgorithm
Vivek
Vivek

Reputation: 1326

Find the largest possible difference in an array with the smaller integer occurring earlier

This is an interview question:

Find the largest possible difference in an array of integers, such that the smaller integer occurs earlier in the array.

Constraint: Numbers are not unique. The range is Integer range of java. (or any other language)

Example:

input 1: {1, 100, 2, 105, -10, 30, 100}

The largest difference is between -10 and 100 -> 110 (here -10 is at the 5th index and 100 is at 7th index)

input 2: {1, 100, 2, 105, -10, 30, 80}

The largest difference is between 1 and 105 -> 104 (here 1 is at the 1st index and 105 is at 4th index)

Possible Solution:

One approach is check for all possible differences and keep a track of the biggest difference found till now O(n^2) complexity.

can this be done in better than O(n^2) time?

Upvotes: 11

Views: 17110

Answers (11)

apachauri
apachauri

Reputation: 1

public static void findlargestDifference(int arr[]){

    int max_diff=0;     
    int min_value=Integer.MIN_VALUE;        
    for(int i=0;i<arr.length;i++){

        if(min_value<arr[i]){               
            min_value=arr[i];               
        }           
        int diff=min_value-arr[i];

        if(max_diff<diff){
            max_diff=diff;
        }                   
    }       
    System.out.println("Max Difference is  "+ max_diff);    
}

Upvotes: -1

Dhandeep Jain
Dhandeep Jain

Reputation: 166

Start from the last element and move backwards. keep in memory the largest element occurred till now. for each element subtract from the max and store at the respective position.

Also, you can keep an element to store the max difference and give the output straight away. O(n) time, O(1) space.

int max = INT_MIN;
int maxdiff = 0;

for (i = sizeof(arr) / sizeof(int) - 1; i >= 0; i--) {
  if (max < arr[i]) {
    max = arr[i];
  }
  int diff = max - arr[i];
  if (maxdiff < diff) {
    maxdiff = diff;
  }
}

print maxdiff;

Upvotes: 10

Soheil
Soheil

Reputation: 795

Ruby solution:

a = [3, 6, 8, 1, 5]
min = 10**6
max_diff = -10**6
a.each do |x|
  min = x if x < min
  diff = x - min
  max_diff = diff if diff > max_diff
end
puts max_diff

Upvotes: 0

Rajesh Kumar
Rajesh Kumar

Reputation: 1

public static void findDifference(Integer arr[]) {
    int indexStart = 0;
    int indexMin = 0;
    int indexEnd = 1;
    int min = arr[0];
    int diff = arr[1] - arr[0];
    for (int counter = 1; counter < arr.length; counter++) {
        if (arr[counter] - min > diff) {
            diff = arr[counter] - min;
            indexEnd = counter;
            indexStart = indexMin;
        }
        if (arr[counter] < min) {
            min = arr[counter];
            indexMin = counter;
        }
    }
    System.out.println("indexStart = " + indexStart);
    System.out.println("indexEnd = " + indexEnd);
    System.out.println("diff = " + diff);
}

Upvotes: -1

SMohan
SMohan

Reputation: 1

First find the difference between the adjacent elements of the array and store all differences in an auxiliary array diff[] of size n-1. Now this problems turns into finding the maximum sum subarray of this difference array.

Upvotes: 0

Rezwan4029
Rezwan4029

Reputation: 109

    // Solution Complexity : O(n)   
    int maxDiff(int a[], int n){
        //  Find difference of adjacent elements
        int diff[n+1];
        for (int i=0; i < n-1; i++)
            diff[i] = a[i+1] - a[i];

        // Now find the maximum sum sub array in diff array
        int max_diff = diff[0];
        for (int i = 1 ; i < n-1 ; i++ ) {
            if( diff[i-1] > 0 ) diff[i] += diff[i-1];
            if( max_diff < diff[i] ) max_diff = diff[i];
        }
        return max_diff;
    }

Upvotes: 0

Nir Alfasi
Nir Alfasi

Reputation: 53525

Dhandeep's algoritm is good and Vivek's translation of the code to Java works! Also, we can also scan the array normally and not in reverse:

int seed[] = {1, 100, 2, 105, -10, 30, 100};
int maxDiff=Integer.MIN_VALUE, minNumber = Integer.MAX_VALUE;

for (int i = 0; i < seed.length ; i++){
    if(minNumber > seed[i]) 
       minNumber = seed[i];

    maxDiff = Math.max(maxDiff, (seed[i]-minNumber));
}
System.out.println(maxDiff);

Upvotes: 11

Ankit Jain
Ankit Jain

Reputation: 2270

public class Test{

    public static void main(String[] args){

        int arr1[] = {1,2,5,7,9};
        int arr2[] = {20,25,26,35};
        int diff = 0;
        int max = 0;

        for(int i=0;i<arr1.length;i++){
            for(int j=0;j<arr2.length;j++){

                diff =  Math.abs(arr1[i]-arr2[j]);
                if(diff > max){
                    max = diff;
                }
            }
        }
    System.out.println(max);
    }   
}

Upvotes: 0

Vivek
Vivek

Reputation: 1326

Thanks @Dhandeep Jain for the answer. There is the java version:

//int seed[] = {1, 100, 2, 105, -10, 30, 100};
        int seed[] = {1, 100, 2, 105, -10, 30, 80};
        int maxDiff=Integer.MIN_VALUE, maxNumber = Integer.MIN_VALUE;

        for (int i = (seed.length-1); i >=0 ; i--){
            if(maxNumber < seed[i]) 
                maxNumber = seed[i];

            maxDiff = Math.max(maxDiff, (maxNumber - seed[i]));
        }
        System.out.println(maxDiff);

Upvotes: 4

themel
themel

Reputation: 8895

I propose that the largest difference is always between the largest number and the smallest number before that or between the smallest number and the largest number after that. These can be determined in linear time.

Upvotes: 0

user1582511
user1582511

Reputation: 1

I'm pretty sure this should solve your problem:

    int largestNumber = Integer.MIN_VALUE;
    int smallestNumber = Integer.MAX_VALUE; 

    for(int i = 0; i < yourArray.Length; i++)
    {
        if(yourArray[i] > largestNumber)
            largestNumber = yourArray[i];

        if(yourArray[i] < smallestNumber)
            smallestNumber = yourArray[i];

    }

    int biggestDifference = largestNumber - smallestNumber ;

Upvotes: -2

Related Questions