Sliding Window & Suffix Array || EXPLAINED INTUTION APPROACH ||
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intution behind this solution comes from the fact that , "we have to find two non o
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intution behind this solution comes from the fact that , "we have to find two non overlaping subarrays ". so we have to start finding the next subarray from the point where our first target is reached.  \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nwe have two objectives here : \n(1) how to find the minimum lenth of target subarray from the remaining subarray\n(2) how we will calculate the answer\n\nFor Objective 1 \n-we will precompute the suffix array using sliding window and maintaining a minimum value (target subarray), we will start iterating from the end of the array\n\nFor Objective 2\n-we will start finding a target subarray from the start, while maintaining the minimum length(from all the previous target subarrays). And once we reach a target subarray we will try to calulate the ans asvnow we know the minimum length of the remaining array( where our current subarray ends) using the suffix array.\n\nlook out for the edge cases in the code.\n\nWe have our ans here folkes !!!\n# Complexity\n- Time complexity: O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n\n    int n;\n    vector<int> suffix;\n    // making a sufix array\n    void suffer(vector<int>& arr, int k){\n        int j = n-1, i = n-1;\n        int mini = INT_MAX;\n        int sum = 0;\n        while(j>=0){\n            sum+= arr[j];\n            while(sum>k){\n                sum-=arr[i];\n                i--;\n            }\n            if(sum == k){\n                mini = min(mini,i - j+ 1);\n            }\n            suffix[j] = mini;\n            j--;\n        }\n    }\n    int minSumOfLengths(vector<int>& arr, int target) {\n        n = arr.size();\n        suffix.resize(n,INT_MAX);\n\n        suffer(arr, target);\n        // we will do sliding window and when a window becomes equal to target we will check for the minimum for index j+1;\n\n        int i = 0, j = 0;\n        int mini = INT_MAX;\n        int sum = 0, ans = INT_MAX;\n        \n        while(j<n){\n            sum += arr[j];\n\n            while(sum> target){\n                sum-= arr[i];\n                i++;\n            }\n            if(sum == target){\n                mini = min(mini, j - i+1);\n                if(j+1<n && suffix[j+1]!= INT_MAX){\n                ans = min(ans, mini + suffix[j+1]);\n                }\n            }\n            j++;\n        }\n        return ans == INT_MAX? -1 : ans;\n    }\n};\n```
['Dynamic Programming', 'Sliding Window', 'Suffix Array', 'C++']