We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Profitable Triplets With Increasing Prices I

Number: 3187

Difficulty: Medium

Paid? Yes

Companies: IBM

Problem Description

Given two 0-indexed arrays prices and profits of the same length, each representing an item’s price and its profit, select three items with indices i, j, and k (with i < j < k) such that prices[i] < prices[j] < prices[k]. The profit from picking a triplet is the sum profits[i] + profits[j] + profits[k]. Return the maximum achievable profit from any valid triplet, or -1 if no such triplet exists.

Key Insights

  • We must enforce both the ordering of indices (i < j < k) and strictly increasing prices (prices[i] < prices[j] < prices[k]).
  • For each potential middle item j, the optimal left candidate is one with the highest profit among all indices i < j that have prices lower than prices[j].
  • Similarly, for the middle item j, the optimal right candidate is one with the highest profit among all indices k > j that have prices greater than prices[j].
  • A brute-force method using two nested loops to compute left and right best candidates is acceptable given n <= 2000 (O(n²) time).
  • More advanced solutions can use binary indexed trees or segment trees for efficient range queries; however, for the given constraints the simpler approach is straightforward and sufficient.

Space and Time Complexity

Time Complexity: O(n²), where n is the number of items, as we scan left and right for each potential middle index. Space Complexity: O(n), for storing the left and right helper arrays.

Solution

The solution involves iterating over each possible middle index j (ranging from 1 to n-2). For each j, perform two scans:

  1. For indices to the left of j (i.e., 0 to j-1), check if prices[i] is less than prices[j] and record the maximum profit among them.
  2. For indices to the right of j (i.e., j+1 to n-1), check if prices[k] is greater than prices[j] and record the maximum profit among them. If both a left candidate and a right candidate exist for j, compute the sum: left_candidate_profit + profits[j] + right_candidate_profit and update the answer accordingly. Return the maximum sum found, or -1 if no valid triplet exists.

This approach uses two auxiliary arrays (or variables computed on the fly) to store the best candidate profits for the left and right of each middle item.

Code Solutions

# Python Solution
def maximumProfitableTriplets(prices, profits):
    n = len(prices)
    # Initialize arrays to store best profit candidate for left and right of each index
    left_best = [-1] * n
    right_best = [-1] * n

    # Compute best profit for left candidate for each middle index j
    for j in range(1, n):
        max_profit = -1
        for i in range(j):
            if prices[i] < prices[j]:
                # Update max_profit if the current candidate provides more profit
                max_profit = max(max_profit, profits[i])
        left_best[j] = max_profit

    # Compute best profit for right candidate for each middle index j
    for j in range(n - 1):
        max_profit = -1
        for k in range(j + 1, n):
            if prices[k] > prices[j]:
                max_profit = max(max_profit, profits[k])
        right_best[j] = max_profit

    max_total = -1
    # Consider each index j as the middle candidate in the triplet.
    for j in range(1, n - 1):
        if left_best[j] != -1 and right_best[j] != -1:
            total = left_best[j] + profits[j] + right_best[j]
            max_total = max(max_total, total)
    return max_total

# Example usage:
prices = [10, 2, 3, 4]
profits = [100, 2, 7, 10]
print(maximumProfitableTriplets(prices, profits))  # Expected output: 19
← Back to All Questions