Maximum Profitable Triplets With Increasing Prices II solution and explanation
IBM
The problem
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 <= 500001 <= prices[i] <= 50001 <= profits[i] <= 106
Approach overview
Problem Overview: You are given arrays representing item prices and profits. Pick three indices i < j < k such that prices[i] < prices[j] < prices[k] and the total profits[i] + profits[j] + profits[k] is maximized. If no valid triplet exists, return -1.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
Check every possible triplet (i, j, k) with three nested loops. For each combination, verify the increasing price condition and compute the total profit. Track the maximum profit seen. This method is straightforward but impractical once n grows beyond a few hundred because the number of combinations explodes to O(n^3). Useful only for understanding the constraints of the problem or validating smaller test cases.
Approach 2: Fix the Middle Element (O(n^2) time, O(1) space)
Treat index j as the middle element of the triplet. Scan the left side to find the best i where prices[i] < prices[j], then scan the right side to find the best k where prices[k] > prices[j]. Combine the best profits from both sides with profits[j]. This reduces one loop compared to brute force but still requires scanning the array for each middle index, resulting in O(n^2) time. Works for moderate input sizes but still too slow for large constraints.
Approach 3: Binary Indexed Tree (Fenwick Tree) Optimization (O(n log n) time, O(n) space)
The key observation: for each middle index j, you only need two values — the maximum profit to the left with a smaller price, and the maximum profit to the right with a larger price. These queries can be answered efficiently using a Binary Indexed Tree over compressed price coordinates.
First pass left-to-right: maintain a Fenwick tree storing the maximum profit seen for each price. Query the structure for the maximum profit among prices strictly less than prices[j]. This gives the best candidate for i. Update the tree with profits[j].
Second pass right-to-left: repeat the process to compute the best profit for k where prices[k] > prices[j]. Combine the best left and right values with profits[j] to compute the maximum triplet profit. Coordinate compression ensures the Fenwick tree size stays manageable.
This approach transforms repeated scans into O(log n) range queries and updates. The technique is common in problems involving ordered queries on arrays such as array optimization and range maximum lookups with segment trees or Fenwick trees.
Recommended for interviews: The Binary Indexed Tree approach. Interviewers expect you to recognize that the middle element splits the problem into two range maximum queries. Starting from the brute force demonstrates understanding, but the O(n log n) Fenwick tree solution shows strong command of advanced data structures.
Solution
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 5000.
class BinaryIndexedTree:
def __init__(self, n: int):
self.n = n
self.c = [0] * (n + 1)
def update(self, x: int, v: int):
while x <= self.n:
self.c[x] = max(self.c[x], v)
x += x & -x
def query(self, x: int) -> int:
mx = 0
while x:
mx = max(mx, self.c[x])
x -= x & -x
return mx
class Solution:
def maxProfit(self, prices: List[int], profits: List[int]) -> int:
n = len(prices)
left = [0] * n
right = [0] * n
m = max(prices)
tree1 = BinaryIndexedTree(m + 1)
tree2 = BinaryIndexedTree(m + 1)
for i, x in enumerate(prices):
left[i] = tree1.query(x - 1)
tree1.update(x, profits[i])
for i in range(n - 1, -1, -1):
x = m + 1 - prices[i]
right[i] = tree2.query(x - 1)
tree2.update(x, profits[i])
return max(
(l + x + r for l, x, r in zip(left, profits, right) if l and r), default=-1
)class BinaryIndexedTree {
private int n;
private int[] c;
public BinaryIndexedTree(int n) {
this.n = n;
c = new int[n + 1];
}
public void update(int x, int v) {
while (x <= n) {
c[x] = Math.max(c[x], v);
x += x & -x;
}
}
public int query(int x) {
int mx = 0;
while (x > 0) {
mx = Math.max(mx, c[x]);
x -= x & -x;
}
return mx;
}
}
class Solution {
public int maxProfit(int[] prices, int[] profits) {
int n = prices.length;
int[] left = new int[n];
int[] right = new int[n];
int m = 0;
for (int x : prices) {
m = Math.max(m, x);
}
BinaryIndexedTree tree1 = new BinaryIndexedTree(m + 1);
BinaryIndexedTree tree2 = new BinaryIndexedTree(m + 1);
for (int i = 0; i < n; ++i) {
int x = prices[i];
left[i] = tree1.query(x - 1);
tree1.update(x, profits[i]);
}
for (int i = n - 1; i >= 0; --i) {
int x = m + 1 - prices[i];
right[i] = tree2.query(x - 1);
tree2.update(x, profits[i]);
}
int ans = -1;
for (int i = 0; i < n; ++i) {
if (left[i] > 0 && right[i] > 0) {
ans = Math.max(ans, left[i] + profits[i] + right[i]);
}
}
return ans;
}
}class BinaryIndexedTree {
private:
int n;
vector<int> c;
public:
BinaryIndexedTree(int n) {
this->n = n;
c.resize(n + 1, 0);
}
void update(int x, int v) {
while (x <= n) {
c[x] = max(c[x], v);
x += x & -x;
}
}
int query(int x) {
int mx = 0;
while (x > 0) {
mx = max(mx, c[x]);
x -= x & -x;
}
return mx;
}
};
class Solution {
public:
int maxProfit(vector<int>& prices, vector<int>& profits) {
int n = prices.size();
vector<int> left(n, 0);
vector<int> right(n, 0);
int m = *max_element(prices.begin(), prices.end());
BinaryIndexedTree tree1(m + 1);
BinaryIndexedTree tree2(m + 1);
for (int i = 0; i < n; ++i) {
int x = prices[i];
left[i] = tree1.query(x - 1);
tree1.update(x, profits[i]);
}
for (int i = n - 1; i >= 0; --i) {
int x = m + 1 - prices[i];
right[i] = tree2.query(x - 1);
tree2.update(x, profits[i]);
}
int ans = -1;
for (int i = 0; i < n; ++i) {
if (left[i] > 0 && right[i] > 0) {
ans = max(ans, left[i] + profits[i] + right[i]);
}
}
return ans;
}
};class BinaryIndexedTree {
private n: number;
private c: number[];
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(0);
}
update(x: number, v: number): void {
while (x <= this.n) {
this.c[x] = Math.max(this.c[x], v);
x += x & -x;
}
}
query(x: number): number {
let mx = 0;
while (x > 0) {
mx = Math.max(mx, this.c[x]);
x -= x & -x;
}
return mx;
}
}
function maxProfit(prices: number[], profits: number[]): number {
const n: number = prices.length;
const left: number[] = Array(n).fill(0);
const right: number[] = Array(n).fill(0);
const m = Math.max(...prices);
const tree1: BinaryIndexedTree = new BinaryIndexedTree(m + 1);
const tree2: BinaryIndexedTree = new BinaryIndexedTree(m + 1);
for (let i = 0; i < n; i++) {
const x: number = prices[i];
left[i] = tree1.query(x - 1);
tree1.update(x, profits[i]);
}
for (let i = n - 1; i >= 0; i--) {
const x: number = m + 1 - prices[i];
right[i] = tree2.query(x - 1);
tree2.update(x, profits[i]);
}
let ans: number = -1;
for (let i = 0; i < n; i++) {
if (left[i] > 0 && right[i] > 0) {
ans = Math.max(ans, left[i] + profits[i] + right[i]);
}
}
return ans;
}type BinaryIndexedTree struct {
n int
c []int
}
func NewBinaryIndexedTree(n int) BinaryIndexedTree {
c := make([]int, n+1)
return BinaryIndexedTree{n: n, c: c}
}
func (bit *BinaryIndexedTree) update(x, v int) {
for x <= bit.n {
bit.c[x] = max(bit.c[x], v)
x += x & -x
}
}
func (bit *BinaryIndexedTree) query(x int) int {
mx := 0
for x > 0 {
mx = max(mx, bit.c[x])
x -= x & -x
}
return mx
}
func maxProfit(prices []int, profits []int) int {
n := len(prices)
left := make([]int, n)
right := make([]int, n)
m := slices.Max(prices)
tree1 := NewBinaryIndexedTree(m + 1)
tree2 := NewBinaryIndexedTree(m + 1)
for i, x := range prices {
left[i] = tree1.query(x - 1)
tree1.update(x, profits[i])
}
for i := n - 1; i >= 0; i-- {
x := m + 1 - prices[i]
right[i] = tree2.query(x - 1)
tree2.update(x, profits[i])
}
ans := -1
for i := 0; i < n; i++ {
if left[i] > 0 && right[i] > 0 {
ans = max(ans, left[i]+profits[i]+right[i])
}
}
return ans
}struct BinaryIndexedTree {
n: usize,
c: Vec<i32>,
}
impl BinaryIndexedTree {
fn new(n: usize) -> BinaryIndexedTree {
BinaryIndexedTree {
n,
c: vec![0; n + 1],
}
}
fn update(&mut self, x: usize, v: i32) {
let mut x = x;
while x <= self.n {
self.c[x] = self.c[x].max(v);
x += x & x.wrapping_neg();
}
}
fn query(&self, x: usize) -> i32 {
let mut x = x;
let mut mx = 0;
while x > 0 {
mx = mx.max(self.c[x]);
x -= x & x.wrapping_neg();
}
mx
}
}
impl Solution {
pub fn max_profit(prices: Vec<i32>, profits: Vec<i32>) -> i32 {
let n = prices.len();
let mut left = vec![0; n];
let mut right = vec![0; n];
let m = prices.iter().cloned().max().unwrap_or(0);
let mut tree1 = BinaryIndexedTree::new((m as usize) + 1);
let mut tree2 = BinaryIndexedTree::new((m as usize) + 1);
for i in 0..n {
let x = prices[i] as usize;
left[i] = tree1.query(x - 1);
tree1.update(x, profits[i]);
}
for i in (0..n).rev() {
let x = (m + 1 - prices[i]) as usize;
right[i] = tree2.query(x - 1);
tree2.update(x, profits[i]);
}
let mut ans = -1;
for i in 0..n {
if left[i] > 0 && right[i] > 0 {
ans = ans.max(left[i] + profits[i] + right[i]);
}
}
ans
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triplets | O(n^3) | O(1) | Conceptual understanding or very small inputs |
| Fix Middle Element + Scan Sides | O(n^2) | O(1) | Moderate constraints where brute force is too slow |
| Binary Indexed Tree / Fenwick Tree | O(n log n) | O(n) | Large arrays requiring fast ordered queries for max profit |
| Segment Tree | O(n log n) | O(n) | Alternative to Fenwick tree when range queries need more flexibility |
Frequently asked questions
Is Maximum Profitable Triplets With Increasing Prices II easy or hard?
Maximum Profitable Triplets With Increasing Prices II is classified as a Hard problem. The challenge comes from recognizing that the middle element splits the problem into two ordered queries and that a Fenwick tree or segment tree is required to achieve O(n log n) performance.
Maximum Profitable Triplets With Increasing Prices II Python/Java solution
Efficient implementations typically use a Fenwick tree to track maximum profits by compressed price index. The logic remains identical across languages such as Python, Java, C++, Go, TypeScript, and Rust: perform prefix maximum queries and updates while scanning the array.
How to solve Maximum Profitable Triplets With Increasing Prices II in O(n log n)?
Treat each index as the middle element of the triplet. Use a Fenwick tree to store the maximum profit for prices encountered so far and query the best profit with a smaller price. Perform a reverse pass to compute the best profit on the right with larger prices. Combine left + current + right profits while maintaining O(log n) updates and queries.
What is the best approach for Maximum Profitable Triplets With Increasing Prices II?
The optimal approach uses a Binary Indexed Tree (Fenwick Tree) with coordinate compression. For each index treated as the middle element, you query the maximum profit on the left with a smaller price and the maximum profit on the right with a larger price. Each query and update takes O(log n), leading to an overall O(n log n) time complexity.
Is Maximum Profitable Triplets With Increasing Prices II asked at Google/Amazon/Meta?
Problems involving increasing sequences with profit maximization and range queries appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that require Fenwick trees, segment trees, or ordered maps are common in senior-level algorithm rounds.
What data structure is used in Maximum Profitable Triplets With Increasing Prices II?
The most common data structure is a Binary Indexed Tree (Fenwick Tree) used for range maximum queries after coordinate-compressing prices. A Segment Tree can also solve the same problem with similar O(n log n) complexity.
What is the time complexity of Maximum Profitable Triplets With Increasing Prices II?
The optimal solution runs in O(n log n) time using a Binary Indexed Tree or Segment Tree to perform range maximum queries. Brute force enumeration takes O(n^3), and a middle-element scanning approach reduces it to O(n^2). The Fenwick tree solution scales efficiently for large inputs.