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

Question

nilkn · Accepted Answer

Iterate over the list, updating two variables each time: the minimum element seen so far and the maximum difference possible so far (calculated as the max of the current max difference and the difference of the current element and the current known minimum). This works in O(n) time with O(1) storage.

melonhead901 · Answer

Build an array max where at each index i max[i] is the highest value to the right of i in the original array. Then iterate over the original array and compute max[i]-orig[i] and return the highest of these values. Requires space and time linear in the length of the array.

zahide · Answer

Looks like an Divide & Conquer algorithm.

turcalu1 · Answer

Start with two pointers (min, max) pointing at first two elements of array and count the difference. Move the max pointer right, if it increases the difference. Then do the same with minimum pointer (w/ the restriction that you cannot jump over the max pointer). Now you have a maximum diff of the first subsequence. Move your pointers on the next two elements after max pointer and repeat the process. In the end you will have a maximum global difference.

Palantir Technologies

Palantir Technologies Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches