medium Maximum Profitable Triplets With Increasing Prices I

Problem Statement

You are given two 0-indexed arrays, prices and profits, both 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].

You have to select three items with the following condition:

• prices[i] < prices[j] < prices[k] where i < j < k.
• If such a selection is possible, calculate the total profit, which is profits[i] + profits[j] + profits[k].

Return the maximum possible profit from this selection. If it's not possible to select three items that satisfy these conditions, return -1.

Examples

Example 1:

• Input: prices = [3, 1, 4, 6, 2], profits = [5, 2, 8, 10, 3]
• Expected Output: 23
• Explanation: The selected triplet is (3, 4, 6) with indices 0, 2, 3. The corresponding profits are 5 + 8 + 10 = 23.

Example 2:

• Input: prices = [2, 7, 1, 5, 8, 10], profits = [3, 9, 1, 4, 7, 6]
• Expected Output: 22
• Explanation: The selected triplet is (7, 8, 10) with indices 1, 4, 5. The corresponding profits are 9 + 7 + 6 = 22.

Example 3:

• Input: prices = [9, 8, 7, 6, 5], profits = [10, 9, 8, 7, 6]
• Expected Output: -1
• Explanation: It is not possible to select three items such that their prices strictly increase.

Constraints:

• 3 <= prices.length == profits.length <= 2000
• 1 <= prices[i] <= 10⁶
• 1 <= profits[i] <= 10⁶

Solution

To solve this problem, the approach leverages the Binary Indexed Tree (BIT) to efficiently track and query the maximum profits that can be obtained from items with increasing prices. The idea is to calculate the maximum profit for a valid triplet of items, where the prices strictly increase. The BIT helps in maintaining and retrieving the maximum profit seen so far as we traverse the list of prices twice—once from left to right and once from right to left. The solution involves calculating the maximum profit that can be achieved from the left and right segments separately, and then combining them to find the overall maximum profit for any valid triplet.

This approach works efficiently because the BIT allows us to perform both update and query operations in logarithmic time. By maintaining two separate BITs (one for the left traversal and one for the right traversal), we can effectively find the maximum profit for any valid triplet by combining the best profits found during the left and right traversals.

Step-by-Step Algorithm

1. Initialize Variables:

   • Determine the maximum value in the prices array and store it in maxPrice. This helps in setting the size of the BIT arrays.
   • Create two BIT arrays bitForMaxLeft and bitForMaxRight, both of size maxPrice + 1. These arrays will be used to store the maximum profit for different price indices during left-to-right and right-to-left traversals.
   • Create an array maxLeftProfit of the same size as the prices array to store the maximum profit that can be obtained for the left side of each item.

2. Left-to-Right Traversal:

   • Iterate Through Prices: Iterate through the prices array from left to right.
   • Calculate maxLeftProfit:
     • For each price at index i, use the getMaxProfit function to query the BIT bitForMaxLeft for the maximum profit corresponding to all prices less than prices[i].
     • Purpose of getMaxProfit: The getMaxProfit function traverses the BIT from the given price down to 0, finding the maximum profit recorded for any price index less than the current price. This allows us to find the best profit we could have obtained before the current price point, which is essential for calculating valid triplets.
   • Store maxLeftProfit: Store this value in maxLeftProfit[i]. This represents the maximum profit we could have achieved on the left side of prices[i].
   • Update BIT for Left Side:
     • Use the updateBIT function to update the BIT bitForMaxLeft with the current prices[i] and profits[i].
     • Purpose of updateBIT: The updateBIT function traverses the BIT from the current price index upwards, ensuring that the maximum profit is recorded at every index touched by the current price. This operation makes sure that any future queries for maximum profit will consider this price's profit as a potential maximum.

3. Right-to-Left Traversal:

   • Initialize maxTotalProfit to -1, which will store the maximum profit for any valid triplet found.
   • Iterate through the prices array from right to left.
   • For each price at index i, adjust the price to adjustedPrice = maxPrice - prices[i] + 1 to handle the reverse traversal in the BIT.
   • Reason for Adjusting the Price Index:
     • When traversing from right to left, we want to find the best profit for prices that are greater than the current price (to ensure increasing order in the triplet).
     • By adjusting the price using maxPrice - prices[i] + 1, we effectively "mirror" the index so that the BIT, which is designed to handle increasing indices naturally, can now handle decreasing price sequences properly during the reverse traversal. This trick allows the same BIT structure to be used in reverse order.
   • Query the BIT bitForMaxRight for the maximum profit corresponding to all prices greater than prices[i].
   • If both maxLeftProfit[i] and the profit found from the right traversal are greater than 0, update maxTotalProfit to the sum of maxLeftProfit[i], profits[i], and the right profit.
   • Update the BIT bitForMaxRight with the adjusted price and the current profit.

4. Return Result:

   • Finally, return maxTotalProfit, which holds the maximum profit for any valid triplet or -1 if no valid triplet was found.

Algorithm Walkthrough

Input: prices = [3, 1, 4, 6, 2], profits = [5, 2, 8, 10, 3]

Initialization:

• maxPrice: Find the maximum value in the prices array.
  • maxPrice = 6
• bitForMaxLeft: Initialize BIT array for left-to-right traversal.
  • bitForMaxLeft = [0, 0, 0, 0, 0, 0, 0]
• bitForMaxRight: Initialize BIT array for right-to-left traversal.
  • bitForMaxRight = [0, 0, 0, 0, 0, 0, 0]
• maxLeftProfit: Initialize array to store maximum profits from left side.
  • maxLeftProfit = [0, 0, 0, 0, 0]
• maxTotalProfit: Initialize the variable to store the result.
  • maxTotalProfit = -1

Left-to-Right Traversal:

1. Step 1 (i = 0, prices[0] = 3):

   • Query BIT: getMaxProfit(bitForMaxLeft, 2) returns 0 (no valid price less than 3).
   • Update maxLeftProfit:
     • maxLeftProfit[0] = 0
   • Update BIT: updateBIT(bitForMaxLeft, 3, 5)
     • Start with i = 3, update bitForMaxLeft[3] = max(0, 5) = 5.
     • Next i = 4 (since i = i + (i & -i)), update bitForMaxLeft[4] = max(0, 5) = 5.
     • End with i = 8 which is out of bounds.
   • Updated Arrays:
     • bitForMaxLeft = [0, 0, 0, 5, 5, 0, 0]
     • maxLeftProfit = [0, 0, 0, 0, 0]

2. Step 2 (i = 1, prices[1] = 1):

   • Query BIT: getMaxProfit(bitForMaxLeft, 0) returns 0 (no valid price less than 1).
   • Update maxLeftProfit:
     • maxLeftProfit[1] = 0
   • Update BIT: updateBIT(bitForMaxLeft, 1, 2)
     • Start with i = 1, update bitForMaxLeft[1] = max(0, 2) = 2.
     • Next i = 2, update bitForMaxLeft[2] = max(0, 2) = 2.
     • Next i = 4, update bitForMaxLeft[4] = max(5, 2) = 5 (no change).
     • End with i = 8 which is out of bounds.
   • Updated Arrays:
     • bitForMaxLeft = [0, 2, 2, 5, 5, 0, 0]
     • maxLeftProfit = [0, 0, 0, 0, 0]

3. Step 3 (i = 2, prices[2] = 4):

   • Query BIT: getMaxProfit(bitForMaxLeft, 3) returns 5 (best profit from price 3).
   • Update maxLeftProfit:
     • maxLeftProfit[2] = 5
   • Update BIT: updateBIT(bitForMaxLeft, 4, 8)
     • Start with i = 4, update bitForMaxLeft[4] = max(5, 8) = 8.
     • End with i = 8 which is out of bounds.
   • Updated Arrays:
     • bitForMaxLeft = [0, 2, 2, 5, 8, 0, 0]
     • maxLeftProfit = [0, 0, 5, 0, 0]

4. Step 4 (i = 3, prices[3] = 6):

   • Query BIT: getMaxProfit(bitForMaxLeft, 5) returns 8 (best profit from price 4).
   • Update maxLeftProfit:
     • maxLeftProfit[3] = 8
   • Update BIT: updateBIT(bitForMaxLeft, 6, 10)
     • Start with i = 6, update bitForMaxLeft[6] = max(0, 10) = 10.
     • End with i = 8 which is out of bounds.
   • Updated Arrays:
     • bitForMaxLeft = [0, 2, 2, 5, 8, 0, 10]
     • maxLeftProfit = [0, 0, 5, 8, 0]

5. Step 5 (i = 4, prices[4] = 2):

   • Query BIT: getMaxProfit(bitForMaxLeft, 1) returns 2 (best profit from price 1).
   • Update maxLeftProfit:
     • maxLeftProfit[4] = 2
   • Update BIT: updateBIT(bitForMaxLeft, 2, 3)
     • Start with i = 2, update bitForMaxLeft[2] = max(2, 3) = 3.
     • Next i = 4, update bitForMaxLeft[4] = max(8, 3) = 8 (no change).
     • End with i = 8 which is out of bounds.
   • Updated Arrays:
     • bitForMaxLeft = [0, 2, 3, 5, 8, 0, 10]
     • maxLeftProfit = [0, 0, 5, 8, 2]

Right-to-Left Traversal:

1. Step 1 (i = 4, prices[4] = 2):

   • Adjust Price: adjustedPrice = 6 - 2 + 1 = 5
   • Query BIT: getMaxProfit(bitForMaxRight, 4) returns 0 (no valid price greater than 2).
   • Update BIT: updateBIT(bitForMaxRight, 5, 3)
     • Start with i = 5, update bitForMaxRight[5] = max(0, 3) = 3.
     • End with i = 6 which is out of bounds.
   • Updated Arrays:
     • bitForMaxRight = [0, 0, 0, 0, 0, 3, 0]
     • maxTotalProfit = -1 (no update)

2. Step 2 (i = 3, prices[3] = 6):

   • Adjust Price: adjustedPrice = 6 - 6 + 1 = 1
   • Query BIT: getMaxProfit(bitForMaxRight, 0) returns 0 (no valid price greater than 6).
   • Update BIT: updateBIT(bitForMaxRight, 1, 10)
     • Start with i = 1, update bitForMaxRight[1] = max(0, 10) = 10.
     • Next i = 2, update bitForMaxRight[2] = max(0, 10) = 10.
     • Next i = 4, update bitForMaxRight[4] = max(0, 10) = 10.
     • End with i = 8 which is out of bounds.
   • Updated Arrays:
     • bitForMaxRight = [0, 10, 10, 0, 10, 3, 0]
     • maxTotalProfit = -1 (no update)

3. Step 3 (i = 2, prices[2] = 4):

   • Adjust Price: adjustedPrice = 6 - 4 + 1 = 3
   • Query BIT: getMaxProfit(bitForMaxRight, 2) returns 10 (best profit from price 6).
   • Update maxTotalProfit:
     • maxTotalProfit = max(-1, 5 + 8 + 10) = 23
   • Update BIT: updateBIT(bitForMaxRight, 3, 8)
     • Start with i = 3, update bitForMaxRight[3] = max(0, 8) = 8.
     • Next i = 4, update bitForMaxRight[4] = max(10, 8) = 10 (no change).
     • End with i = 8 which is out of bounds.
   • Updated Arrays:
     • bitForMaxRight = [0, 10, 10, 8, 10, 3, 0]
     • maxTotalProfit = 23

4. Step 4 (i = 1, prices[1] = 1):

   • Adjust Price: adjustedPrice = 6 - 1 + 1 = 6
   • Query BIT: getMaxProfit(bitForMaxRight, 5) returns 3 (best profit from price 2).
   • Update maxTotalProfit:
     • maxTotalProfit = max(23, 0 + 2 + 3) = 23 (no change)
   • Update BIT: updateBIT(bitForMaxRight, 6, 2)
     • Start with i = 6, update bitForMaxRight[6] = max(0, 2) = 2.
     • End with i = 8 which is out of bounds.
   • Updated Arrays:
     • bitForMaxRight = [0, 10, 10, 8, 10, 3, 2]
     • maxTotalProfit = 23

