Watch 10 video solutions for Maximum Profitable Triplets With Increasing Prices I, a medium level problem involving Array, Binary Indexed Tree, Segment Tree. This walkthrough by NeetCode has 848,276 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] where i < 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] <= 106Problem 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 | 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. |