Katkat
Back

Compute maximum later-earlier difference

CitadelSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to optimize an O(n^2) brute-force search into an O(n) linear-time solution using a single-pass scan while maintaining state variables.

Maximum Later-Earlier Difference

You are given an array of integers prices representing the historical daily values of a stock over a period of time. Your task is to find the maximum possible difference between two values such that the larger value occurs at a later index than the smaller value.

Formally, find the maximum value of prices[j] - prices[i] such that j > i. If no such positive difference exists (i.e., the array is sorted in non-increasing order), return 0.

Function Signature

def max_difference(prices: list[int]) -> int:

Constraints

  • 2 <= len(prices) <= 10^5
  • -10^6 <= prices[i] <= 10^6

Examples

Example 1: Input: prices = [7, 1, 5, 3, 6, 4] Output: 5 Explanation: The maximum difference is 5, obtained by choosing 1 at index 1 and 6 at index 4 (6 - 1 = 5).

Example 2: Input: prices = [9, 7, 4, 1] Output: 0 Explanation: No pair exists where the later element is larger than the earlier one.

Edge Cases

  • Arrays with two elements where the second is smaller.
  • Arrays with identical values.
  • Large negative numbers.

Hints

Hint 1

Instead of using two nested loops to compare every pair, consider keeping track of the minimum element seen so far as you iterate through the array.

Hint 2

At each index `j`, the maximum profit you could make if you sold at `prices[j]` is simply `prices[j]` minus the minimum value seen in the range `[0, j-1]`.

Hint 3

Update the overall maximum difference while updating the minimum value encountered as you traverse the array once.

Follow-up questions

  • How would you modify your algorithm if you were allowed to perform multiple transactions (i.e., buy and sell multiple times) to maximize total profit?
  • What if the requirement changed to find the maximum difference where the later element is smaller than the earlier element (i.e., a 'loss' scenario)?
  • How would you handle the data if the input array was too large to fit in memory and was instead provided as a stream of integers?