Rust/Python linear solution with cumulative min from left to right and right to left
Intuition\nInstead of looking at all tripplets you can precalculate the minimum values from left to right and from right to left (basically commulative min).\n\
# Intuition\nInstead of looking at all tripplets you can precalculate the minimum values from left to right and from right to left (basically commulative min).\n\nNow you iterate over all values from 1 to n - 1. And check what is the min to the left and to the right of it. Which gives us a simple linear solution.\n\n# Complexity\n- Time complexity: $O(n)$\n- Space complexity: $O(n)$\n\n# Code\n```Rust []\nimpl Solution {\n  pub fn minimum_sum(nums: Vec<i32>) -> i32 {\n    let n = nums.len();\n    let mut min_l = vec![nums[0]; n];\n    let mut min_r = vec![nums[n - 1]; n];\n\n    for i in 1 .. n {\n      min_l[i] = min_l[i - 1].min(nums[i]);\n    }\n    for i in (0 .. n - 1).rev() {\n      min_r[i] = min_r[i + 1].min(nums[i]);\n    }\n\n    let mut res = i32::MAX;\n    for i in 1 .. n - 1 {\n      if nums[i] > min_l[i - 1] && nums[i] > min_r[i + 1] {\n        res = res.min(nums[i] + min_l[i - 1] + min_r[i + 1]);\n      }\n    }\n\n    if res == i32::MAX {\n      return -1\n    }\n    return res;\n  }\n}\n```\n```python []\nclass Solution:\n  def minimumSum(self, nums: List[int]) -> int:\n    min_l = [nums[0]] * len(nums)\n    min_r = [nums[-1]] * len(nums)\n\n    for i in range(1, len(nums)):\n      min_l[i] = min(min_l[i - 1], nums[i])\n    for i in range(len(nums) - 2, -1, -1):\n      min_r[i] = min(min_r[i + 1], nums[i])\n\n    res = float(\'inf\')\n    for i in range(1, len(nums) - 1):\n      if nums[i] > min_l[i - 1] and nums[i] > min_r[i + 1]:\n        res = min(res, nums[i] + min_l[i - 1] + min_r[i + 1])\n    return -1 if res == float(\'inf\') else res\n```
['Python3', 'Rust']