How hard is LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II?

LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II is rated Hard on LeetCode.

What is the time complexity of LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II?

The Python solution on this page runs in O(n \times \log M).

What is the space complexity of LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II?

The Python solution on this page uses O(M) auxiliary space.

What topics does LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II cover?

LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II is tagged Binary Indexed Tree, Segment Tree and Array on LeetCode.

Maximum Profitable Triplets With Increasing Prices II — LeetCode 2921 Python Solution

HardLeetCode PremiumBinary Indexed TreeSegment TreeArray

Problem: #2921
Reading time: 7 min
Source: leetcode.com

The problem

Given the 0-indexed arrays prices and profits of length n. There are n items in an store where the ith item has a price of prices[i] and a profit of profits[i].

Example

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.

Python solution

Python

class BinaryIndexedTree:
    def __init__(self, n: int):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, v: int):
        while x <= self.n:
            self.c[x] = max(self.c[x], v)
            x += x & -x

    def query(self, x: int) -> int:
        mx = 0
        while x:
            mx = max(mx, self.c[x])
            x -= x & -x
        return mx


class Solution:
    def maxProfit(self, prices: List[int], profits: List[int]) -> int:
        n = len(prices)
        left = [0] * n
        right = [0] * n

        m = max(prices)
        tree1 = BinaryIndexedTree(m + 1)
        tree2 = BinaryIndexedTree(m + 1)

        for i, x in enumerate(prices):
            left[i] = tree1.query(x - 1)
            tree1.update(x, profits[i])
        for i in range(n - 1, -1, -1):
            x = m + 1 - prices[i]
            right[i] = tree2.query(x - 1)
            tree2.update(x, profits[i])

        return max(
            (l + x + r for l, x, r in zip(left, profits, right) if l and r), default=-1
        )

Complexity

Measure	Complexity
Time	O(n \times \log M)
Space	O(M) auxiliary

Frequently asked questions

How hard is LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II?: LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II is rated Hard on LeetCode.
What is the time complexity of LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II?: The Python solution on this page runs in O(n \times \log M).
What is the space complexity of LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II?: The Python solution on this page uses O(M) auxiliary space.
What topics does LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II cover?: LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II is tagged Binary Indexed Tree, Segment Tree and Array on LeetCode.
Is LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II a premium problem?: Yes. LeetCode 2921. Maximum Profitable Triplets With Increasing Prices II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.