LeetCode 2921 - Maximum Profitable Triplets With Increasing Prices II

Difficulty: 🔴 Hard
Topics: Array, Binary Indexed Tree, Segment Tree

Solution

Problem Understanding

The problem asks us to select three items from a store such that their prices are strictly increasing and their indices are in order, i.e., if we pick items i, j, and k, we must have i < j < k and prices[i] < prices[j] < prices[k]. Each item also has a corresponding profit, and the total profit of a valid triplet is the sum of the three items' profits. Our task is to maximize this profit or return -1 if no such triplet exists.

The input consists of two arrays, prices and profits, both of length n, where 3 <= n <= 50000. The prices array contains integers in the range [1, 5000], and profits contain integers in [1, 10^6]. This tells us the input is large enough that a naive O(n^3) solution would be infeasible, so an optimized approach is necessary.

Important edge cases include strictly decreasing prices (no valid triplet exists), repeated prices (since the sequence must be strictly increasing, duplicates cannot be used consecutively), and minimal input size n = 3.

Approaches

The brute-force approach would be to iterate over all possible triplets (i, j, k) with nested loops, checking the conditions i < j < k and prices[i] < prices[j] < prices[k] and computing the total profit. While this guarantees correctness, it has a time complexity of O(n^3), which is too slow for n = 50000.

The optimal approach leverages the idea of precomputing maximum profits for potential left and right elements of the middle item. Specifically, for each index j considered as the middle item, we compute:

The maximum profit for an item i < j where prices[i] < prices[j].
The maximum profit for an item k > j where prices[k] > prices[j].

These maximums can be efficiently computed using a Binary Indexed Tree (Fenwick Tree) or Segment Tree indexed by price values, which allows querying the maximum profit for all prices less than or greater than a given price in O(log P) time, where P is the maximum price (5000). This reduces the time complexity to O(n log P).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(1)	Iterates over all triplets and sums profits if valid
Optimal	O(n log P)	O(P)	Uses segment trees/BIT to precompute maximum left/right profits efficiently

Algorithm Walkthrough

Initialize two Binary Indexed Trees (or Segment Trees), one to track maximum profit for prices to the left and one for prices to the right.
Traverse the array from left to right, for each j compute max_left_profit[j] as the maximum profit of any i < j such that prices[i] < prices[j] using a query on the left BIT.
Traverse the array from right to left, for each j compute max_right_profit[j] as the maximum profit of any k > j such that prices[k] > prices[j] using a query on the right BIT.
Iterate through all indices j as the middle element and compute the total profit as max_left_profit[j] + profits[j] + max_right_profit[j].
Track the maximum profit across all valid middle indices. If no valid triplet exists (some max_left_profit or max_right_profit is zero), return -1.

Why it works: For each middle element j, the algorithm guarantees that the chosen left and right elements produce the maximum possible profit that satisfies the strictly increasing price condition. The segment tree/BIT ensures that the query for the maximum profit among eligible prices is efficient.

Python Solution

from typing import List

class BIT:
    def __init__(self, size: int):
        self.tree = [0] * (size + 2)
        self.size = size + 2
    
    def update(self, index: int, value: int):
        while index < self.size:
            self.tree[index] = max(self.tree[index], value)
            index += index & -index
    
    def query(self, index: int) -> int:
        res = 0
        while index > 0:
            res = max(res, self.tree[index])
            index -= index & -index
        return res

class Solution:
    def maxProfit(self, prices: List[int], profits: List[int]) -> int:
        n = len(prices)
        max_price = max(prices)
        
        left_bit = BIT(max_price)
        max_left_profit = [0] * n
        for i in range(n):
            max_left_profit[i] = left_bit.query(prices[i] - 1)
            left_bit.update(prices[i], profits[i])
        
        right_bit = BIT(max_price)
        max_right_profit = [0] * n
        for i in range(n - 1, -1, -1):
            # query for prices greater than current
            max_right_profit[i] = right_bit.query(max_price) - right_bit.query(prices[i])
            right_bit.update(prices[i], profits[i])
        
        result = -1
        for i in range(n):
            if max_left_profit[i] > 0 and max_right_profit[i] > 0:
                result = max(result, max_left_profit[i] + profits[i] + max_right_profit[i])
        return result

Explanation: We use a Binary Indexed Tree to maintain the maximum profit for all prices seen so far (left side) and for all prices to the right. For each index, we query the left tree for max profit among smaller prices and the right tree for max profit among larger prices, then combine with the middle profit to update the result.

Go Solution

package main

func maxProfit(prices []int, profits []int) int {
	n := len(prices)
	maxPrice := 0
	for _, p := range prices {
		if p > maxPrice {
			maxPrice = p
		}
	}

	BIT := func(size int) []int {
		return make([]int, size+2)
	}
	update := func(bit []int, index int, value int) {
		for index < len(bit) {
			if bit[index] < value {
				bit[index] = value
			}
			index += index & -index
		}
	}
	query := func(bit []int, index int) int {
		res := 0
		for index > 0 {
			if bit[index] > res {
				res = bit[index]
			}
			index -= index & -index
		}
		return res
	}

	leftBit := BIT(maxPrice)
	maxLeft := make([]int, n)
	for i := 0; i < n; i++ {
		maxLeft[i] = query(leftBit, prices[i]-1)
		update(leftBit, prices[i], profits[i])
	}

	rightBit := BIT(maxPrice)
	maxRight := make([]int, n)
	for i := n - 1; i >= 0; i-- {
		maxRight[i] = query(rightBit, maxPrice) - query(rightBit, prices[i])
		update(rightBit, prices[i], profits[i])
	}

	result := -1
	for i := 0; i < n; i++ {
		if maxLeft[i] > 0 && maxRight[i] > 0 {
			sum := maxLeft[i] + profits[i] + maxRight[i]
			if sum > result {
				result = sum
			}
		}
	}
	return result
}

Note: The Go implementation is similar to Python. The slice is used for BIT storage, and indexing is handled carefully to avoid out-of-bounds. Go handles integers natively large enough to store profits without overflow.

Worked Examples

Example 1: prices = [10,2,3,4], profits = [100,2,7,10]

Step 1: Compute max_left_profit using BIT:

i	prices[i]	profits[i]	max_left_profit[i]
0	10	100	0
1	2	2	0
2	3	7	2
3	4	10	7

Step 2: Compute max_right_profit using BIT:

i	max_right_profit[i]
3	0
2	10
1	7
0	0

Step 3: Compute result:

i = 2 → max_left = 2, middle = 7, max_right = 10 → total = 19
Result = 19

Example 3: strictly decreasing prices → no valid triplet → return -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log P)	We traverse the array twice and each BIT operation is O(log P)
Space