Skip to main content
Talentd

Maximum Value of an Ordered Triplet I - Solution & Explanation

EasyArray11 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

You are given a 0-indexed integer array nums.

Return the maximum value over all triplets of indices (i, j, k) such that i < j < k. If all such triplets have a negative value, return 0.

The value of a triplet of indices (i, j, k) is equal to (nums[i] - nums[j]) * nums[k].

 

Example 1:

Input: nums = [12,6,1,2,7]
Output: 77
Explanation: The value of the triplet (0, 2, 4) is (nums[0] - nums[2]) * nums[4] = 77.
It can be shown that there are no ordered triplets of indices with a value greater than 77.

Example 2:

Input: nums = [1,10,3,4,19]
Output: 133
Explanation: The value of the triplet (1, 2, 4) is (nums[1] - nums[2]) * nums[4] = 133.
It can be shown that there are no ordered triplets of indices with a value greater than 133.

Example 3:

Input: nums = [1,2,3]
Output: 0
Explanation: The only ordered triplet of indices (0, 1, 2) has a negative value of (nums[0] - nums[1]) * nums[2] = -3. Hence, the answer would be 0.

 

Constraints:

  • 3 <= nums.length <= 100
  • 1 <= nums[i] <= 106

Approach Overview

Problem Overview: You are given an integer array nums. The goal is to compute the maximum value of the expression (nums[i] - nums[j]) * nums[k] such that i < j < k. If every possible value is negative, return 0. The challenge is efficiently evaluating valid triplets while respecting the index ordering constraint.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

The most direct method checks every ordered triplet (i, j, k) where i < j < k. Use three nested loops: the outer loop selects i, the second selects j, and the third selects k. For each combination, compute (nums[i] - nums[j]) * nums[k] and track the maximum value seen. This approach is useful for verifying correctness and understanding the problem constraints, but it quickly becomes impractical because the number of triplets grows cubically. With arrays of size n, the runtime is O(n^3) and the algorithm uses constant extra memory O(1). This method works only for very small inputs.

Approach 2: Prefix and Suffix Maximums (O(n) time, O(n) space)

The expression (nums[i] - nums[j]) * nums[k] can be maximized by selecting the largest possible nums[i] before j and the largest possible nums[k] after j. Instead of enumerating every triplet, precompute helpful values. First build a prefix array where prefixMax[j] stores the maximum element from index 0 to j. Then build a suffix array where suffixMax[j] stores the maximum element from index j to the end of the array.

Now treat each index j as the middle element of the triplet. The best candidate on the left is prefixMax[j-1], and the best candidate on the right is suffixMax[j+1]. Compute the value (prefixMax[j-1] - nums[j]) * suffixMax[j+1] and update the global maximum. This reduces the search from three nested loops to a single pass over the array after preprocessing. The overall complexity becomes O(n) time with O(n) extra memory.

This technique works because the best triplet for a fixed j must use the maximum available value on both sides to maximize the difference and the multiplier. Precomputing those values avoids repeated scanning of the array.

The solution relies on simple preprocessing over an array and a classic prefix/suffix preprocessing pattern often used in problems involving range maximum queries. Variants of this idea appear frequently in optimization problems where each index acts as a pivot.

Recommended for interviews: The prefix and suffix maximum approach. Interviewers expect candidates to move beyond brute force and recognize that the optimal i and k for each j are simply the maximum values on each side. Implementing this in O(n) time shows strong problem‑decomposition skills while keeping the code straightforward.

Approach 1: Brute Force Approach

This approach involves iterating through all possible triplet indices.

We loop through all positions for i, j, and k while maintaining the required i < j < k condition, and for each triplet, we compute the value and maintain the maximum encountered.

While this approach is simple, it's not efficient for large arrays due to its O(n^3) time complexity.

This Python function loops through each combination of i, j, and k, calculates the triplet value, and tracks the maximum value seen.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time complexity: O(n^3)
Space complexity: O(1)

