Sliding Window HackerRank — Java Edition

Q: Two children, Lily and Ron, want to share a chocolate bar. Each of the squares has an integer on it. Lily decides to share a contiguous segment of the bar selected such that: The length of the segment matches Ron’s birth month, and, the sum of the integers on the squares is equal to his birth day. Determine how many ways she can divide the chocolate.

Return: the number of ways the bar can be divided (int)

Constraints:

One strategy that helps me tackle problems is visualizing the ask and sketching it on a notepad. As I did this, I quickly recognized this as a sliding window problem. In this type of problem, we work with a subset of elements (the “window”) within an array and systematically “slide” the window across the entire array, checking for subsets that meet our conditions (the length of the segment must match Ron’s birth month). This process continues until we’ve examined all possible segments in the array by reaching its end.

Let’s visualize this with the following inputs: [2,2,1,3,2], d = 4, m = 2

public static int birthday(List<Integer> s, int d, int m) {
    int patternsFound = 0; // Counter to track valid segments

    for (int i = 0; i <= s.size() - m; i++) { 
        int windowSum = 0; // Track sum for the current window

        for (int j = 0; j < m; j++) { 
            windowSum += s.get(i + j); // Start window relative to i
        }

        // If the sum matches the target value d increase the final count
        if (windowSum == d) {
            patternsFound++;
        }
    }

    return patternsFound;
}

To solve the above I first initialized a counter, patternsFound, to track the number of valid segments that meet the condition. Next, I used a for loop to iterate, or slide a window, across the list. *Ensure that the window stays within bounds. Inside the loop, I used a second for loop to calculate the sum of elements within the current window, keeping track of this sum with windowSum. After calculating the sum for the current window, I checked if it matched the target value d. If it did, I incremented patternsFound. Finally, once traversing the entire list, I returned the total number of patterns found.