Is Maximum Profitable Triplets With Increasing Prices I easy or hard?

This problem is generally rated Medium. The brute-force reasoning is straightforward, but reaching the optimal O(n log n) solution requires understanding Fenwick Trees or Segment Trees along with coordinate compression.

Maximum Profitable Triplets With Increasing Prices I Python/Java solution

Python and Java implementations usually follow the same pattern: coordinate compress the prices, maintain a Fenwick Tree storing maximum profit, and perform prefix queries to find the best candidate with a smaller price. A second pass from the right computes the best larger-price candidate before combining results.

What is the best approach for Maximum Profitable Triplets With Increasing Prices I?

The most efficient approach uses a Binary Indexed Tree (Fenwick Tree) with coordinate compression. It allows querying the maximum profit for prices smaller or larger than the current element in O(log n). By computing the best left and right candidates for every index, the overall complexity becomes O(n log n) with O(n) space.

Is Maximum Profitable Triplets With Increasing Prices I asked at Google/Amazon/Meta?

Problems combining increasing constraints with range queries appear frequently in interviews at large tech companies such as Google, Amazon, and Meta. Variants often require Fenwick Trees, Segment Trees, or ordered maps to efficiently query prefix or suffix ranges.

What data structure is used in Maximum Profitable Triplets With Increasing Prices I?

The optimal solution typically uses a Binary Indexed Tree (Fenwick Tree) to maintain prefix maximum profits for compressed price indices. A Segment Tree can also solve the same range maximum query problem with similar O(n log n) complexity.

What is the time complexity of Maximum Profitable Triplets With Increasing Prices I?

A straightforward enumeration of the middle element takes O(n^2) time because each index scans both the prefix and suffix to find valid partners. The optimized approach using a Binary Indexed Tree reduces the complexity to O(n log n) by turning repeated scans into logarithmic range maximum queries.

Description Hints 6 Solution Video 27:46

2907. Maximum Profitable Triplets With Increasing Prices I

Q: How to solve Maximum Profitable Triplets With Increasing Prices I in O(n log n)?

Compress the price values and use a Binary Indexed Tree to store the maximum profit seen for each price rank. Sweep left to right to compute the best profit for a smaller price, then sweep right to left for larger prices. Combine these with the current profit to evaluate each possible middle element in linear time.

Medium56.2% acceptance1 companyPremium elsewhere, free here

Given the 0-indexed arrays prices and profits of length n. There are n items in an store where the i^th 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] 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, 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 <= 2000
1 <= prices[i] <= 10⁶
1 <= profits[i] <= 10⁶

Asked at 1 company

IBM

Topics

Hints open one at a time

Hint 1

Let's fix the middle chosen item.

Hint 2

For a fixed item with an index j, iterate over items with an index k > j such that prices[k] > prices[j].

Hint 3

Find the maximum profit[k] with the above condition. Let's call this maximum value max_right.

Hint 4

Do the same for items with an index i < j such that prices[i] < prices[j] and find the maximum profit[i] among them. Let's call this maximum value max_left.

Hint 5

Now the profit when an item with the index j is the middle one would be profit[j] + max_right + max_left.

Hint 6

Finally, do the above procedure for all j's and find the maximum profit among them. That would be the final answer.

27:46

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[10,2,3,4]
[100,2,7,10]

Input

[1,2,3,4,5]
[1,5,3,4,6]

Input

[4,3,2,1]
[33,20,19,87]

Your code is saved on this device.Solution