LeetCode Solutions Blog

Maximum Profitable Triplets With Increasing Prices II

Number: 3204

Difficulty: Hard

Paid? Yes

Companies: IBM

Problem Description

Given two 0-indexed arrays prices and profits where the iᵗʰ item costs prices[i] and yields a profit of profits[i], pick three items with indices i, j, k (with i < j < k) satisfying prices[i] < prices[j] < prices[k]. The goal is to maximize the total profit: profits[i] + profits[j] + profits[k]. If no valid triplet exists, return -1.

Key Insights

For each candidate middle item j, we independently need:
- A left candidate i (with i < j) having the largest profit among those with prices[i] < prices[j].
- A right candidate k (with k > j) having the largest profit among those with prices[k] > prices[j].
The sum is linear so the problem reduces to precomputing for every index j the optimal left and right profits.
Because prices are bounded (up to 5000), Binary Indexed Trees (BIT) or Segment Trees can be used to quickly query maximum profits over a range of prices.
The left side can be processed in a forward pass using a standard BIT that supports range maximum queries.
The right side is processed in a backward pass. By mapping each price p to a reversed index (maxPrice – p + 1), we can use a BIT to quickly query the maximum profit among items with higher price.

Space and Time Complexity

Time Complexity: O(n log M), where M is the maximum price (<= 5000) Space Complexity: O(M + n)

Solution

We solve the problem in two passes:

During a left-to-right pass, for each index j, we use a BIT (keyed by price) to query the maximum profit among all indices i < j with prices[i] < prices[j]. This value is stored in leftBest[j].
During a right-to-left pass, we use a modified BIT that works on reversed price indices. For each index j, we query for the maximum profit among indices k > j having prices[k] > prices[j] and store the result in rightBest[j].
Finally, for each index j that qualifies (both leftBest[j] and rightBest[j] are valid), we compute the sum leftBest[j] + profits[j] + rightBest[j] and track the maximum sum.
If no valid triplet exists, return -1.

Key data structures:

Two Binary Indexed Trees (one for each pass) for efficient range maximum queries.
The BIT update and query operations run in O(log M) time.

This approach ensures we meet the constraint requirements even for n up to 50000.

Code Solutions

# Python solution with detailed inline comments

# Define BIT for standard (prefix maximum queries)
class BIT:
    def __init__(self, size):
        self.size = size
        self.tree = [0]*(size+1)
    
    # Update BIT: at index 'i', store maximum of current value and new 'value'
    def update(self, i, value):
        while i <= self.size:
            self.tree[i] = max(self.tree[i], value)
            i += i & -i
            
    # Query for maximum value in range [1, i]
    def query(self, i):
        result = 0
        while i > 0:
            result = max(result, self.tree[i])
            i -= i & -i
        return result

def maximumProfitTriplets(prices, profits):
    n = len(prices)
    maxPrice = max(prices)
    
    # Left pass: for each index j, find the maximum profit from an index i (< j) with price < prices[j]
    leftBest = [-1] * n
    bit_left = BIT(maxPrice)
    for j in range(n):
        # Query BIT for prices less than prices[j]: use prices[j]-1
        best = bit_left.query(prices[j] - 1)
        # If no valid left profit found, best remains 0 and we set leftBest[j] to -1
        leftBest[j] = best if best > 0 else -1
        # Update BIT with current profit at position prices[j]
        bit_left.update(prices[j], profits[j])
    
    # Right pass: use reversed indexing to query items with higher price efficiently.
    # Map each price p to: rev_index = maxPrice - p + 1.
    # For an item j, items with price > prices[j] will have rev_index < (maxPrice - prices[j] + 1).
    rightBest = [-1] * n
    bit_right = BIT(maxPrice)
    for j in range(n-1, -1, -1):
        rev_index = maxPrice - prices[j] + 1
        # Query BIT for rev_index-1 to get maximum profit among items with price > prices[j]
        best = bit_right.query(rev_index - 1)
        rightBest[j] = best if best > 0 else -1
        # Update BIT at rev_index with profits[j]
        bit_right.update(rev_index, profits[j])
    
    # Calculate the maximum triplet profit
    max_triplet = -1
    for j in range(n):
        if leftBest[j] != -1 and rightBest[j] != -1:
            current_sum = leftBest[j] + profits[j] + rightBest[j]
            max_triplet = max(max_triplet, current_sum)
    
    return max_triplet

# Example usage:
# prices = [10, 2, 3, 4]
# profits = [100, 2, 7, 10]
# print(maximumProfitTriplets(prices, profits))  # Expected output: 19