Sliding Window on Arrays in DSA Java - Time & Space Complexity

Time Complexity: Sliding Window on Arrays

O(n)

Understanding Time Complexity

We want to understand how the time needed changes when using the sliding window technique on arrays.

Specifically, how does the number of steps grow as the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public int maxSumSubarray(int[] arr, int k) {
    int maxSum = 0, windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;
    for (int i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        if (windowSum > maxSum) {
            maxSum = windowSum;
        }
    }
    return maxSum;
}
    

This code finds the maximum sum of any subarray of size k using a sliding window.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two loops that each run over parts of the array.
• How many times: First loop runs k times, second loop runs (n - k) times, where n is array length.

How Execution Grows With Input

As the array size grows, the total steps grow roughly in a straight line with n.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The work grows directly with the size of the array.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows in a straight line as the array gets bigger.

Common Mistake

[X] Wrong: "The sliding window always takes more time because it has two loops inside."

[OK] Correct: The two loops together still only go through the array once, so the total time grows linearly, not more.

Interview Connect

Understanding sliding window time complexity helps you explain efficient solutions clearly and confidently in interviews.

Self-Check

"What if we changed the window size k to vary with n, like k = n/2? How would the time complexity change?"

Practice

1. What is the main purpose of the sliding window technique on arrays?

easy

A. To efficiently find subarray sums or properties without recomputing everything

B. To sort the array elements in ascending order

C. To reverse the array elements

D. To find the maximum element in the entire array

Solution

1. Step 1: Understand the sliding window concept

   The sliding window technique moves a fixed-size window over the array to avoid repeated calculations.

2. Step 2: Identify the main use case

   It helps find sums or other properties of subarrays efficiently by updating the window incrementally.

3. Final Answer:

   To efficiently find subarray sums or properties without recomputing everything -> Option A

4. Quick Check:

   Sliding window = efficient subarray calculation [OK]

Hint: Think of a moving window to avoid repeated work [OK]

Common Mistakes:

• Confusing sliding window with sorting
• Thinking it reverses the array
• Assuming it finds max element globally

2. Which of the following Java code snippets correctly initializes a sliding window sum for the first k elements of an array arr?

easy

A. int sum = 0; for(int i = 1; i < k; i++) sum += arr[i];

B. int sum = arr[0]; for(int i = 1; i <= k; i++) sum += arr[i];

C. int sum = 0; for(int i = 0; i <= k; i++) sum += arr[i];

D. int sum = 0; for(int i = 0; i < k; i++) sum += arr[i];

Solution

1. Step 1: Check loop boundaries for summing first k elements

   The loop should run from 0 to k-1 to include exactly k elements.

2. Step 2: Verify each option's loop range

   int sum = 0; for(int i = 0; i < k; i++) sum += arr[i]; loops i from 0 to less than k, summing arr[0] to arr[k-1], which is correct.

3. Final Answer:

   int sum = 0; for(int i = 0; i < k; i++) sum += arr[i]; -> Option D

4. Quick Check:

   Loop 0 to k-1 sums first k elements [OK]

Hint: Loop from 0 to less than k to sum k elements [OK]

Common Mistakes:

• Using <= k causes out-of-bound errors
• Starting loop from 1 misses first element
• Initializing sum with arr[0] and looping incorrectly

3. What will be the output of the following Java code?

int[] arr = {1, 3, 2, 6, -1, 4, 1, 8, 2};
int k = 5;
int maxSum = 0, windowSum = 0;
for(int i = 0; i < k; i++) {
    windowSum += arr[i];
}
maxSum = windowSum;
for(int i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];
    if(windowSum > maxSum) {
        maxSum = windowSum;
    }
}
System.out.println(maxSum);

medium

A. 16

B. 17

C. 18

D. 19

Solution

1. Step 1: Calculate initial window sum for first 5 elements

   Sum of arr[0..4] = 1+3+2+6+(-1) = 11

2. Step 2: Slide window and update maxSum

   i=5: windowSum=11+4-1=14, maxSum=14
   i=6: windowSum=14+1-3=12, maxSum=14
   i=7: windowSum=12+8-2=18, maxSum=18
   i=8: windowSum=18+2-6=14, maxSum=18

3. Final Answer:

   18 -> Option C

4. Quick Check:

   Max sliding window sum = 18 [OK]

Hint: Update sum by adding new and removing old element [OK]

Common Mistakes:

• Not subtracting the element leaving the window
• Incorrect initial sum calculation
• Updating maxSum incorrectly

4. Identify the bug in the following sliding window code that finds the maximum sum of subarrays of size k:

int maxSum = 0;
int windowSum = 0;
for(int i = 0; i <= k; i++) {
    windowSum += arr[i];
}
maxSum = windowSum;
for(int i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];
    if(windowSum > maxSum) {
        maxSum = windowSum;
    }
}
System.out.println(maxSum);

medium

A. The first loop should run from i = 0 to i < k, not i <= k

B. maxSum should be initialized to Integer.MIN_VALUE

C. The second loop should start from i = k + 1

D. windowSum should be reset to 0 before the second loop

Solution

1. Step 1: Check the first loop boundary

   The first loop runs i from 0 to k inclusive, which sums k+1 elements causing out-of-bounds error.

2. Step 2: Correct loop boundary

   The loop should run from 0 to less than k to sum exactly k elements.

3. Final Answer:

   The first loop should run from i = 0 to i < k, not i <= k -> Option A

4. Quick Check:

   Loop boundary off by one causes error [OK]

Hint: Use < k, not <= k, for k elements [OK]

Common Mistakes:

• Using <= k causes array index out of bounds
• Incorrect initialization of maxSum
• Wrong start index in second loop

5. Given an array of integers, write a Java method using the sliding window technique to find the length of the longest subarray with sum less than or equal to a given value target. Which approach correctly solves this problem?

hard

A. Sort the array and use binary search to find subarrays with sum ≤ target

B. Use two pointers to expand and shrink the window, updating max length when sum ≤ target

C. Use nested loops to check all subarrays and track the longest valid one

D. Use a stack to store sums and pop when sum exceeds target

Solution

1. Step 1: Understand the problem constraints

   We want the longest subarray with sum ≤ target, which requires dynamic window size.

2. Step 2: Apply sliding window with two pointers

   Use two pointers to expand the window adding elements, shrink from left when sum > target, track max length.

3. Final Answer:

   Use two pointers to expand and shrink the window, updating max length when sum ≤ target -> Option B

4. Quick Check:

   Two-pointer sliding window finds longest valid subarray [OK]

Hint: Expand window, shrink when sum too big, track max length [OK]

Common Mistakes:

• Sorting breaks original order, invalid for subarrays
• Nested loops are inefficient for large arrays
• Stack is not suitable for sum-based sliding window