@algorithm.ts/sliding-window v4.0.0

A typescript implementation of the sliding-window algorithm.

Install

• npm

  npm install --save @algorithm.ts/sliding-window

• yarn

  yarn add @algorithm.ts/sliding-window

Usage

• SlidingWindow

  Member	Return	Description
  constructor(options: ISlidingWindowProps)	SlidingWindow
  reset(options?: ISlidingWindowResetOptions)	void	Reset the sliding window.
  forwardLeftBoundary(steps?: number)	void	Move the sliding window left boundary forward by steps steps.
  forwardRightBoundary(steps?: number)	void	Move the sliding window right boundary forward by steps steps.
  min()	number | undefined	Return the minimum element in the Sliding Window.

• ISlidingWindowProps

  • WINDOW_SIZE: (required) the width of the sliding window.

  • compare: (required) compare two index to determine which one is smaller.

  • startIndex: (optional) the first index of the input range.

Example

• A solution of https://leetcode.com/problems/sliding-window-maximum/

  import { SlidingWindow } from '@algorithm.ts/sliding-window'
  
  export function maxSlidingWindow(nums: number[], K: number): number[] {
    const N = nums.length
    if (N < K) return []
  
    const results: number[] = []
    const window = new SlidingWindow({
      WINDOW_SIZE: K,
      compare: (x, y) => nums[y] - nums[x],
    })
  
    window.forwardRightBoundary(K - 1)
    for (let i = K - 1; i < N; ++i) {
      window.forwardRightBoundary()
      results.push(nums[window.min()!])
    }
    return results
  }

Related