Introduction

This problem asks for the maximum value of arr[j] - arr[i] where index i is earlier than j. It is the same core pattern used in one-transaction stock-profit questions. A brute-force search works but scales poorly, so an O(n) scan is the practical solution.

Problem Restatement

Given an integer array, find the largest difference between two elements such that:

• The smaller value comes first in the array.
• The larger value comes later.

You can return only the numeric difference, or return both indices and values to explain the result.

Brute Force vs Linear Scan

Brute force checks every pair and computes all differences.

1def max_diff_bruteforce(arr):
2    best = None
3    for i in range(len(arr)):
4        for j in range(i + 1, len(arr)):
5            diff = arr[j] - arr[i]
6            if best is None or diff > best:
7                best = diff
8    return best

This is simple but time complexity is quadratic, which gets expensive quickly.

The optimal linear idea is:

• Keep the minimum value seen so far on the left.
• At each position, compute current value minus that minimum.
• Update global best difference when larger.

Optimal O(n) Algorithm

1from typing import List, Optional, Tuple
2
3
4def max_diff_with_indices(arr: List[int]) -> Optional[Tuple[int, int, int]]:
5    if len(arr) < 2:
6        return None
7
8    min_idx = 0
9    best_i = 0
10    best_j = 1
11    best_diff = arr[1] - arr[0]
12
13    for j in range(1, len(arr)):
14        current_diff = arr[j] - arr[min_idx]
15        if current_diff > best_diff:
16            best_diff = current_diff
17            best_i = min_idx
18            best_j = j
19
20        if arr[j] < arr[min_idx]:
21            min_idx = j
22
23    return best_i, best_j, best_diff
24
25
26data = [2, 3, 10, 6, 4, 8, 1]
27result = max_diff_with_indices(data)
28print(result)
29if result:
30    i, j, diff = result
31    print("values:", data[i], data[j], "difference:", diff)

Complexity:

• Time is linear.
• Extra space is constant.

This is optimal for a single pass over a static array.

Edge Cases and Result Semantics

Your API should define behavior for decreasing arrays. Example array [9, 7, 4, 1] has maximum difference -2 if you require distinct indices and allow negative results.

Alternative semantics used in finance-style tasks clamp to zero when no profitable pair exists.

1def max_non_negative_diff(arr):
2    result = max_diff_with_indices(arr)
3    if result is None:
4        return 0
5    return max(0, result[2])

Pick one semantic and document it. Ambiguous expectations cause subtle bugs in downstream logic.

Streaming and Large Data

If values arrive as a stream, you can run the same logic online without storing all values.

1class MaxDifferenceTracker:
2    def __init__(self):
3        self.seen = 0
4        self.min_val = None
5        self.best = None
6
7    def update(self, x: int):
8        if self.seen == 0:
9            self.min_val = x
10            self.seen += 1
11            return
12
13        diff = x - self.min_val
14        if self.best is None or diff > self.best:
15            self.best = diff
16
17        if x < self.min_val:
18            self.min_val = x
19
20        self.seen += 1
21
22
23tracker = MaxDifferenceTracker()
24for v in [5, 1, 7, 3, 9]:
25    tracker.update(v)
26print(tracker.best)

This keeps memory constant and is suitable for telemetry pipelines or large log processing jobs.

Testing Strategy

Include tests for:

• Strictly increasing arrays.
• Strictly decreasing arrays.
• Repeated values.
• Negative numbers.
• Short arrays with zero or one element.

1cases = [
2    ([1, 2, 3], 2),
3    ([3, 2, 1], -1),
4    ([7, 7, 7], 0),
5    ([-5, -2, -9, 0], 9),
6]
7
8for arr, expected in cases:
9    out = max_diff_with_indices(arr)
10    got = None if out is None else out[2]
11    print(arr, got, expected)

Common Pitfalls

• Checking all pairs in production code. Fix by tracking running minimum in one pass.
• Forgetting index order condition. Fix by only comparing current value against past minimum, never future values.
• Returning zero by default without defined semantics. Fix by documenting whether negative maximum is allowed.
• Mishandling short arrays. Fix by returning None or raising clear error for fewer than two elements.
• Tracking minimum value but not its index. Fix by keeping both value position and best pair indices.

Summary

• The optimal algorithm is a single left-to-right scan with a running minimum.
• Time complexity is linear and space complexity is constant.
• Decide early whether negative maximum differences are valid outputs.
• The same logic works for arrays and streaming inputs.
• Keep tests focused on boundary cases and semantic expectations.