5. Step 5 (i = 0, prices[0] = 3):

   • Adjust Price: adjustedPrice = 6 - 3 + 1 = 4
   • Query BIT: getMaxProfit(bitForMaxRight, 3) returns 8 (best profit from price 4).
   • maxLeftProfit[0] = 0, which is not valid.

Final Output:

• Return Result: The maximum profit from the valid triplet is 23, so return 23.

Code

class Solution {

  public int maxProfit(int[] prices, int[] profits) {
    // Find the maximum price from the prices array
    int maxPrice = 0,
      n = prices.length;
    for (int price : prices) {
      maxPrice = Math.max(maxPrice, price);
    }

    // Initialize Binary Indexed Trees (BIT) for left and right max profits
    int[] bitForMaxLeft = new int[maxPrice + 1];
    int[] bitForMaxRight = new int[maxPrice + 1];

    // Array to store max profit for the left side of each price
    int[] maxLeftProfit = new int[n];

    // Calculate maxLeftProfit using BIT for each price
    for (int i = 0; i < n; i++) {
      maxLeftProfit[i] = getMaxProfit(bitForMaxLeft, prices[i] - 1);
      updateBIT(bitForMaxLeft, prices[i], profits[i]);
    }

    // Initialize the result as -1 indicating no valid triplet found yet
    int maxTotalProfit = -1;

    // Traverse the prices array from right to left to calculate the result
    for (int i = n - 1; i >= 0; i--) {
      int adjustedPrice = maxPrice - prices[i] + 1;
      int maxRightProfit = getMaxProfit(bitForMaxRight, adjustedPrice - 1);

      // Update maxTotalProfit if both maxLeftProfit and maxRightProfit are greater than 0
      if (maxLeftProfit[i] > 0 && maxRightProfit > 0) {
        maxTotalProfit = Math.max(
          maxTotalProfit,
          maxLeftProfit[i] + profits[i] + maxRightProfit
        );
      }
      updateBIT(bitForMaxRight, adjustedPrice, profits[i]);
    }

    return maxTotalProfit;
  }

  // Update BIT with the new profit value at the given price index
  private void updateBIT(int[] bit, int priceIndex, int profit) {
    for (int i = priceIndex; i > 0 && i < bit.length; i = i + (i & -i)) {
      bit[i] = Math.max(bit[i], profit);
    }
  }

  // Get the maximum profit value from BIT for a given price index
  private int getMaxProfit(int[] bit, int priceIndex) {
    int maxProfit = 0;
    for (int i = priceIndex; i > 0; i = i - (i & -i)) {
      maxProfit = Math.max(bit[i], maxProfit);
    }
    return maxProfit;
  }

  // Main method to test the examples
  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[] prices1 = { 3, 1, 4, 6, 2 };
    int[] profits1 = { 5, 2, 8, 10, 3 };
    System.out.println(
      "Example 1 Result: " + solution.maxProfit(prices1, profits1)
    );

    // Example 2
    int[] prices2 = { 2, 7, 1, 5, 8, 10 };
    int[] profits2 = { 3, 9, 1, 4, 7, 6 };
    System.out.println(
      "Example 2 Result: " + solution.maxProfit(prices2, profits2)
    );

    // Example 3
    int[] prices3 = { 9, 8, 7, 6, 5 };
    int[] profits3 = { 10, 9, 8, 7, 6 };
    System.out.println(
      "Example 3 Result: " + solution.maxProfit(prices3, profits3)
    );
  }
}

Complexity Analysis

Time Complexity

• The code primarily involves two operations on the Binary Indexed Tree (BIT): updateBIT and getMaxProfit.
• The updateBIT operation takes time, where maxPrice is the maximum value in the prices array.
• The getMaxProfit operation also takes time.
• The solution iterates over the prices array twice, each time performing these operations. Therefore, the overall time complexity is , where n is the length of the prices array.

Space Complexity

• The space complexity is dominated by the space needed for the two BIT arrays (bitForMaxLeft and bitForMaxRight), which have a size of maxPrice + 1.
• Additionally, an array of size n is used for storing maxLeftProfit.
• Thus, the total space complexity is .