Google Onsite Question | Very Easy Java O(n) with explanation
\nclass Solution {\n    \n    private int INF = 1000000;\n    \n    public int minSumOfLengths(int[] arr, int target) {\n        if(arr == null || arr.length ==
```\nclass Solution {\n    \n    private int INF = 1000000;\n    \n    public int minSumOfLengths(int[] arr, int target) {\n        if(arr == null || arr.length == 0 || target <= 0) {\n            return 0;\n        }\n        \n        int[] left = findLeft(arr, target); // Calculate length of all sub arrays whose sum is target & ends at i, starts at any j >= 0 where j <= i.\n        int[] right = findLeft(reverse(arr), target); // Do the same thing for right side.\n        right = reverse(right);\n        \n\t\t// Now start from the left, for all i, replace left[i] with the best (minimum most) length, we do this so that at any point i, we know the most optimal sub array length from the left. We will use this information after some time.\n        int minLeft = left[0];\n        for(int i = 1; i < left.length; i++) {\n            minLeft = Math.min(minLeft, left[i]);\n            left[i] = minLeft;\n        }\n        \n        int result = INF;\n\t\t// Now, left[i] already contains most optimal left side sub array length with sum = target from 0 to i.\n\t\t// We will start with right side, make sum of right[i] & left[i-1] since we need to take non-overlapping sub arrays, and compare the sum with result & set the result if necessary.\n        for(int i = right.length - 1; i > 0; i--) {\n            if(right[i] + left[i-1] < result) {\n                result = right[i] + left[i-1];\n            }\n        }\n        \n        return result < INF ? result : -1;\n    }\n    \n    private int[] reverse(int[] a) {\n        int[] r = new int[a.length];\n        int i = 0;\n        for(; i < a.length; i++) {\n            r[i] = a[a.length - 1 - i];\n        }\n        \n        return r;\n    } \n    \n    private int[] findLeft(int[] arr, int target) {\n        int start = 0, i = 0;\n        int sum = 0;\n        int[] left = new int[arr.length];\n        Arrays.fill(left, INF);\n        \n        while(i < arr.length) {\n            sum += arr[i];\n            \n            while(sum > target && start <= i) {\n                sum -= arr[start];\n                start++;\n            }\n            \n            if(sum == target) {\n                left[i] = i - start + 1;\n            }\n            \n            i++;\n        }\n        \n        return left;\n    }\n}\n```
[]