Tejav
#2874

Maximum Value of an Ordered Triplet II

Medium
ArrayPrefix Sum/MaximumSuffix Sum/MaximumDynamic Programming
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n)
Space
O(1)
O(n)
💡

Intuition

Time O(n)Space O(n)

By preprocessing prefix and suffix maximum arrays, we can efficiently find the best triplet values without needing to check every combination. This reduces the number of calculations significantly.

⚙️

Algorithm

3 steps
  1. 1Step 1: Create a prefix maximum array where prefix_max[i] is the maximum value from nums[0] to nums[i].
  2. 2Step 2: Create a suffix maximum array where suffix_max[i] is the maximum value from nums[i] to nums[n-1].
  3. 3Step 3: Iterate through each index j from 1 to n-2, and for each j, calculate the value using the prefix_max and suffix_max arrays: max_value = max(max_value, (prefix_max[j-1] - nums[j]) * suffix_max[j+1]).
solution.py14 lines
1def max_triplet_value(nums):
2    n = len(nums)
3    prefix_max = [0] * n
4    suffix_max = [0] * n
5    prefix_max[0] = nums[0]
6    for i in range(1, n):
7        prefix_max[i] = max(prefix_max[i-1], nums[i])
8    suffix_max[n-1] = nums[n-1]
9    for i in range(n-2, -1, -1):
10        suffix_max[i] = max(suffix_max[i+1], nums[i])
11    max_value = 0
12    for j in range(1, n-1):
13        max_value = max(max_value, (prefix_max[j-1] - nums[j]) * suffix_max[j+1])
14    return max_value
ℹ

Complexity note: The time complexity is linear because we only pass through the array a few times (for prefix and suffix calculations), and the space complexity is linear due to the additional arrays used.

  • 1The order of indices matters, which is why we need to maintain the conditions i < j < k.
  • 2Using prefix and suffix arrays allows us to efficiently compute maximum values without redundant calculations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.