2874. Maximum Value of an Ordered Triplet II - Detailed Explanation

Problem Statement

You’re given a 0‑indexed integer array nums. You need to choose three indices (i, j, k) with 0 ≤ i < j < k < nums.length to maximize

(nums[i] – nums[j]) * nums[k]

Return that maximum value; if every triplet’s value is negative, return 0.

Examples

Input:  nums = [12,6,1,2,7]
Output: 77
Explanation: The best triplet is (0,2,4): (nums[0] – nums[2]) * nums[4] = (12–1)*7 = 77.

Input:  nums = [1,10,3,4,19]
Output: 133
Explanation: The best triplet is (1,2,4): (10–3)*19 = 7*19 = 133.

Input:  nums = [1,2,3]
Output: 0
Explanation: The only triplet (0,1,2) gives (1–2)*3 = –3, so we return 0.

Constraints

• 3 ≤ nums.length ≤ 10⁵
• 1 ≤ nums[i] ≤ 10⁶

Hints

• A brute‑force check of all O(n³) triplets will time out.
• Notice that for each k, you want the largest possible (nums[i] – nums[j]) with i<j<k.
• You can maintain two running values while scanning once from left to right:
  1. mx = maximum of nums[0..j]
  2. mxDiff = maximum of mx – nums[j]
     Then for each new element as nums[k], compute mxDiff * nums[k] and update your answer.

Brute Force Approach

1. Initialize ans = 0.
2. Triple‑loop over i from 0 to n-3, j from i+1 to n-2, k from j+1 to n-1.
3. Compute val = (nums[i] – nums[j]) * nums[k] and set ans = max(ans, val).
4. Return ans.

• Time: O(n³)
• Space: O(1)
• Too slow for n up to 10⁵.

Optimal One‑Pass Approach

Maintain three variables as you scan the array once:

• mx = the maximum value seen so far (candidate for nums[i]),
• mxDiff = the maximum mx – nums[j] seen so far (best (nums[i]–nums[j])),
• ans = best triplet value found.

Algorithm

mx = nums[0]
mxDiff = –∞
ans = 0

for idx in 1..n-1:
    x = nums[idx]
    // If we have seen at least one valid (i,j), try using x as k
    if mxDiff != –∞:
        ans = max(ans, mxDiff * x)
    // Now treat x as the new j, update best (i,j)
    mxDiff = max(mxDiff, mx – x)
    // Finally update mx to consider x as a future i
    mx = max(mx, x)

return ans

• Why it works

  • At each step idx, mx is the largest nums[i] with i < idx.
  • mxDiff is the largest (nums[i] – nums[j]) with i < j < idx.
  • Multiplying mxDiff by nums[idx] considers all triplets ending at k = idx.

• Time: O(n) — single pass

• Space: O(1)

Step‑by‑Step Walkthrough

For nums = [12,6,1,2,7]:

Initialization:
  mx = 12, mxDiff = –∞, ans = 0

idx = 1 (x = 6):
  mxDiff = max(–∞, 12–6 = 6) → 6
  mx = max(12,6) → 12

idx = 2 (x = 1):
  ans = max(0, 6*1 = 6) → 6
  mxDiff = max(6, 12–1 = 11) → 11
  mx = max(12,1) → 12

idx = 3 (x = 2):
  ans = max(6, 11*2 = 22) → 22
  mxDiff = max(11, 12–2 = 10) → 11
  mx = max(12,2) → 12

idx = 4 (x = 7):
  ans = max(22, 11*7 = 77) → 77
  mxDiff = max(11, 12–7 = 5) → 11
  mx = max(12,7) → 12

Return 77

Complexity Analysis

• Time: O(n) — one pass over nums.
• Space: O(1) — only a few variables.

Python Code