Maximum Value of an Ordered Triplet I
EasyAsked by:
34 views
Topics:
Arrays
You are given a 0-indexed integer array nums.
Return the maximum value over all triplets of indices (i, j, k) such that i < j < k. If all such triplets have a negative value, return 0.
The value of a triplet of indices (i, j, k) is equal to (nums[i] - nums[j]) * nums[k].
Example 1:
Input: nums = [12,6,1,2,7] Output: 77 Explanation: The value of the triplet (0, 2, 4) is (nums[0] - nums[2]) * nums[4] = 77. It can be shown that there are no ordered triplets of indices with a value greater than 77.
Example 2:
Input: nums = [1,10,3,4,19] Output: 133 Explanation: The value of the triplet (1, 2, 4) is (nums[1] - nums[2]) * nums[4] = 133. It can be shown that there are no ordered triplets of indices with a value greater than 133.
Example 3:
Input: nums = [1,2,3] Output: 0 Explanation: The only ordered triplet of indices (0, 1, 2) has a negative value of (nums[0] - nums[1]) * nums[2] = -3. Hence, the answer would be 0.
Constraints:
3 <= nums.length <= 1001 <= nums[i] <= 106
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 numbers in the input array?
- Can the input array be empty, or contain fewer than three elements?
- If no such triplet exists where nums[i] * nums[j] * nums[k] > 0, what value should I return?
- Are duplicate values allowed within the input array, and if so, how should they be handled in forming the triplet?
- Can the input array contain negative numbers?
Brute Force Solution
Approach
The goal is to find the biggest value we can make by picking three numbers in a specific order and doing some math with them. A brute force method means we're going to try every possible combination of three numbers to see which one gives us the largest result.
Here's how the algorithm would work step-by-step:
- Look at the very first number in the group.
- Pair this first number with every other number that comes after it in the group.
- For each of these pairs, pick every number that comes after both of them.
- For each combination of three numbers, calculate the value based on the specific mathematical formula.
- Keep track of the biggest value you've calculated so far.
- Repeat this process, starting with the second number in the group as the first number, and do it again until you've tried every number as the first number.
- After checking all possible combinations of three numbers, the biggest value you kept track of is your answer.
Code Implementation
def maximum_value_of_an_ordered_triplet(numbers):
maximum_value = 0
list_length = len(numbers)
for first_element_index in range(list_length):
# Iterate through each element as the first element.
for second_element_index in range(first_element_index + 1, list_length):
for third_element_index in range(second_element_index + 1, list_length):
# Ensure indices are in increasing order.
current_value = (numbers[first_element_index] - numbers[second_element_index]) * numbers[third_element_index]
maximum_value = max(maximum_value, current_value)
# The largest triplet value is returned.
return maximum_valueBig(O) Analysis
Time Complexity
O(n^3) – The algorithm iterates through all possible triplets (i, j, k) in the input array of size n, where i < j < k. The outermost loop selects the first element (nums[i]), which runs n times. The second loop selects the second element (nums[j]) after the first, running approximately n times. The innermost loop selects the third element (nums[k]) after the second, again running approximately n times. Therefore, the total number of operations is proportional to n * n * n, which simplifies to O(n^3).
Space Complexity
O(1) – The provided brute force algorithm iterates through all possible triplets within the input array but does not use any auxiliary data structures that scale with the input size. It only maintains a constant number of variables to keep track of the current maximum value and loop indices. Therefore, the space complexity is constant, independent of the input size N (where N is the number of elements in the array).
Optimal Solution
Approach
The key is to find the maximum value efficiently by keeping track of the largest values seen so far. We'll scan the sequence of numbers and, at each position, try to maximize the value of the ordered triplet using the best values found before and after that position. This avoids checking every single combination.
Here's how the algorithm would work step-by-step:
- Go through the list of numbers from the beginning to the end.
- As you go, remember the biggest number you've seen so far before the current number.
- Also, for each number, look at all the numbers to the right of it and find the biggest one among those.
- For each number in the original sequence, use it along with the biggest number to its left, and the biggest number to its right to calculate the value of our special formula.
- Keep track of the largest value you've calculated using that formula as you move through the list.
- Once you've checked every number, the largest value you tracked is your answer.
Code Implementation
def maximum_value_of_ordered_triplet(numbers) -> int:
list_length = len(numbers)
maximum_value = 0
for i in range(list_length):
for j in range(i + 1, list_length):
for k in range(j + 1, list_length):
current_value = (numbers[i] - numbers[j]) * numbers[k]
maximum_value = max(maximum_value, current_value)
return maximum_value
def maximum_triplet_value_optimized(numbers):
list_length = len(numbers)
if list_length < 3:
return 0
max_value = 0
prefix_max = [0] * list_length
suffix_max = [0] * list_length
prefix_max[0] = numbers[0]
# We need max value to the left for each element.
for i in range(1, list_length):
prefix_max[i] = max(prefix_max[i - 1], numbers[i])
suffix_max[list_length - 1] = numbers[list_length - 1]
# We need max value to the right for each element.
for i in range(list_length - 2, -1, -1):
suffix_max[i] = max(suffix_max[i + 1], numbers[i])
for j in range(1, list_length - 1):
current_value = (prefix_max[j - 1] - numbers[j]) * suffix_max[j + 1]
max_value = max(max_value, current_value)
return max_value
def maximum_triplet_value_best(numbers):
list_length = len(numbers)
if list_length < 3:
return 0
max_value = 0
first_max = numbers[0]
# We track the largest number to the left
for j in range(1, list_length - 1):
for k in range(j + 1, list_length):
current_value = (first_max - numbers[j]) * numbers[k]
max_value = max(max_value, current_value)
first_max = max(first_max, numbers[j])
# Update the largest number
return max_value
def maximum_triplet_value_optimal(numbers):
list_length = len(numbers)
if list_length < 3:
return 0
maximum_value = 0
max_left = numbers[0]
# Stores max value to the left
for j in range(1, list_length - 1):
max_right = 0
# Find max value to the right of j
for k in range(j + 1, list_length):
max_right = max(max_right, numbers[k])
current_value = (max_left - numbers[j]) * max_right
maximum_value = max(maximum_value, current_value)
max_left = max(max_left, numbers[j])
# Update max value to the left
return maximum_valueBig(O) Analysis
Time Complexity
O(n²) – The algorithm iterates through the input array nums of size n. For each element nums[i], it finds the maximum element to its left in O(1) time, assuming it's precomputed or tracked on the fly. Crucially, for each element nums[i], it also iterates through the remaining elements to its right to find the maximum element on the right. This nested iteration results in a cost proportional to the number of pairs (i, j) where j > i. Therefore, the time complexity is dominated by this nested loop which calculates the maximum value on the right for each element, leading to approximately n * (n-1)/2 operations, simplifying to O(n²).
Space Complexity
O(N) – The algorithm uses an auxiliary array to store the maximum values to the right of each element. This array, let's call it rightMax, has the same size as the input array nums, which we define as N. Therefore, the space required for rightMax is directly proportional to the size of the input. Consequently, the space complexity is O(N).
Edge Cases
| Case | How to Handle |
|---|---|
| Empty input array | Return 0 immediately as no triplet exists. |
| Array size less than 3 | Return 0 since a triplet cannot be formed. |
| Array with all elements equal to 0 | Return 0 as the product will always be zero. |
| Array with all elements as negative numbers | Return 0 since any product involving only negative numbers will be negative or zero. |
| Large positive numbers that might cause integer overflow | Use long data type for intermediate calculations to avoid overflow. |
| Array with a mix of very large positive and very small negative numbers | The current approach will correctly identify the maximum product among triplets. |
| Array with only one peak in the values (one large number and the rest are significantly smaller) | The algorithm should correctly identify this peak to maximize the result. |
| Maximum size input array | The algorithm should remain efficient (O(n)) even with the maximum input size. |
Empty input array
How to Handle:
Return 0 immediately as no triplet exists.
Array size less than 3
How to Handle:
Return 0 since a triplet cannot be formed.
Array with all elements equal to 0
How to Handle:
Return 0 as the product will always be zero.
Array with all elements as negative numbers
How to Handle:
Return 0 since any product involving only negative numbers will be negative or zero.
Large positive numbers that might cause integer overflow
How to Handle:
Use long data type for intermediate calculations to avoid overflow.
Array with a mix of very large positive and very small negative numbers
How to Handle:
The current approach will correctly identify the maximum product among triplets.
Array with only one peak in the values (one large number and the rest are significantly smaller)
How to Handle:
The algorithm should correctly identify this peak to maximize the result.
Maximum size input array
How to Handle:
The algorithm should remain efficient (O(n)) even with the maximum input size.
Explore Interview QuestionsTaro 75Google Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Interview ExperiencesOpenAI Interview ExperiencesAnthropic Interview ExperiencesPerplexity Interview ExperiencesWindsurf Interview ExperiencesMistral AI Interview Experiences
