HOW I GRADUALLY OPTIMIZED | C++
\nHOW I APPROACHED AND GRADUALLY OPTIMIZED\n\nFIRST (TLE) 53/60 passed\n\n1) prefix sum array\n2) collect all the subarray {start, end} whose sum matches target
\nHOW I APPROACHED AND GRADUALLY OPTIMIZED\n\nFIRST (TLE) 53/60 passed\n\n1) prefix sum array\n2) collect all the subarray {start, end} whose sum matches target\n3) loop through unique pair subarrays N*(N-1)/2\n4) compare non-overlapping and minimize the sum of their lengths\n\n```\nclass Solution {\npublic:\n    int minSumOfLengths(vector<int>& arr, int target) {\n        int n = arr.size();\n        arr.insert(arr.begin(),0);\n        \n        for(int i=1;i<=n;i++)\n            arr[i]+=arr[i-1];\n        \n        vector<pair<int,int>> vtr;\n        for(int i=0;i<n;i++){\n           for(int j=i;j<n;j++){\n               int subsum = arr[j+1]-arr[i];\n               if(subsum==target)\n                   vtr.push_back({i,j});\n           }\n        }\n\n        int mini = INT_MAX;\n        if(vtr.size()<=1)\n            return -1;\n        for(int i=0;i<vtr.size();i++){\n            for(int j=i+1; j<vtr.size();j++){\n                if(vtr[i].second<vtr[j].first){\n                    mini=min(vtr[i].second-vtr[i].first+1 + vtr[j].second-vtr[j].first+1 , mini);\n                }\n            }\n        }\n        if(mini==INT_MAX) return -1;\n        else return mini;\n        \n    }\n};\n```\n\n\nSECOND 54/60 (TLE) PASSED\n\n1) JUST BREAKING THE LOOP WHEN SUBARRAY SUM IS GREATER THAN THE TARGET\n\n```\nclass Solution {\npublic:\n    int minSumOfLengths(vector<int>& arr, int target) {\n        int n = arr.size();\n        arr.insert(arr.begin(),0);\n        \n        for(int i=1;i<=n;i++)\n            arr[i]+=arr[i-1];\n        \n\n        vector<pair<int,int>> vtr;\n        for(int i=0;i<n;i++){\n           for(int j=i;j<n;j++){\n               int subsum = arr[j+1]-arr[i];\n               if(subsum>target)\n                   break;\n               if(subsum==target)\n                   vtr.push_back({i,j});\n           }\n        }\n     \n        int mini = INT_MAX;\n        if(vtr.size()<=1)\n            return -1;\n        for(int i=0;i<vtr.size();i++){\n            for(int j=i+1; j<vtr.size();j++){\n                if(vtr[i].second<vtr[j].first){\n                    mini=min(vtr[i].second-vtr[i].first+1 + vtr[j].second-vtr[j].first+1 , mini);\n                }\n            }\n        }\n        if(mini==INT_MAX) return -1;\n        else return mini;\n        \n    }\n};\n```\n\nTHIRD 54/60 (TLE) PASSED\n\n1) INSTEAD OF PREFIX SUM ARRAY, I USED A HASHMAP TO STORE THE {SUM, ending_array_index}\n2) WITH THE HELP OF THE MAP COLLECT SUBARRAY INDICES {start, end} WHOSE SUM EQUALS TARGET\n\n```\nclass Solution {\npublic:\n    int minSumOfLengths(vector<int>& arr, int target) {\n        int n = arr.size();\n        vector<int> v = arr;\n        map<int,int> mp;\n        mp[0]=-1;\n        vector<pair<int,int>> vtr;\n        int sum=0;\n        for(int i=0;i<n;i++){\n            sum+=arr[i];\n            if(mp.find(sum-target)!=mp.end()){\n                vtr.push_back({mp[sum-target]+1, i});\n            }\n            mp[sum]=i;\n        }\n        for(auto x:vtr)\n            cout<<x.first<<" "<<x.second<<endl;\n        \n        \n         int mini = INT_MAX;\n        if(vtr.size()<=1)\n            return -1;\n        for(int i=0;i<vtr.size();i++){\n            for(int j=i+1; j<vtr.size();j++){\n                if(vtr[i].second<vtr[j].first){\n                    mini=min(vtr[i].second-vtr[i].first+1 + vtr[j].second-vtr[j].first+1 , mini);\n                }\n            }\n        }\n        if(mini==INT_MAX) return -1;\n        else return mini;\n        \n    }\n};\n```\n\nFOURTH (WRONG) 56/60 PASSED\n\n1) TO OPTIMIZE THE SECOND PART, I DO NOT CHECK THAT OVERLAPPING CONDITION\n2) JUST ADDED THE TWO MEAN SUBARRAY LENGTH AND RETURNED\n\n```\nbool comp(pair<int,int> a, pair<int,int> b){\n    return a.second-a.first+1 < b.second-b.first+1;\n}\n\nclass Solution {\npublic:\n    int minSumOfLengths(vector<int>& arr, int target) {\n        int n = arr.size();\n        vector<int> v = arr;\n        map<int,int> mp;\n        mp[0]=-1;\n        vector<pair<int,int>> vtr;\n        int sum=0;\n        for(int i=0;i<n;i++){\n            sum+=arr[i];\n            if(mp.find(sum-target)!=mp.end()){\n                vtr.push_back({mp[sum-target]+1, i});\n            }\n            mp[sum]=i;\n        }\n        if(vtr.size()<=1)\n            return -1;\n        sort(vtr.begin(), vtr.end(), comp);\n        return vtr[0].second - vtr[0].first+1+vtr[1].second - vtr[1].first+1;\n        \n    }\n};\n```\n\nFIFTH (WRONG) 57/60 PASSED\n\n1) JUST ADDED A OVERLAP CHECKER TWO THE PREVIOUSLY INSERTED SUBARRAY INDICES\n\n```\nbool comp(pair<int,int> a, pair<int,int> b){\n    return a.second-a.first+1 < b.second-b.first+1;\n}\n\nclass Solution {\npublic:\n    int minSumOfLengths(vector<int>& arr, int target) {\n        int n = arr.size();\n        vector<int> v = arr;\n        map<int,int> mp;\n        mp[0]=-1;\n        vector<pair<int,int>> vtr;\n        int sum=0;\n        for(int i=0;i<n;i++){\n            sum+=arr[i];\n            if(mp.find(sum-target)!=mp.end()){\n                if(vtr.size()==0)\n                    vtr.push_back({mp[sum-target]+1, i});\n                else{\n                    if(vtr.back().second<mp[sum-target]+1){\n                        vtr.push_back({mp[sum-target]+1, i});\n                    }\n                }\n            }\n            mp[sum]=i;\n        }\n        if(vtr.size()<=1)\n            return -1;\n        sort(vtr.begin(), vtr.end(), comp);\n        return vtr[0].second - vtr[0].first+1+vtr[1].second - vtr[1].first+1;\n       \n        \n    }\n};\n```\n\nSIXTH (CORRECT) ALL PASSED (60/60)\n\n1) USED MAP TO STORE {KEY: ARRAY_INDEX -> VAL: PREFIX_SUM}\n2) FOR EACH INDEX\n    I SEARCHED IF TARGET SUM SUBARRAYS EXSIST IN THE LEFT OR NOT\n        IF EXSIST I CONSIDER THE MINIMUM OF THEIR LENGTH\n    I SEARCHED IF A TARGET SUM SUBARRAY EXSISTS IN ITS JUST RIGHT OR NOT\n        IF EXSISTS ALONG WITH A VALID LEFT SUBARRAY I CONSIDER THE MINIMUM OF LENGTH SUM OF THE TWO\n\n```\nbool comp(pair<int,int> a, pair<int,int> b){\n    return a.second-a.first+1 < b.second-b.first+1;\n}\n\nclass Solution {\npublic:\n    int minSumOfLengths(vector<int>& arr, int target) {\n        int n = arr.size();\n        vector<int> v = arr;\n        map<int,int> mp;\n        mp[0]=-1;\n        vector<pair<int,int>> vtr;\n        int sum=0;\n        for(int i=0;i<n;i++){\n            sum+=arr[i];\n            mp[sum]=i;\n            \n        }\n        \n        int left =INT_MAX/2;\n        int right=0;\n        int mini = INT_MAX;\n        sum=0;\n        for(int i=0;i<n;i++){\n            sum+=arr[i];\n            if(mp.find(sum-target)!=mp.end()){\n                left = min(left,i-mp[sum-target]);\n            }\n            if(mp.find(sum+target)!=mp.end()){\n                right = mp[sum+target]-i;\n                if(left!=INT_MAX/2)\n                    mini=min(mini, right+left);\n            }\n            \n        }\n        if(mini==INT_MAX)\n            return -1;\n        return mini;\n    \n    }\n};\n```\n
[]