Solution using Prefix and Suffix Arrays (DP)
IntuitionThe problem asks to find the minimum sum of a triplet (i, j, k) from the array, where i < j < k, and the element at index j should be greater than both
# **Intuition**  
The problem asks to find the minimum sum of a triplet (i, j, k) from the array, where `i < j < k`, and the element at index `j` should be greater than both its prefix (i.e., `nums[i]` for `i < j`) and its suffix (i.e., `nums[k]` for `k > j`). This suggests that `nums[j]` should be the local peak in terms of value, surrounded by smaller numbers. The task is to find such a triplet and return its sum. If no such triplet exists, return -1.

---

# **Approach**  
1. **Prefix and Suffix Arrays:**
   - **Prefix array**: For each index `j`, store the smallest value seen from the left up to `j-1`. This helps quickly determine if there's a smaller value to the left of `j`.
   - **Suffix array**: For each index `j`, store the smallest value seen from the right up to `j+1`. This helps quickly determine if there's a smaller value to the right of `j`.

2. **Iterating through possible middle elements:**
   - After constructing the prefix and suffix arrays, iterate through each possible middle element `nums[j]` and check if it satisfies the condition `nums[j] > prefix[j-1]` and `nums[j] > suffix[j+1]`.
   - If so, calculate the sum `nums[i] + nums[j] + nums[k]` and update the minimum sum found.

3. **Edge case handling:**
   - If no valid triplet is found after checking all possibilities, return -1.

---

# **Complexity**  
- **Time complexity:**  
  - Constructing the prefix array takes **O(n)**.  
  - Constructing the suffix array takes **O(n)**.  
  - Iterating through each possible middle element and checking conditions also takes **O(n)**.  
  - **Total: O(n)**, where **n** is the size of the array.

- **Space complexity:**  
  - We use two extra arrays (prefix and suffix) to store minimum values, each of size **n**.  
  - **Total: O(n)**.

---

# **Code**  
```cpp
class Solution {
public:
    int minimumSum(vector<int>& nums) {
        int n = nums.size();
        
        vector<int> prefix(n, 0);
        prefix[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = min(prefix[i - 1], nums[i]);
        }

        vector<int> suffix(n, 0);
        suffix[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = min(suffix[i + 1], nums[i]);
        }

        int answer = 2500; // this value is based on the constraints of the problem ==> (max value of nums[i] * max length of nums array) = (50*50)
        for (int j = 1; j < n - 1; j++) {
            if (nums[j] > prefix[j - 1] && nums[j] > suffix[j + 1]) {
                answer = min(answer, nums[j] + prefix[j - 1] + suffix[j + 1]);
            }
        }

        if (answer == 2500) {
            return -1;
        }

        return answer;
    }
};
```
['Array', 'Dynamic Programming', 'C++']