Efficient C++ Solution Using Stack (NSR and NSL)
Intuition\n Describe your first thoughts on how to solve this problem. \nThe code aims to find the minimum sum of elements in an array while considering specifi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe code aims to find the minimum sum of elements in an array while considering specific conditions.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. The code defines two functions:\n   - NSR (Next Smaller to Right)\n   - NSL (Next Smaller to Left)\n2. These functions find the next smaller elements to the right and left of each element in the input array.\n3. Two stacks are used to efficiently track these smaller elements.\n4. After finding the next smaller elements to the right and left, we calculate the sum of these smaller elements with the current element and keep track of the minimum sum.\n5. The `minimumSum` function checks if the current element is greater than the next smaller elements on both the right and left. If so, it calculates the sum.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n# Code\n```cpp\nclass Solution {\npublic:\n    #define loop2(n) for(int i=n-1;i>=0;i--)\n    #define loop(n) for(int i=0;i<n;i++)\n\n    vector<int> NSR(vector<int>& nums, int n) {\n        stack<int> st;\n        vector<int> ans;\n        loop2(n) {\n            while (!st.empty() && nums[st.top()] >= nums[i])\n                st.pop();\n            if (!st.empty())\n                ans.push_back(nums[st.top()]);\n            else {\n                ans.push_back(nums[i]);\n                st.push(i);\n            }\n        }\n        reverse(ans.begin(), ans.end());\n        return ans;\n    }\n\n    vector<int> NSL(vector<int>& nums, int n) {\n        stack<int> st;\n        vector<int> ans;\n        loop(n) {\n            while (!st.empty() && nums[st.top()] >= nums[i])\n                st.pop();\n            if (!st.empty())\n                ans.push_back(nums[st.top()]);\n            else {\n                ans.push_back(nums[i]);\n                st.push(i);\n            }\n        }\n        return ans;\n    }\n\n    int minimumSum(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> nsr = NSR(nums, n);\n        vector<int> nsl = NSL(nums, n);\n\n        int mn = INT_MAX;\n        loop(n) {\n            if (nsl[i] < nums[i] && nums[i] > nsr[i]) {\n                int sum = nsr[i] + nsl[i] + nums[i];\n                mn = min(mn, sum);\n            }\n        }\n\n        if (mn == INT_MAX)\n            return -1;\n        return mn;\n    }\n};\n
['Stack', 'Monotonic Stack', 'C++']