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?