kotlin coding test course, sliding window

One of the common problem types that appear in coding interviews is the Sliding Window technique. This technique is very useful when working with subsets of an array. In particular, it boasts excellent performance when calculating the sum, maximum, minimum, etc., of consecutive elements. In this article, we will explain the basic concept of the sliding window along with the process of solving practical problems in detail.

Problem Introduction

Problem: Maximum Length of Subarray

There is a given integer array nums and an integer k. Your task is to find the length of the longest subarray in the nums array such that the sum of its consecutive elements is less than or equal to k. If such an array does not exist, return 0.

Example

    Input: nums = [1, 2, 3, 4, 5], k = 5
    Output: 2
    Explanation: The length of [2, 3] or [1, 2] is a maximum of 2.
    

Approach to the Problem

This problem can be solved using the sliding window technique. This method involves traversing the array while using two pointers (start and end) to adjust the size of the window. The longest subarray satisfying the desired condition is found by adjusting the window size as needed.

Problem Solving Process

Step 1: Initialize Pointers

First, initialize the start pointer start and the end pointer end. Set the start pointer to 0 and the end pointer to 0. Also, initialize a variable sum to keep track of the sum of the array.

Step 2: Expand the Window with a Loop

Move the end pointer end to the end of the array to expand the window. Add the current element to sum, and if sum exceeds k, move the start pointer start to adjust sum to be less than or equal to k.

Step 3: Update Maximum Length

When each window is less than or equal to k, calculate the current length and store it in the maximum length variable.

Step 4: Return Result

After completing all the processes, return the maximum length.

Kotlin Implementation

fun maxLengthSubArray(nums: IntArray, k: Int): Int {
    var start = 0
    var end = 0
    var sum = 0
    var maxLength = 0

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

        while (sum > k && start <= end) {
            sum -= nums[start]
            start++
        }

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

    return maxLength
}

Result Verification

After executing the code to solve the problem, verify the results with various test cases.

fun main() {
    println(maxLengthSubArray(intArrayOf(1, 2, 3, 4, 5), 5)) // Output: 2
    println(maxLengthSubArray(intArrayOf(1, 2, 3, 4, 5), 11)) // Output: 5
    println(maxLengthSubArray(intArrayOf(5, 4, 3, 2, 1), 3)) // Output: 1
    println(maxLengthSubArray(intArrayOf(1, 2, 3, 4, 5), 0)) // Output: 0
}

Conclusion

In this tutorial, we covered the process of solving the maximum length subarray problem using the sliding window technique. The sliding window technique is a powerful tool for efficiently solving array or string problems. Practice this technique through various problems.