Problem Description

You are given two arrays prices and profits, both of length n, where each index i represents an item in a store with price prices[i] and profit profits[i].

Your task is to select exactly three items with indices i, j, and k that satisfy the following conditions:

• The indices must be in increasing order: i < j < k
• The prices must be in strictly increasing order: prices[i] < prices[j] < prices[k]

When you select three items meeting these conditions, your total profit is calculated as profits[i] + profits[j] + profits[k].

The goal is to find the maximum possible profit from selecting three items that satisfy both conditions. If it's impossible to find three items meeting the requirements, return -1.

For example, if you have items where the prices form an increasing sequence at certain positions, you want to pick the three positions that not only have increasing prices but also give you the highest combined profit values.

Intuition

When we need to find three items with specific ordering constraints, a natural approach is to fix one element and search for the other two. Since we need prices[i] < prices[j] < prices[k], the middle element j acts as a pivot point - it must be greater than something on its left and smaller than something on its right.

By fixing the middle element j, we can break down the problem into two independent subproblems:

1. Find the best item to the left of j with a smaller price
2. Find the best item to the right of j with a larger price

For each position j, we want to maximize profits[i] + profits[j] + profits[k]. Since profits[j] is fixed when we choose j, we need to maximize profits[i] among all valid items on the left and maximize profits[k] among all valid items on the right.

The key insight is that for each middle position j:

• We scan all positions i < j and track the maximum profit among items with prices[i] < prices[j]
• We scan all positions k > j and track the maximum profit among items with prices[k] > prices[j]

If we can find at least one valid item on both sides (meaning both left and right are non-zero), we have a valid triplet. We calculate the total profit as left + profits[j] + right and update our answer if this is better than what we've found so far.

This approach ensures we check all possible middle elements and for each one, we greedily select the best possible left and right elements, guaranteeing we find the optimal solution.

Learn more about Segment Tree patterns.

Solution Approach

The solution implements the enumerate-the-middle-element strategy. Here's how the algorithm works:

1. Initialize the answer: Start with ans = -1 to handle the case where no valid triplet exists.

2. Enumerate the middle element: Loop through each index j from 0 to n-1, treating profits[j] as the middle element of our triplet. We store profits[j] as x for convenience.

3. Find the best left element: For each middle position j:

   • Initialize left = 0 to track the maximum profit on the left
   • Iterate through all indices i from 0 to j-1
   • For each i, check if prices[i] < prices[j]
   • If true and profits[i] > left, update left = profits[i]
   • After this loop, left contains the maximum profit among all valid left elements

4. Find the best right element: Similarly for the right side:

   • Initialize right = 0 to track the maximum profit on the right
   • Iterate through all indices k from j+1 to n-1
   • For each k, check if prices[j] < prices[k]
   • If true and profits[k] > right, update right = profits[k]
   • After this loop, right contains the maximum profit among all valid right elements

5. Update the answer: If both left and right are non-zero (meaning we found valid elements on both sides):

   • Calculate the total profit as left + x + right where x is profits[j]
   • Update ans = max(ans, left + x + right)

6. Return the result: After checking all possible middle elements, return ans.

The time complexity is O(n²) since for each of the n middle elements, we scan through potentially all other elements to find the best left and right values. The space complexity is O(1) as we only use a constant amount of extra space for variables.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Example Input:

• prices = [10, 20, 15, 30, 25]
• profits = [5, 3, 7, 2, 8]

We need to find three items with indices i < j < k where prices[i] < prices[j] < prices[k].

Step-by-step execution:

When j = 0 (price=10, profit=5):

• Left side: No elements exist before index 0, so left = 0
• Right side: Check indices 1-4
  • Index 1: price=20 > 10 ✓, profit=3, so right = 3
  • Index 2: price=15 > 10 ✓, profit=7 > 3, so right = 7
  • Index 3: price=30 > 10 ✓, profit=2 < 7, keep right = 7
  • Index 4: price=25 > 10 ✓, profit=8 > 7, so right = 8
• Since left = 0, no valid triplet exists with j=0 as middle

When j = 1 (price=20, profit=3):

• Left side: Check index 0
  • Index 0: price=10 < 20 ✓, profit=5, so left = 5
• Right side: Check indices 2-4
  • Index 2: price=15 < 20 ✗, skip
  • Index 3: price=30 > 20 ✓, profit=2, so right = 2
  • Index 4: price=25 > 20 ✓, profit=8 > 2, so right = 8
• Valid triplet found! Total = 5 + 3 + 8 = 16
• Update ans = 16

When j = 2 (price=15, profit=7):

