Maximum Profitable Triplets With Increasing Prices I - Solution & Explanation
Problem Statement
Given the 0-indexed arrays prices and profits of length n. There are n items in an store where the ith item has a price of prices[i] and a profit of profits[i].
We have to pick three items with the following condition:
prices[i] < prices[j] < prices[k]wherei < j < k.
If we pick items with indices i, j and k satisfying the above condition, the profit would be profits[i] + profits[j] + profits[k].
Return the maximum profit we can get, and -1 if it's not possible to pick three items with the given condition.
Example 1:
Input: prices = [10,2,3,4], profits = [100,2,7,10] Output: 19 Explanation: We can't pick the item with index i=0 since there are no indices j and k such that the condition holds. So the only triplet we can pick, are the items with indices 1, 2 and 3 and it's a valid pick since prices[1] < prices[2] < prices[3]. The answer would be sum of their profits which is 2 + 7 + 10 = 19.
Example 2:
Input: prices = [1,2,3,4,5], profits = [1,5,3,4,6] Output: 15 Explanation: We can select any triplet of items since for each triplet of indices i, j and k such that i < j < k, the condition holds. Therefore the maximum profit we can get would be the 3 most profitable items which are indices 1, 3 and 4. The answer would be sum of their profits which is 5 + 4 + 6 = 15.
Example 3:
Input: prices = [4,3,2,1], profits = [33,20,19,87] Output: -1 Explanation: We can't select any triplet of indices such that the condition holds, so we return -1.
Constraints:
3 <= prices.length == profits.length <= 20001 <= prices[i] <= 1061 <= profits[i] <= 106
Approach Overview
Problem Overview: You are given two arrays prices and profits. Choose three indices i < j < k such that prices[i] < prices[j] < prices[k]. Among all valid triplets, return the maximum possible sum profits[i] + profits[j] + profits[k]. If no valid triplet exists, return -1.
Approach 1: Enumerate the Middle Element (O(nĀ²) time, O(1) space)
Treat each index j as the middle element of the triplet. Scan the left side to find the maximum profits[i] where prices[i] < prices[j]. Then scan the right side to find the maximum profits[k] where prices[k] > prices[j]. If both exist, compute the candidate profit profits[i] + profits[j] + profits[k] and update the answer. This brute-force style enumeration works because every valid triplet must have a unique middle element. The downside is the nested scanning: for each j, you potentially traverse the entire prefix and suffix, leading to O(nĀ²) time and O(1) extra space. Still useful as a baseline and easy to reason about.
Approach 2: Binary Indexed Tree (O(n log n) time, O(n) space)
The expensive part of the previous approach is repeatedly searching for the best profit on the left and right with price constraints. A Binary Indexed Tree (Fenwick Tree) stores the maximum profit seen so far for compressed price values and answers these queries in O(log n). First coordinate-compress the values in prices. Sweep from left to right and use the BIT to query the maximum profit for any price smaller than prices[j]. Store this as the best left candidate. Then sweep from right to left using another BIT to compute the best right candidate where price is greater than the current one. Once both arrays are built, combine them with profits[j] to evaluate each triplet in linear time. This reduces repeated scans and brings the complexity down to O(n log n) time with O(n) extra space.
This problem mixes ordering constraints with range maximum queries, which is why data structures from the segment tree or Fenwick tree family fit naturally. The input itself is a simple array, but the increasing price condition turns it into a range query problem.
Recommended for interviews: Start by explaining the middle-element enumeration. It proves you understand the structure of the triplet constraint. Then move to the Binary Indexed Tree optimization that answers "best profit with smaller/greater price" queries in O(log n). Interviewers usually expect the O(n log n) approach because it demonstrates familiarity with coordinate compression and Fenwick Trees for range maximum queries.
Approach 1: Enumerate the Middle Element
We can enumerate the middle element profits[j], and then enumerate the left element profits[i] and the right element profits[k]. For each profits[j], we need to find the maximum profits[i] and the maximum profits[k] such that prices[i] < prices[j] < prices[k]. We define left as the maximum value on the left of profits[j], and right as the maximum value on the right of profits[j]. If they exist, we update the answer as ans = max(ans, left + profits[j] + right).
The time complexity is O(n^2), where n is the length of the array. The space complexity is O(1).
Approach 2: Binary Indexed Tree
We can use two Binary Indexed Trees (BITs) to maintain the maximum profit on the left and right of each price, respectively. Then, we enumerate the middle price, query the maximum profit on both sides through the BIT, and finally take the maximum value.
The time complexity is O(n times log M), and the space complexity is O(M). Here, n is the length of the array prices, and M is the maximum value in the array prices. In this problem, M \le 10^6.
Since the length of prices does not exceed 2000, and the value of prices[i] reaches 10^6, we can discretize prices, which can reduce the space complexity to O(n).
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Enumerate the Middle Element | ā |
| Binary Indexed Tree | ā |
| Default Approach | ā |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Enumerate the Middle Element | O(nĀ²) | O(1) | Good baseline solution and easy to implement when constraints are small. |
| Binary Indexed Tree (Fenwick Tree) | O(n log n) | O(n) | Best general solution for large inputs where repeated range maximum queries are needed. |
Video Solution
Sliding Window: Best Time to Buy and Sell Stock - Leetcode 121 - Python ā¢ NeetCode ā¢ 848,276 views views
Watch 9 more video solutions āFrequently Asked Questions
Is Maximum Profitable Triplets With Increasing Prices I easy or hard?
Maximum Profitable Triplets With Increasing Prices I Python/Java solution
How to solve Maximum Profitable Triplets With Increasing Prices I in O(n log n)?
What is the best approach for Maximum Profitable Triplets With Increasing Prices I?
Is Maximum Profitable Triplets With Increasing Prices I asked at Google/Amazon/Meta?
What data structure is used in Maximum Profitable Triplets With Increasing Prices I?
What is the time complexity of Maximum Profitable Triplets With Increasing Prices I?
Ready to solve this problem?
Practice Maximum Profitable Triplets With Increasing Prices I with our built-in code editor and test cases.
Practice on FleetCode