educative.io

Why start with the largest window and shrink rather than the smallest window and grow?

Courses
,
#1

When I originally did the solution without reading the answer, I expanded the window size until I found a sum that was greater than or equal to S. My solution completed around 3.6s on average. The answer algorithm uses the biggest window and shrinks, searching for the smallest window length possible with an answer greater than S. When I ran the answer solution, it completed around 3.9s on average.

Can you help me understand what shrinking the window optimizes for compared to growing?

Here is my growing solution:
public static int findMinSubArray(int S, int[] arr) {
int solutionLength = 0;
boolean found = false;
for (int windowSize = 1; windowSize < arr.length; windowSize++) {
if(found) {
break;
}
int windowStart = 0;
int windowSum = 0;

        for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
            windowSum += arr[windowEnd];

            if(windowEnd >= windowSize - 1) {
                if(windowSum >= S) {
                    solutionLength = windowSize;
                    found = true;
                    break;
                }

                windowSum -= arr[windowStart];
                windowStart++;
            }
        }
    }

    return solutionLength;
}

Is my solution with growing the window too optimistic, whereas shrinking the window is likely to find any solution faster given larger data sets?

1 Like
#2

In your solution, the Worst Case run time is O(n^2)
because if the final solution is the length of the array, then it is the worst case.

Instead to loop by the different size, remember the start index and then move the start index when reach the sum S until it is smaller than S is actually faster in the runtime it is O(2n)-> O(n)