Subarray Division 2

  • + 0 comments

    Java 8, Sliding Sum Technique, O(n)

    I added some comments explaining the code

        public static int birthday(List<Integer> s, int d, int m) {
            // Write your code here
            int currSize = 0;
            int numWays = 0;
            if (s.size() < m) return 0;
            
    // get sum of first segement (first m elements)
            for (int i = 0; i < m; i++) { 
                currSize += s.get(i);
            }
    // check sum == d
            if (currSize == d) { 
                numWays++;
            }
            
    // sliding window, subtract prev element and add next element to get sum of the next segment (size m)
    // starts at 1 because you already calculated first segement sum
    // ends on the last segment of size m
            for (int j = 1; j < s.size() - m + 1; j++) { 
                currSize -= s.get(j - 1);
                currSize += s.get(j + m - 1);
                
                if (currSize == d) {
                    numWays++;
                }
            }
            
            return numWays;
        }