Try this approach in the editor →

Approach 2: Optimized Approach with Prefix and Suffix Arrays

This approach aims to reduce repetitive calculations by maintaining prefix and suffix arrays.

The idea is to preprocess information to find the maximum elements before and after any element, thereby facilitating quick look-up while iterating through the central elements of the triplets.

This Python solution uses prefix and suffix arrays to maintain the maximum values up to each point. This allows an O(n^2) solution, significantly reducing the time compared to the brute force method.

Code

PythonC++

Python

C++

Complexity

Time complexity: O(n^2)
Space complexity: O(n)

Try this approach in the editor →

Approach 3: Maintaining Prefix Maximum and Maximum Difference

We use two variables mx and mxDiff to maintain the prefix maximum value and maximum difference, respectively, and use a variable ans to maintain the answer. Initially, these variables are all 0.

Next, we iterate through each element x in the array as nums[k]. First, we update the answer ans = max(ans, mxDiff times x). Then we update the maximum difference mxDiff = max(mxDiff, mx - x). Finally, we update the prefix maximum value mx = max(mx, x).

After iterating through all elements, we return the answer ans.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time complexity: O(n^3)
Space complexity: O(1)

Optimized Approach with Prefix and Suffix Arrays

Time complexity: O(n^2)
Space complexity: O(n)

Maintaining Prefix Maximum and Maximum Difference—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Triplet EnumerationO(n^3)O(1)Useful for understanding the problem or validating small test cases
Prefix and Suffix Maximum ArraysO(n)O(n)Best general solution for large arrays and interview settings

Video Solution

Maximum Value of an Ordered Triplet I | Multiple Approaches | Leetcode 2873 | codestorywithMIK • codestorywithMIK • 10,236 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Value of an Ordered Triplet I easy or hard?
The problem is categorized as Easy on LeetCode. The brute force idea is straightforward, but recognizing the prefix and suffix optimization is the key step that reduces the complexity to O(n).
How to solve Maximum Value of an Ordered Triplet I in O(n)?
Precompute prefix maximum values so you know the largest nums[i] to the left of each index. Also compute suffix maximum values to know the largest nums[k] to the right. Treat each index j as the middle element and compute (prefixMax[j-1] - nums[j]) * suffixMax[j+1], updating the maximum result during a single pass.
Maximum Value of an Ordered Triplet I Python or C++ solution
Python and C++ implementations typically build prefixMax and suffixMax arrays first. Then they iterate through the array treating each index as j, compute the candidate value using the precomputed maximums, and track the maximum result. This implementation runs in O(n) time.
What is the best approach for Maximum Value of an Ordered Triplet I?
The optimal approach uses prefix and suffix maximum arrays. For each index j, track the largest value before it (best i) and the largest value after it (best k). This allows computing (nums[i] - nums[j]) * nums[k] in a single pass. The overall complexity becomes O(n) time with O(n) extra space.
What data structure is used in Maximum Value of an Ordered Triplet I?
The solution primarily uses arrays. Two auxiliary arrays store prefix maximum values and suffix maximum values so the algorithm can quickly access the best candidate elements on both sides of the middle index.
What is the time complexity of Maximum Value of an Ordered Triplet I?
The brute force solution runs in O(n^3) time because it checks every possible ordered triplet. The optimized solution with prefix and suffix maximum arrays runs in O(n) time since it preprocesses the array and evaluates each index once.
Is Maximum Value of an Ordered Triplet I asked at Google, Amazon, or Meta?
Problems involving ordered triplets, prefix preprocessing, and array optimization frequently appear in technical interviews at large companies such as Amazon, Google, and Meta. While the exact problem may vary, the technique of using prefix and suffix maximums is a common interview pattern.

Ready to solve this problem?

Practice Maximum Value of an Ordered Triplet I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Sum of Mountain Triplets I

Next

Number of Arithmetic Triplets