Maximum Increasing Triplet Value

Medium

Asked by:

15 views

Topics:

Arrays

You are given a 0-indexed integer array nums of length n.

A triplet of indices (i, j, k) is a increasing triplet if i < j < k and nums[i] < nums[j] < nums[k].

The value of a triplet (i, j, k) is (nums[i] - nums[j]) * nums[k].

Return the maximum value of all possible increasing triplets. If no increasing triplet exists, return 0.

Example 1:

Input: nums = [1,3,2,4,5]
Output: 6
Explanation: The triplets with value greater than 0 are:
- (0, 1, 2) -> (1 - 3) * 2 = -4
- (0, 1, 3) -> (1 - 3) * 4 = -8
- (0, 1, 4) -> (1 - 3) * 5 = -10
- (0, 2, 3) -> (1 - 2) * 4 = -4
- (0, 2, 4) -> (1 - 2) * 5 = -5
- (1, 2, 3) -> (3 - 2) * 4 = 4
- (1, 2, 4) -> (3 - 2) * 5 = 5
- (2, 3, 4) -> (2 - 4) * 5 = -10
Triplet (1, 2, 4) has the maximum value, which is 5.

Example 2:

Input: nums = [1000000,1,1000000]
Output: 0
Explanation: The only possible triplet is (0, 1, 2) but 1000000 > 1 so it is not an increasing triplet.

Example 3:

Input: nums = [3,1,5,11,2]
Output: 0
Explanation: The increasing triplets are:
- (0, 2, 3) -> (3 - 5) * 11 = -22
- (1, 2, 3) -> (1 - 5) * 11 = -44
- (1, 4, 3) -> (1 - 2) * 11 = -11
The triplet with the maximum value is (0, 2, 3). Since all values are negative, return 0.

Constraints:

3 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the `nums` array? Can they be negative, zero, or very large?
What is the maximum size of the `nums` array? I'd like to understand the scale of the input.
If there are multiple increasing triplets, should I return the maximum product amongst all such triplets, or is there another criterion for selecting the triplet?
Are duplicate values allowed in the `nums` array, and if so, how should they be handled when determining an increasing triplet?
If no increasing triplet exists, should I return 0, or is there any other specific value I should return in that case?

Brute Force Solution

Approach

The brute force method for this problem is all about checking every possible group of three numbers. We need to go through all combinations to find the best triplet that meets our conditions.

Here's how the algorithm would work step-by-step:

Take the first number in the list.
For that first number, look at every number that comes after it in the list.
If you find a number that's bigger than the first one, hold onto it as a potential second number.
For that potential second number, look at every number that comes after it in the list.
If you find a number that's bigger than the second number, you've found a potential third number.
If all three numbers are increasing, calculate their product.
Remember the highest product you've found so far.
Keep trying all possible combinations of first, second, and third numbers by repeating the steps above.
Once you've tried every possible combination, the highest product you remembered is your answer.

Code Implementation

def maximum_increasing_triplet_value_brute_force(numbers):
    max_product = 0
    list_length = len(numbers)

    for first_index in range(list_length):
        first_number = numbers[first_index]
        for second_index in range(first_index + 1, list_length):
            second_number = numbers[second_index]

            # Ensure second number is greater than the first
            if second_number > first_number:
                for third_index in range(second_index + 1, list_length):
                    third_number = numbers[third_index]

                    # Ensure third number is greater than the second
                    if third_number > second_number:

                        # Update the maximum product if needed
                        product = first_number * second_number * third_number
                        max_product = max(max_product, product)

    return max_product

Big(O) Analysis

Time Complexity

O(n^3) – The brute force approach iterates through all possible triplets in the input array of size n. For each element, the algorithm searches for a second element greater than the first, and then for each of those pairs, it searches for a third element greater than the second. This means that for each of the n elements, we potentially iterate through the remaining elements twice in a nested fashion resulting in approximately n * n * n operations in the worst case. Therefore, the time complexity is O(n^3).

Space Complexity

O(1) – The brute force method, as described, iterates through the input list using nested loops to find the maximum increasing triplet value. It only utilizes a few variables to store the current potential triplet values and the maximum product found so far. Since the number of these variables does not depend on the input size N (the number of elements in the list), the auxiliary space required remains constant regardless of the input. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The goal is to find three numbers in the given list such that they increase in value as they appear, and maximize the product of these three numbers. Instead of checking all possible combinations of three numbers, we efficiently keep track of the best potential first and second numbers as we go through the list.

Here's how the algorithm would work step-by-step:

Keep track of the smallest number seen so far as we move through the list. This will be our potential first number of the triplet.
Keep track of the best second number we've found so far. This is the largest number we've seen that is still smaller than any number that has appeared later in the list.
For each number in the list, check if it is greater than our best second number. If it is, then we have found a potential third number that, combined with our best first and second numbers, forms an increasing triplet.
If a larger number is found we calculate the product of the potential triplet, if its larger than our current maximum triplet product we update the largest product seen so far.
Continue to update smallest and best second number as you iterate through the list
The largest value stored will be the result we return.

Code Implementation

def maximum_increasing_triplet_value(numbers):
    smallest_number = float('inf')
    best_second_number = 0
    maximum_triplet_value = 0

    for number in numbers:
        if number > best_second_number:
            # Found a potential third number.
            maximum_triplet_value = max(maximum_triplet_value, smallest_number * best_second_number * number)

        if number > smallest_number and number < best_second_number:
            # We found a better middle value
            best_second_number = number

        if number < smallest_number:
            # Keep track of the smallest number
            smallest_number = number

    return maximum_triplet_value

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input list of size n only once. Inside the loop, it performs constant time operations: updating the smallest number seen so far, updating the best second number, and checking if the current number can form an increasing triplet. Therefore, the time complexity is directly proportional to the size of the input list, resulting in O(n).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It stores a few variables to keep track of the smallest number seen so far, the best second number found so far, and the current maximum triplet product. The number of these variables does not depend on the size N of the input list, so the auxiliary space is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as there can be no triplet.
Array size less than 3	Return 0 as a triplet requires at least three elements.
Array with all elements being equal	The algorithm should return 0, as no increasing triplet can be formed.
Array with all elements in descending order	The algorithm should return 0, as no increasing triplet can be formed.
Array containing zero(s)	Zeros can be included and may affect the final product, depending on other numbers present, which the algorithm handles correctly.
Array containing negative numbers	The algorithm needs to consider that the product of three negative numbers might be larger than other triplets.
Integer overflow in multiplication	Use long data type to store the product to avoid integer overflow.
Large input array	Ensure algorithm's time complexity doesn't exceed O(n^2) or the execution time will be excessive.

Null or empty input array

How to Handle:

Return 0 immediately as there can be no triplet.

Array size less than 3

How to Handle:

Return 0 as a triplet requires at least three elements.

Array with all elements being equal

How to Handle:

The algorithm should return 0, as no increasing triplet can be formed.

Array with all elements in descending order

How to Handle:

The algorithm should return 0, as no increasing triplet can be formed.

Array containing zero(s)

How to Handle:

Zeros can be included and may affect the final product, depending on other numbers present, which the algorithm handles correctly.

Array containing negative numbers

How to Handle:

The algorithm needs to consider that the product of three negative numbers might be larger than other triplets.

Integer overflow in multiplication

How to Handle:

Use long data type to store the product to avoid integer overflow.

Large input array

How to Handle:

Ensure algorithm's time complexity doesn't exceed O(n^2) or the execution time will be excessive.