algoadvance

Leetcode 2873. Maximum Value of an Ordered Triplet I

Problem Statement

You are given an integer array nums. The ordered triplet (a, b, c) is a valid ordered triplet if the following conditions are satisfied:

  1. 0 <= a < b < c < nums.length
  2. nums[a] < nums[b] < nums[c]

Return the maximum value of (nums[a] + nums[b] + nums[c]) among all valid ordered triplets. If no valid triplet exists, return 0.

Clarifying Questions

  1. What is the size range of the input array nums?
    • Typically, the arrays can be quite large, but for the sake of practical constraints, let’s assume the size can go up to 10^5.
  2. Can the numbers in nums be negative?
    • Yes, the numbers can be positive, negative, or zero.
  3. What should be returned if no triplets are found?
    • The problem specifies that if no valid triplet exists, you should return 0.

Strategy

  1. Brute Force Approach:
    • We can iterate through all possible triplets (a, b, c) and check if they form a valid triplet and calculate their sum.
    • This approach involves three nested loops, and its time complexity is O(n^3). This is not efficient for large arrays.
  2. Optimized approach using Dynamic Programming:
    • Maintain two auxiliary arrays:
      1. leftMax[i] to store the maximum values from the left to i-1 which are less than nums[i].
      2. rightMax[i] to store the maximum values from i+1 to the end of the array which are greater than nums[i].
    • Iterate the array to populate leftMax and rightMax arrays and calculate the possible triplet values efficiently.

Time Complexity

The time complexity for the optimized approach will be O(n) for creating the left and right helper arrays plus O(n) for computing the result, which is O(n) overall.

Code

Here’s the C++ implementation of the optimized approach:

#include <vector>
#include <algorithm>
#include <limits.h>

int maxValueOrderedTriplet(std::vector<int>& nums) {
    int n = nums.size();
    if (n < 3) return 0;

    std::vector<int> leftMax(n, INT_MIN);
    std::vector<int> rightMax(n, INT_MIN);

    // Fill leftMax
    for (int i = 1; i < n; ++i) {
        leftMax[i] = leftMax[i-1];
        if (nums[i-1] < nums[i]) {
            leftMax[i] = std::max(leftMax[i], nums[i-1]);
        }
    }

    // Fill rightMax
    for (int i = n-2; i >= 0; --i) {
        rightMax[i] = rightMax[i+1];
        if (nums[i+1] > nums[i]) {
            rightMax[i] = std::max(rightMax[i], nums[i+1]);
        }
    }

    // Find the maximum triplet sum
    int maxSum = 0;
    for (int b = 1; b < n-1; ++b) {
        if (leftMax[b] != INT_MIN && rightMax[b] != INT_MIN) {
            maxSum = std::max(maxSum, leftMax[b] + nums[b] + rightMax[b]);
        }
    }

    return maxSum;
}

// Example usage
// int main() {
//     std::vector<int> nums = {1, 2, 3, 4};
//     int result = maxValueOrderedTriplet(nums);
//     std::cout << "Max value of ordered triplet: " << result << std::endl;
//     return 0;
// }

Explanation

  1. leftMax and rightMax Arrays:
    • leftMax[i]: holds the maximum elements to the left of i which are smaller than nums[i].
    • rightMax[i]: holds the maximum elements to the right of i which are greater than nums[i].
  2. Filling leftMax and rightMax Arrays:
    • We fill leftMax from left to right by checking for elements smaller than the current element.
    • We fill rightMax from right to left by checking for elements greater than the current element.
  3. Compute Maximum Sum:
    • We iterate through the array and check each position as the middle element of the triplet.
    • We then compute the possible sum of the triplet using the precomputed arrays and track the maximum sum.

This solution ensures that we find the optimal triplet sum in linear time.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI