Java Coding Test Course, Sliding Window

Hello! Today, we will learn about an algorithm technique called Sliding Window. This technique is suitable for problems that involve finding partial sums or maximum/minimum values in continuous data. Additionally, this technique significantly reduces time complexity, making it a frequently tested topic in coding assessments.

What is Sliding Window?

Sliding Window is a technique that creates a window of a specific size in linear data structures like arrays or strings and manipulates the contents of that window. This technique is primarily useful in situations such as:

  • When calculating the sum or average of consecutive elements
  • When finding the maximum/minimum value that satisfies specific conditions
  • When looking for values within defined intervals in various optimization problems

Problem Description

Problem: Maximum Length of Subarray

Given an integer array nums and an integer k, find the length of the longest subarray whose sum is less than or equal to k.

Input Example

nums = [1, 2, 3, 4, 5]
k = 5

Output Example

2

The maximum length of a subarray such as [2, 3] or [1, 2] with a sum less than or equal to 5 is 2.

Solution Process

1. Problem Analysis

This problem is about finding the longest subarray with a sum less than or equal to k from the given array. If solved using brute force, the time complexity would be O(n^2), so we can improve it using the sliding window technique.

2. Applying the Sliding Window Technique

The sliding window technique maintains the current sum of the window using two pointers pointing to the start and end of the array. While adjusting the size of the window, we need to find the maximum length. The basic approach is as follows:

Algorithm

  1. Use two pointers start and end to point to the beginning and end of the window.
  2. Move the end pointer to the end of the array while calculating the current window’s sum.
  3. If the sum exceeds k, move the start pointer to the right to decrease the current window’s sum.
  4. Calculate the current window’s length for each case and update the maximum length.

3. Java Code Implementation

Now, let’s write Java code based on the algorithm above:


public class MaxLengthSubarray {
    public static int maxLengthSubarray(int[] nums, int k) {
        int start = 0, end = 0;
        int maxLength = 0;
        int sum = 0;

        while (end < nums.length) {
            sum += nums[end];

            while (sum > k) {
                sum -= nums[start];
                start++;
            }

            maxLength = Math.max(maxLength, end - start + 1);
            end++;
        }

        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        int k = 5;
        System.out.println("Maximum length of subarray: " + maxLengthSubarray(nums, k));
    }
}

4. Code Explanation

The code above performs the following tasks:

  • The maxLengthSubarray function takes the input array nums and integer k as arguments.
  • It initializes the pointers start and end, and uses the sum variable to maintain the current window’s sum.
  • In the while loop, the end pointer is moved, adding nums[end] to the sum.
  • If the current sum exceeds k, the start pointer is moved to the right to update the sum.
  • The maximum length is updated at each step, ultimately returning the maximum length.

Conclusion

Sliding Window is one of the very useful techniques in coding assessments. Through this problem, we learned how to solve algorithm problems more efficiently. Utilizing this technique increases the likelihood of solving various problems more quickly.

If you found this blog post helpful, try out other problems as well. We hope you will learn more about various algorithms and problem-solving techniques!