Skip to main content

Sliding Window Fixed Size

This technique aims to reduce the use of nested loop and replace it with a single loop. This algorithmic technique is used when we need to handle the input data in a specific/fixed window size.

How to Identify​

  • Data Structure Involves: Array, String, Linked List
  • Question Type: Find the K-sized substring, subarray, or a target value in a linear data structure such as a linked list, array, or string.

Example​

Contains Duplicate II​

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example
Input: nums = [1,2,3,1], k = 3
Output: true
Typescript
function containsNearbyDuplicate(nums: number[], k: number): boolean {
    const set = new Set<number>()

    for(let i=0; i<nums.length; i++){
        if(i > k) set.delete(nums[i-k-1])
        if(set.has(nums[i])) return true 
        set.add(nums[i])
    }

    return false
}
ProblemsDifficulty
1Contains Duplicate IIEasy
2Number of Sub-arrays of Size K and Average Greater than or Equal to ThresholdMedium