We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Increasing Triplet Value

Number: 3378

Difficulty: Medium

Paid? Yes

Companies: Uber

Problem Description

Given an array nums, find the maximum value of a triplet (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. The triplet’s value is defined as nums[i] - nums[j] + nums[k]. There is a guarantee that at least one valid triplet exists.

Key Insights

  • For a fixed middle index j, the triplet value becomes (nums[i] + nums[k]) - nums[j]. Thus, to maximize it you want:
    • The largest possible nums[i] from indices before j with the condition nums[i] < nums[j].
    • The largest possible nums[k] from indices after j with the condition nums[k] > nums[j].
  • You cannot simply choose the maximum from the left or right segments; the chosen candidate must satisfy the strict inequality relative to nums[j].
  • For the right side, a suffix maximum array can be built, but you need to ensure that the candidate is strictly greater than nums[j].
  • For the left side, a data structure (like a Fenwick Tree or Balanced BST) can help perform queries to find the maximum element less than the current nums[j] among all previous indices.
  • Coordinate compression is useful because nums[i] can be as large as 10^9, making direct indexing infeasible.

Space and Time Complexity

Time Complexity: O(n log n) – The algorithm iterates over the array and uses logarithmic time queries/updates for maintaining and querying the left candidates. Space Complexity: O(n) – To store the Fenwick tree (or similar data structure) and additional arrays.

Solution

The solution iterates through the array while keeping track of two components for every potential middle index j:

  1. The best candidate from the left (i), which is the maximum value among all previous nums[i] that are strictly less than nums[j]. This is maintained with a Fenwick tree (after coordinate compressing the array) that supports range maximum queries.
  2. The best candidate from the right (k), which can be precomputed using a suffix maximum array. For every index j, the maximum candidate for k is the maximum element in nums[j+1…n-1] that is strictly greater than nums[j].

For every index j (as the middle element), if both a valid left candidate and a valid right candidate exist, compute candidate value = left_candidate + right_candidate - nums[j] and update the answer if it is greater than the current maximum.

Key implementation details:

  • Use coordinate compression to map the values in nums to a smaller range [1, M] since the Fenwick tree must be used on indices.
  • The Fenwick tree is updated with each new value as you move from left to right.
  • Build a suffix maximum array in one pass from the right.

This method ensures that each query and update is performed in O(log n) time, resulting in an overall time complexity of O(n log n).

Code Solutions

# Python solution using Fenwick Tree for range maximum queries and suffix maximum array
class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)
    
    def update(self, index, value):
        # index is 1-based in Fenwick tree
        while index <= self.size:
            self.tree[index] = max(self.tree[index], value)
            index += index & (-index)
    
    def query(self, index):
        # query max for indices in [1, index]
        result = 0
        while index > 0:
            result = max(result, self.tree[index])
            index -= index & (-index)
        return result

def maximumTripletValue(nums):
    n = len(nums)
    # Build suffix maximum array: right_max[i] = max(nums[i+1 ... n-1])
    right_max = [0] * n
    right_max[n - 1] = -1  # no valid candidate for last index
    for i in range(n - 2, -1, -1):
        right_max[i] = max(nums[i + 1], right_max[i + 1])
    
    # Coordinate compression
    sorted_vals = sorted(set(nums))
    comp = {val: i + 1 for i, val in enumerate(sorted_vals)}  # 1-indexed

    fenw = FenwickTree(len(comp))
    max_triplet = float('-inf')
    
    # Iterate for potential middle element j
    for j in range(n):
        # For left candidate: query maximum value among indices with nums[i] < nums[j]
        # using compressed value (comp[nums[j]] - 1)
        best_left = fenw.query(comp[nums[j]] - 1)
        
        # For right candidate: ensure that the suffix maximum is greater than nums[j]
        best_right = right_max[j] if right_max[j] > nums[j] else -1
        
        if best_left > 0 and best_right > nums[j]:
            candidate_value = best_left + best_right - nums[j]
            max_triplet = max(max_triplet, candidate_value)
        
        # Update Fenwick Tree with current nums[j]
        fenw.update(comp[nums[j]], nums[j])
    
    return max_triplet

# Example usage:
print(maximumTripletValue([1,5,3,6]))  # Expected output: 4
← Back to All Questions