Prefix & Suffix Array || C++
Intuition\nLeetCode Hints :\n- Let\'s create two arrays prefix and suffix where prefix[i] is the minimum length of sub-array ends before i and has sum = k, suff
# Intuition\nLeetCode Hints :\n- Let\'s create two arrays prefix and suffix where prefix[i] is the minimum length of sub-array ends before i and has sum = k, suffix[i] is the minimum length of sub-array starting at or after i and has sum = k.\n- The answer we are searching for is min(prefix[i] + suffix[i]) for all values of i from 0 to n-1 where n == arr.length.\n- If you are still stuck with how to build prefix and suffix, you can store for each index i the length of the sub-array starts at i and has sum = k or infinity otherwise, and you can use it to build both prefix and suffix.\n\n# Code\n```\nclass Solution \n{\npublic:\n    int minSumOfLengths(vector<int>& arr, int target) \n    {\n        map<int,int> prefix;\n        int n=arr.size();\n        vector<int> p(n), s(n);\n        int currsum=0;\n        int ans=INT_MAX;\n        for(int x=0; x<n; x++)\n        {\n            currsum+=arr[x];\n            if(currsum==target) ans=min(ans,x+1);\n            else\n            {\n                if(prefix.find(currsum-target)!=prefix.end()) \n                {\n                    ans=min(ans,x-prefix[currsum-target]);\n                }\n            }\n            prefix[currsum]=x;\n            p[x]=ans;\n        }\n        map<int,int> suffix;\n        currsum=0;\n        ans=INT_MAX;\n        for(int x=n-1; x>=0; x--)\n        {\n            currsum+=arr[x];\n            if(currsum==target) ans=min(ans,n-x);\n            else\n            {\n                if(suffix.find(currsum-target)!=suffix.end()) \n                {\n                    ans=min(ans,suffix[currsum-target]-x);\n                }\n            }\n            suffix[currsum]=x;\n            s[x]=ans;\n        }\n        ans=INT_MAX;\n        for(int x=1; x<n; x++)\n        {\n            if((long long)p[x-1]+s[x]<INT_MAX) ans=min(ans,p[x-1]+s[x]);\n        }\n        if(ans==INT_MAX) return -1;\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'C++']