• Left side: Check indices 0-1
  • Index 0: price=10 < 15 ✓, profit=5, so left = 5
  • Index 1: price=20 > 15 ✗, skip
• Right side: Check indices 3-4
  • Index 3: price=30 > 15 ✓, profit=2, so right = 2
  • Index 4: price=25 > 15 ✓, profit=8 > 2, so right = 8
• Valid triplet found! Total = 5 + 7 + 8 = 20
• Update ans = 20

When j = 3 (price=30, profit=2):

• Left side: Check indices 0-2
  • Index 0: price=10 < 30 ✓, profit=5, so left = 5
  • Index 1: price=20 < 30 ✓, profit=3 < 5, keep left = 5
  • Index 2: price=15 < 30 ✓, profit=7 > 5, so left = 7
• Right side: Check index 4
  • Index 4: price=25 < 30 ✗, skip
• Right side has no valid elements, so right = 0
• No valid triplet with j=3 as middle

When j = 4 (price=25, profit=8):

• Left side: Check indices 0-3
  • Index 0: price=10 < 25 ✓, profit=5, so left = 5
  • Index 1: price=20 < 25 ✓, profit=3 < 5, keep left = 5
  • Index 2: price=15 < 25 ✓, profit=7 > 5, so left = 7
  • Index 3: price=30 > 25 ✗, skip
• Right side: No elements after index 4, so right = 0
• No valid triplet with j=4 as middle

Final Result: The maximum profit is 20, achieved by selecting items at indices (0, 2, 4) with prices (10, 15, 25) and profits (5, 7, 8).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm uses a main loop that iterates through each element j in the profits array (n iterations). For each position j, it performs:

• A loop from index 0 to j-1 to find the maximum profit on the left side (up to j iterations)
• A loop from index j+1 to n-1 to find the maximum profit on the right side (up to n-j-1 iterations)

For each j, the total work is approximately j + (n-j-1) = n-1 operations. Since this happens for all n positions, the total time complexity is O(n × n) = O(n²).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• Variable n to store the array length
• Variable ans to track the maximum profit
• Variables j and x for the main loop
• Variables left and right to store intermediate results
• Loop variables i and k

All these variables use constant space regardless of the input size, resulting in O(1) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Initialization of Maximum Values

A common mistake is initializing max_left_profit and max_right_profit with -1 or negative infinity instead of 0. This can lead to incorrect results when no valid left or right element exists.

Incorrect approach:

max_left_profit = -1  # Wrong!
max_right_profit = -1  # Wrong!

Why it's wrong: If we initialize with -1 and no valid element exists on one side, we might still calculate a sum using -1, leading to an incorrect total that's less than it should be. The check if max_left_profit and max_right_profit: would also incorrectly pass since -1 is truthy.

Correct approach:

max_left_profit = 0  # Correct
max_right_profit = 0  # Correct

2. Using Wrong Comparison for Updating Maximum Profits

Another pitfall is using <= instead of < when updating the maximum profit values, or forgetting to check if the new profit is actually better.

Incorrect approach:

# Wrong: accepts equal profits without checking if it's actually better
if prices[i] < prices[j]:
    max_left_profit = profits[i]  # Always updates, not checking maximum

Correct approach:

if prices[i] < prices[j] and profits[i] > max_left_profit:
    max_left_profit = profits[i]

3. Confusing Price and Profit Comparisons

A subtle but critical mistake is mixing up which array to use for comparisons. Prices determine validity, while profits determine optimality.

Incorrect approach:

# Wrong: comparing profits instead of prices for validity
if profits[i] < profits[j] and profits[i] > max_left_profit:
    max_left_profit = profits[i]

Correct approach:

# Prices for validity check, profits for optimization
if prices[i] < prices[j] and profits[i] > max_left_profit:
    max_left_profit = profits[i]

4. Edge Case: All Zeros in Profits Array

If the profits array contains zeros, the condition if max_left_profit and max_right_profit: would fail even if valid non-zero profit items exist at position j.

Better approach for handling zeros:

# Instead of relying on truthiness, explicitly check if valid elements were found
if max_left_profit > 0 and max_right_profit > 0:
    max_profit_sum = max(max_profit_sum, 
                       max_left_profit + current_profit + max_right_profit)
# Or track whether valid elements were found separately
left_found = False
right_found = False
for i in range(j):
    if prices[i] < prices[j]:
        left_found = True
        max_left_profit = max(max_left_profit, profits[i])

However, this depends on whether the problem allows zero or negative profits. The original solution assumes all profits are positive based on the check logic.