LeetCode 3073 - Maximum Increasing Triplet Value

We are given an integer array nums, and we must find three indices (i, j, k) such that: - i < j < k - nums[i] < nums[j] < nums[k] Among all valid increasing triplets, we want to maximize the expression: The task is not to maximize the sum of the triplet.

leetcodemediumarrayordered-set

LeetCode Problem 3073

Difficulty: 🟡 Medium
Topics: Array, Ordered Set

Solution

Problem Understanding

We are given an integer array nums, and we must find three indices (i, j, k) such that:

  • i < j < k
  • nums[i] < nums[j] < nums[k]

Among all valid increasing triplets, we want to maximize the expression:

$$nums[i] - nums[j] + nums[k]$$

The task is not to maximize the sum of the triplet. Instead, the middle element is subtracted, which changes the optimization strategy significantly.

The input array can contain up to 10^5 elements, and each value can be as large as 10^9. These constraints immediately rule out any cubic time solution because checking every possible triplet would take far too long.

The problem guarantees that at least one valid increasing triplet exists, so we never need to handle the case where no answer is possible.

The important challenge is balancing the three values correctly:

  • We want nums[k] to be as large as possible because it is added.
  • We want nums[j] to be as small as possible because it is subtracted.
  • We still need nums[i] < nums[j] < nums[k].

A naive implementation may incorrectly focus only on the largest increasing triplet values without accounting for the subtraction of the middle element.

Another subtle issue is that the smallest valid nums[i] is usually best because it contributes positively while also making it easier to satisfy the increasing condition.

Approaches

Brute Force

The most direct solution is to try every possible triplet (i, j, k).

We use three nested loops:

  • The first loop chooses i
  • The second loop chooses j
  • The third loop chooses k

For every triplet, we check whether:

$$nums[i] < nums[j] < nums[k]$$

If the condition is valid, we compute:

$$nums[i] - nums[j] + nums[k]$$

and update the maximum answer.

This approach is correct because it exhaustively evaluates every valid triplet. However, its time complexity is far too large.

With n = 10^5, an O(n^3) algorithm would require roughly:

$$(10^5)^3 = 10^{15}$$

operations, which is completely infeasible.

Key Insight for the Optimal Solution

We can rewrite the target expression as:

$$(nums[i] - nums[j]) + nums[k]$$

For every position j, we need:

  • The smallest valid value before j that is less than nums[j]
  • The largest valid value after j that is greater than nums[j]

If we know these efficiently, then every index j can act as the middle element of the triplet.

The critical observation is:

  • Since nums[i] is added positively, the best i is actually the smallest valid value before j
  • Since nums[k] is added positively, the best k is the largest valid value after j

Thus, for each j, we need:

$$\min(nums[i]) \text{ where } i < j \text{ and } nums[i] < nums[j]$$

and

$$\max(nums[k]) \text{ where } k > j \text{ and } nums[k] > nums[j]$$

We can preprocess suffix maximums to efficiently obtain the best k.

For the left side, we only need the minimum value seen so far because if the minimum value is smaller than nums[j], it is always the best choice.

This leads to a linear time solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Checks every possible triplet
Optimal O(n) O(n) Uses prefix minimum and suffix maximum

Algorithm Walkthrough

  1. Create a suffix maximum array.

For every index i, store the maximum value from i to the end of the array.

This allows us to quickly determine the largest possible nums[k] for any middle index j. 2. Initialize a running minimum value.

As we scan from left to right, maintain the smallest number encountered so far.

This represents the best possible nums[i]. 3. Iterate through the array using each position as the middle element j.

For every index j:

  • Check whether the current minimum value is smaller than nums[j]
  • Check whether the suffix maximum after j is larger than nums[j]

If both conditions hold, then a valid increasing triplet exists. 4. Compute the triplet value.

Using:

$$minLeft - nums[j] + maxRight$$

where:

  • minLeft is the smallest valid left value
  • maxRight is the largest valid right value
  1. Update the global maximum answer.
  2. Update the running minimum.

After processing index j, update the prefix minimum using the current element.

Why it works

For a fixed middle element nums[j], the expression is:

$$nums[i] - nums[j] + nums[k]$$

The only constraints are:

$$nums[i] < nums[j] < nums[k]$$

To maximize the expression:

  • We should maximize nums[k]
  • We should minimize nums[j]
  • We should choose the smallest valid nums[i]

The suffix maximum array guarantees we always choose the best possible k, and the running prefix minimum guarantees we always choose the best possible i.

Since every index is considered exactly once as the middle element, the algorithm evaluates all optimal candidates.

Python Solution

from typing import List

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)

        # suffix_max[i] = maximum value from i to n-1
        suffix_max = [0] * n
        suffix_max[-1] = nums[-1]

        for i in range(n - 2, -1, -1):
            suffix_max[i] = max(nums[i], suffix_max[i + 1])

        min_left = nums[0]
        answer = 0

        for j in range(1, n - 1):
            max_right = suffix_max[j + 1]

            if min_left < nums[j] < max_right:
                value = min_left - nums[j] + max_right
                answer = max(answer, value)

            min_left = min(min_left, nums[j])

        return answer

The implementation begins by constructing the suffix_max array. Each position stores the largest value that appears at or after that index. This allows constant time lookup of the best possible right element for every middle index.

Next, the algorithm scans the array from left to right while maintaining min_left, the smallest value seen so far.

For every middle position j, the algorithm retrieves:

  • min_left
  • max_right

It then verifies that:

min_left < nums[j] < max_right

This ensures a valid increasing triplet exists.

If valid, the triplet value is computed and compared against the current maximum.

Finally, min_left is updated so future iterations have access to the smallest prefix value.

Go Solution

func maximumTripletValue(nums []int) int {
	n := len(nums)

	// suffixMax[i] = maximum value from i to n-1
	suffixMax := make([]int, n)
	suffixMax[n-1] = nums[n-1]

	for i := n - 2; i >= 0; i-- {
		if nums[i] > suffixMax[i+1] {
			suffixMax[i] = nums[i]
		} else {
			suffixMax[i] = suffixMax[i+1]
		}
	}

	minLeft := nums[0]
	answer := 0

	for j := 1; j < n-1; j++ {
		maxRight := suffixMax[j+1]

		if minLeft < nums[j] && nums[j] < maxRight {
			value := minLeft - nums[j] + maxRight

			if value > answer {
				answer = value
			}
		}

		if nums[j] < minLeft {
			minLeft = nums[j]
		}
	}

	return answer
}

The Go implementation follows the same algorithmic structure as the Python version.

Slices are used for the suffix maximum array. Since the constraints fit comfortably within Go's standard integer range on modern platforms, no special overflow handling is required.

Go does not provide built in min or max functions for integers, so explicit comparisons are used instead.

Worked Examples

Example 1

Input:

nums = [5, 6, 9]

Step 1: Build suffix maximum array

Index Value suffix_max
2 9 9
1 6 9
0 5 9

Result:

suffix_max = [9, 9, 9]

Step 2: Iterate

Initial state:

min_left = 5
answer = 0
j nums[j] min_left max_right Valid? Value answer
1 6 5 9 Yes 5 - 6 + 9 = 8 8

Final answer:

8

Example 2

Input:

nums = [1, 5, 3, 6]

Step 1: Build suffix maximum array

Index Value suffix_max
3 6 6
2 3 6
1 5 6
0 1 6

Result:

suffix_max = [6, 6, 6, 6]

Step 2: Iterate

Initial state:

min_left = 1
answer = 0
j nums[j] min_left max_right Valid? Value answer
1 5 1 6 Yes 1 - 5 + 6 = 2 2
2 3 1 6 Yes 1 - 3 + 6 = 4 4

Final answer:

4

Complexity Analysis

Measure Complexity Explanation
Time O(n) One pass to build suffix maximums and one pass to evaluate triplets
Space O(n) The suffix maximum array stores one value per index

The algorithm performs only two linear scans of the array. Every operation inside the loops is constant time, so the overall runtime is linear.

The only extra memory used is the suffix maximum array.

Test Cases

from typing import List

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)

        suffix_max = [0] * n
        suffix_max[-1] = nums[-1]

        for i in range(n - 2, -1, -1):
            suffix_max[i] = max(nums[i], suffix_max[i + 1])

        min_left = nums[0]
        answer = 0

        for j in range(1, n - 1):
            max_right = suffix_max[j + 1]

            if min_left < nums[j] < max_right:
                answer = max(answer, min_left - nums[j] + max_right)

            min_left = min(min_left, nums[j])

        return answer

sol = Solution()

assert sol.maximumTripletValue([5, 6, 9]) == 8  # smallest valid input
assert sol.maximumTripletValue([1, 5, 3, 6]) == 4  # multiple valid triplets
assert sol.maximumTripletValue([1, 2, 3, 4]) == 3  # strictly increasing array
assert sol.maximumTripletValue([2, 1, 5, 0, 4, 6]) == 7  # classic mixed ordering
assert sol.maximumTripletValue([1, 10, 2, 20]) == 19  # best middle element is not largest
assert sol.maximumTripletValue([3, 4, 5]) == 4  # exactly one triplet
assert sol.maximumTripletValue([1, 2, 1000000000]) == 999999999  # large values
assert sol.maximumTripletValue([1, 3, 2, 4, 5]) == 4  # multiple candidate middles
assert sol.maximumTripletValue([1, 100, 2, 3, 200]) == 199  # late large suffix value

Test Summary

Test Why
[5, 6, 9] Smallest possible valid array
[1, 5, 3, 6] Multiple valid triplets
[1, 2, 3, 4] Strictly increasing sequence
[2, 1, 5, 0, 4, 6] Mixed ordering and updates to prefix minimum
[1, 10, 2, 20] Best middle value is not the largest
[3, 4, 5] Exactly one valid triplet
[1, 2, 1000000000] Very large numbers
[1, 3, 2, 4, 5] Multiple competing middle indices
[1, 100, 2, 3, 200] Large suffix value appears late

Edge Cases

One important edge case is the minimum valid array length of three elements. In this situation, there is exactly one possible triplet. The implementation handles this naturally because the loop runs exactly once for the middle index.

Another important case is when the array is strictly increasing. Here, every position can potentially serve as the middle element. The algorithm correctly evaluates each one and selects the maximum expression value.

Arrays with fluctuating values can also be tricky. For example:

[2, 1, 5, 0, 4, 6]

The smallest prefix value changes during iteration, and the best triplet may involve elements that are far apart. The running min_left variable ensures the algorithm always uses the optimal left candidate.

Large integer values are another concern. Since nums[i] can reach 10^9, the computed expression may also become large. Both Python and Go safely handle these values under the problem constraints.

Finally, repeated local peaks can mislead naive greedy strategies. A larger middle value is actually harmful because it is subtracted. The algorithm avoids this mistake by evaluating the actual expression value for every valid middle position instead of greedily selecting large numbers.