LeetCode Problem 2907

Difficulty: 🟡 Medium
Topics: Array, Binary Indexed Tree, Segment Tree

Solution

LeetCode 2907 - Maximum Profitable Triplets With Increasing Prices I

Problem Understanding

This problem asks us to select exactly three items from a store while satisfying both an index ordering condition and a strictly increasing price condition.

We are given two arrays:

• prices[i] represents the price of the ith item
• profits[i] represents the profit earned from selecting the ith item

We must choose indices i, j, and k such that:

• i < j < k
• prices[i] < prices[j] < prices[k]

If these conditions are satisfied, the total profit becomes:

$$profits[i] + profits[j] + profits[k]$$

Our goal is to maximize this total profit. If no valid triplet exists, we must return -1.

The important detail is that both the indices and prices must increase strictly. Increasing indices alone are not enough, and increasing prices alone are not enough. Both conditions must hold simultaneously.

The constraints are relatively small:

• n <= 2000

This immediately tells us that an O(n^2) solution is acceptable because:

$$2000^2 = 4,000,000$$

which is manageable.

However, an O(n^3) brute-force approach would require up to:

$$2000^3 = 8,000,000,000$$

operations, which is far too slow.

Several edge cases are important:

• Arrays may already be strictly decreasing, making any valid triplet impossible.
• Multiple items may have high profits but incompatible prices.
• The optimal triplet may not involve the globally highest profits.
• Prices must be strictly increasing, equal prices cannot be used together.
• There may be only one valid triplet in the entire array.

The problem guarantees:

• Both arrays have the same length.
• All values are positive integers.
• At least three elements exist.

Approaches

Brute Force Approach

The most direct solution is to try every possible triplet (i, j, k) where:

• i < j < k

For every triplet, we check whether:

$$prices[i] < prices[j] < prices[k]$$

If the condition holds, we compute the profit sum and track the maximum.

This approach is correct because it exhaustively evaluates every valid possibility. No triplet can be missed.

However, there are three nested loops, so the time complexity becomes:

$$O(n^3)$$

With n = 2000, this is too slow.

Optimal Approach

The key observation is that each valid triplet has a middle element j.

If we fix j, then:

• We need the best valid left element i
• We need the best valid right element k

Specifically:

• i < j and prices[i] < prices[j]
• k > j and prices[k] > prices[j]

For every position j, we can scan:

• Left side to find the maximum possible left profit
• Right side to find the maximum possible right profit

Then the candidate answer becomes:

$$bestLeft + profits[j] + bestRight$$

This reduces the complexity to O(n^2).

Since n <= 2000, this is efficient enough.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every possible triplet
Optimal	O(n²)	O(1)	Treats each index as the middle element

Algorithm Walkthrough

1. Initialize the answer as -1.

We use -1 because the problem requires returning -1 when no valid triplet exists. 2. Iterate through every index j as the middle element.

The middle element determines the structure of the triplet. Every valid triplet must have exactly one middle position. 3. Search the left side of j.

For every index i < j, check whether:

$$prices[i] < prices[j]$$

If valid, update the maximum left profit. 4. Search the right side of j.

For every index k > j, check whether:

$$prices[k] > prices[j]$$

If valid, update the maximum right profit. 5. If both sides contain valid candidates, compute the total profit.

The total becomes:

$$leftBest + profits[j] + rightBest$$ 6. Update the global maximum answer. 7. After processing all middle positions, return the final answer.

Why it works

Every valid triplet has a unique middle index j. By fixing j, the problem separates into two independent subproblems:

• Find the best valid left element
• Find the best valid right element

Because we examine all possible middle positions and always choose the maximum compatible profits on both sides, the algorithm guarantees the optimal total profit is found.

Python Solution

from typing import List

class Solution:
    def maxProfit(self, prices: List[int], profits: List[int]) -> int:
        n = len(prices)
        best_profit = -1

        for middle in range(n):
            left_best = -1
            right_best = -1

            # Find best left candidate
            for left in range(middle):
                if prices[left] < prices[middle]:
                    left_best = max(left_best, profits[left])

            # Find best right candidate
            for right in range(middle + 1, n):
                if prices[right] > prices[middle]:
                    right_best = max(right_best, profits[right])

            # If both sides are valid, update answer
            if left_best != -1 and right_best != -1:
                total_profit = left_best + profits[middle] + right_best
                best_profit = max(best_profit, total_profit)

        return best_profit

The implementation directly follows the algorithm.

The outer loop treats every index as the middle element of the triplet.

For each middle position:

• The first inner loop searches leftward for the highest profit whose price is smaller.
• The second inner loop searches rightward for the highest profit whose price is larger.

If both valid sides exist, we combine their profits with the middle profit and update the answer.

The implementation uses only a few integer variables, so the extra memory usage stays constant.

Go Solution

package main

func maxProfit(prices []int, profits []int) int {
	n := len(prices)
	bestProfit := -1

	for middle := 0; middle < n; middle++ {
		leftBest := -1
		rightBest := -1

		// Find best left candidate
		for left := 0; left < middle; left++ {
			if prices[left] < prices[middle] {
				if profits[left] > leftBest {
					leftBest = profits[left]
				}
			}
		}

		// Find best right candidate
		for right := middle + 1; right < n; right++ {
			if prices[right] > prices[middle] {
				if profits[right] > rightBest {
					rightBest = profits[right]
				}
			}
		}

		// Update answer if valid triplet exists
		if leftBest != -1 && rightBest != -1 {
			totalProfit := leftBest + profits[middle] + rightBest

			if totalProfit > bestProfit {
				bestProfit = totalProfit
			}
		}
	}

	return bestProfit
}

The Go implementation is structurally identical to the Python solution.

One small difference is that Go does not provide a built in max() function for integers, so comparisons are written explicitly using if statements.

Integer overflow is not a concern because the problem guarantees all results fit inside a signed 32-bit integer.

Worked Examples

Example 1

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

We examine each middle position.

Middle Index	Middle Price	Best Left Profit	Best Right Profit	Total
0	10	none	none	invalid
1	2	none	10	invalid
2	3	2	10	19
3	4	7	none	invalid

The best valid answer is:

$$2 + 7 + 10 = 19$$

Result:

19

Example 2

prices  = [1,2,3,4,5]
profits = [1,5,3,4,6]

All prices are increasing, so many triplets are valid.

Middle Index	Middle Profit	Best Left Profit	Best Right Profit	Total
1	5	1	6	12
2	3	5	6	14
3	4	5	6	15

Maximum result:

$$5 + 4 + 6 = 15$$

Result:

15

Example 3

prices  = [4,3,2,1]
profits = [33,20,19,87]

Prices are strictly decreasing.

No valid triplet can satisfy:

$$prices[i] < prices[j] < prices[k]$$

Result:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Each middle index scans both left and right sides
Space	O(1)	Only a few variables are used

The outer loop runs n times. For each middle index, we may scan up to n elements on the left and right combined. This gives quadratic complexity overall.

No additional arrays or data structures are required, so the extra memory usage remains constant.

Test Cases

from typing import List

class Solution:
    def maxProfit(self, prices: List[int], profits: List[int]) -> int:
        n = len(prices)
        best_profit = -1

        for middle in range(n):
            left_best = -1
            right_best = -1

            for left in range(middle):
                if prices[left] < prices[middle]:
                    left_best = max(left_best, profits[left])

            for right in range(middle + 1, n):
                if prices[right] > prices[middle]:
                    right_best = max(right_best, profits[right])

            if left_best != -1 and right_best != -1:
                best_profit = max(
                    best_profit,
                    left_best + profits[middle] + right_best
                )

        return best_profit

sol = Solution()

assert sol.maxProfit([10,2,3,4], [100,2,7,10]) == 19
# Basic example with exactly one valid triplet

assert sol.maxProfit([1,2,3,4,5], [1,5,3,4,6]) == 15
# Fully increasing prices

assert sol.maxProfit([4,3,2,1], [33,20,19,87]) == -1
# No valid triplet exists

assert sol.maxProfit([1,3,2,4], [5,100,6,7]) == 112
# Best middle choice is not the largest price

assert sol.maxProfit([1,2,2,3], [1,10,20,30]) == 51
# Equal prices cannot both be used

assert sol.maxProfit([5,1,6,2,7], [10,20,30,40,50]) == 110
# Non-contiguous valid triplet

assert sol.maxProfit([1,2,3], [10,20,30]) == 60
# Smallest valid array size

assert sol.maxProfit([3,1,2], [5,6,7]) == -1
# Minimum size but invalid ordering

Test Summary

Test	Why
[10,2,3,4]	Validates basic functionality
[1,2,3,4,5]	Tests fully increasing prices
[4,3,2,1]	Tests impossible case
[1,3,2,4]	Tests nontrivial middle selection
[1,2,2,3]	Verifies strict inequality handling
[5,1,6,2,7]	Tests scattered valid indices
[1,2,3]	Smallest valid input size
[3,1,2]	Smallest invalid configuration

Edge Cases

One important edge case occurs when the prices array is strictly decreasing. In this scenario, no triplet can ever satisfy the increasing price requirement. A naive implementation might incorrectly assume some triplet always exists. This solution safely handles the situation by initializing the answer to -1 and updating it only when both valid left and right candidates exist.

Another important case involves duplicate prices. The condition requires strictly increasing prices, not nondecreasing prices. For example, prices like [1,2,2,3] cannot use both 2 values together. The implementation correctly uses strict comparisons:

prices[left] < prices[middle]

and

prices[right] > prices[middle]

so duplicates are automatically excluded.

A third edge case occurs when the highest profit items do not form a valid increasing sequence. A greedy approach that simply picks the top three profits would fail. The algorithm avoids this mistake by validating every candidate against the price ordering rules before considering its profit contribution.