Maximum Profitable Triplets With Increasing Prices II

Maximum Profitable Triplets With Increasing Prices II - Problem

You are given two 0-indexed arrays prices and profits of length n. There are n items in a store where the i^th item has a price of prices[i] and a profit of profits[i].

We need to pick exactly 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, or -1 if it's not possible to pick three items with the given condition.

Input & Output

Example 1 — Basic Valid Triplet

$ Input: prices = [10,20,30,40], profits = [20,30,40,50]

› Output: 120

💡 Note: Pick indices (0,1,2): prices 10 < 20 < 30, profits 20+30+40 = 90. Pick indices (0,1,3): prices 10 < 20 < 40, profits 20+30+50 = 100. Pick indices (0,2,3): prices 10 < 30 < 40, profits 20+40+50 = 110. Pick indices (1,2,3): prices 20 < 30 < 40, profits 30+40+50 = 120. Maximum is 120.

Example 2 — No Valid Triplet

$ Input: prices = [4,3,2,1], profits = [33,20,19,56]

› Output: -1

💡 Note: Prices are in decreasing order, so no triplet (i,j,k) exists where prices[i] < prices[j] < prices[k].

Example 3 — Mixed Order

$ Input: prices = [1,7,3,10,5], profits = [5,10,3,6,4]

› Output: 20

💡 Note: Pick indices (0,1,3): prices 1 < 7 < 10, profits 5+10+6 = 21. Pick indices (0,2,3): prices 1 < 3 < 10, profits 5+3+6 = 14. Pick indices (2,4,3) is invalid since 4 > 3. Best valid triplet gives profit 21.

Constraints

3 ≤ prices.length = profits.length ≤ 2000
1 ≤ prices[i] ≤ 5000
1 ≤ profits[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays: prices and profits of items

Constraint

Find triplet (i,j,k) where i < j < k and prices[i] < prices[j] < prices[k]

Output

Maximum sum of profits[i] + profits[j] + profits[k]

Key Takeaway

🎯 Key Insight: Fix the middle element and optimize left/right searches for maximum profits

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is to fix the middle element and efficiently find maximum profits on left and right with valid price constraints. The optimal approach uses advanced data structures like segment trees for O(n log n) complexity, but the simpler O(n²) fix-middle solution works well for most cases. Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Segment Tree / Binary Indexed Tree	O(n log n)	O(n)	Use advanced data structures to efficiently query maximum profits in price ranges
Brute Force - Check All Triplets	O(n³)	O(1)	Check every possible triplet (i,j,k) with i < j < k and prices[i] < prices[j] < prices[k]
Fix Middle Element	O(n²)	O(1)	For each middle element j, find maximum profit elements on left and right with valid price constraints

Segment Tree / Binary Indexed Tree — Algorithm Steps

Create sorted indices by price
For each middle element, query max profit in valid price ranges
Use segment tree for range maximum queries
Update tree as we process elements

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort by Price

Create sorted order for coordinate compression

Build Tree

Construct segment tree for range maximum queries

Query & Update

For each middle element, query valid ranges

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* prices, int* profits, int n) {
    if (n < 3) return -1;
    
    int maxProfit = -1;
    
    // Simple approach: for each middle element
    for (int j = 1; j < n - 1; j++) {
        int leftMax = -1;
        int rightMax = -1;
        
        // Find max profit on left with smaller price
        for (int i = 0; i < j; i++) {
            if (prices[i] < prices[j]) {
                if (leftMax == -1 || profits[i] > leftMax) {
                    leftMax = profits[i];
                }
            }
        }
        
        // Find max profit on right with larger price
        for (int k = j + 1; k < n; k++) {
            if (prices[k] > prices[j]) {
                if (rightMax == -1 || profits[k] > rightMax) {
                    rightMax = profits[k];
                }
            }
        }
        
        if (leftMax != -1 && rightMax != -1) {
            int current = leftMax + profits[j] + rightMax;
            if (maxProfit == -1 || current > maxProfit) {
                maxProfit = current;
            }
        }
    }
    
    return maxProfit;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int prices[1000], profits[1000];
    int n = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        prices[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    int m = 0;
    token = strtok(line + 1, ",]");
    while (token != NULL) {
        profits[m++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(prices, profits, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), each query and update on segment tree takes O(log n)

⚡ Linearithmic

Space Complexity

O(n)

Segment tree requires O(n) space for storing maximum values

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Segment Tree / Binary Indexed Tree — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler