2873. Maximum Value of an Ordered Triplet I

[Antim-IWP]

2873. Maximum Value of an Ordered Triplet I

📌 Problem Statement

Given a 0-indexed integer array nums, we need to find the maximum value over all ordered triplets (i, j, k) such that i < j < k. The value of the triplet is defined as:

[
(nums[i] - nums[j]) \times nums[k]
]

If all such triplets result in a negative value, return 0.

---

✅ Approach & Solution

We can efficiently solve this problem using a single pass (O(n)) approach with three key variables:

• mx → Stores the maximum value encountered so far.
• mx_diff → Tracks the maximum difference (nums[i] - nums[j]) encountered so far.
• ans → Stores the maximum valid triplet value.

Algorithm

1. Iterate through the array while keeping track of mx and mx_diff.
2. At each step, update ans with mx_diff * nums[k].
3. Update mx_diff to store the highest difference (mx - x).
4. Update mx as the max element encountered so far.
5. Return ans, ensuring we return 0 if no positive value is found.

---

📌 Code Implementation

from typing import List

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        ans = mx = mx_diff = 0
        for x in nums:
            ans = max(ans, mx_diff * x)
            mx_diff = max(mx_diff, mx - x)
            mx = max(mx, x)
        return ans

---

🔥 Complexity Analysis

• Time Complexity: O(n) → We traverse nums once.
• Space Complexity: O(1) → We use only a few integer variables.

---

🛠 Example Walkthrough

Example 1

🔹 nums = [12,6,1,2,7]
✔️ Maximum triplet: (0, 2, 4)
✔️ Computation: (12 - 1) * 7 = 77
✅ Output: 77

Example 2

🔹 nums = [1,10,3,4,19]
✔️ Maximum triplet: (1, 2, 4)
✔️ Computation: (10 - 3) * 19 = 133
✅ Output: 133

Example 3

🔹 nums = [1,2,3]
✔️ Only possible triplet: (0, 1, 2)
✔️ Computation: (1 - 2) * 3 = -3
✔️ Since it's negative, return 0.
✅ Output: 0

---

🚀 Alternative Approaches

1️⃣ Brute Force (O(n³))

• Try all (i, j, k) triplets and compute their values.
• Inefficient for large inputs (n ≤ 100 is small, but still not ideal).

2️⃣ Using Prefix Arrays (O(n²))

• Precompute max values up to j and use them for calculations.

📌 Why is our approach optimal?
🔹 It avoids unnecessary iterations and only keeps track of the required values, leading to an efficient O(n) solution.

---

🏷 Tags:

• Greedy
• Array
• Mathematical Optimization

---

❓ Discussion

💬 Q: Can this handle large inputs efficiently?
✔️ Yes! Our O(n) solution works in milliseconds for n ≤ 100.

💬 Q: What if all values in nums are the same?
✔️ mx_diff = 0, so the result will be 0.

💬 Q: Can we solve this using DP?
✔️ Yes, but unnecessary since greedy works optimally in O(n).

💬 Q: What are some edge cases we should test?
✔️ Are there any input cases that might break our approach?

💬 Q: Could this be optimized further?
✔️ The current solution is already O(n), but is there a way to reduce the number of operations or improve readability?

---

🔥 PRs & Issues Welcome!

👥 Feel free to suggest optimizations or discuss edge cases! 🚀

[iamAntimPal]

nice question and seggetion