Leetcode 1477: Find Two Non-overlapping Sub-arrays Each With Target Sum

In this Leetcode problem, we want to find 2 non overlapping subarray with subarray sum target, and we want to find the pair such that sum of the length of both subarrays is minimal:

Problem statement

Solution

Below is the outline of the algorithms I used, which essentially finds all the subarrays and then go through them in order…

1.How to find the valid subarrays in the first place?
1.a. Since values in array are positive, can do a sliding window
2. Add all the intervals in a List sorted by start
2.a. No need to actually sort, since by using the sliding window it will be sorted already
2.b. Can use a class Interval with methods len(), start(), and end(), method names are quite explicit
3. Also create TreeMap lengthToCount storing the count for each interval length
4. Use TreeSet<Interval> overlap sorted by end
5. Use int minLeft = -1 storing the min length of an interval fully on the left
6. Maintain current the value of the next Interval start as currentFrontier
7. Go through the interval list in order
7.a At each step add minLeft and the min key in lengthToCount and maintain all the data structures by passing the next Interval to the overlap set and update minLeft