Leetcode: Fixed sliding window pattern
Motivation
As a software engineer, we always try to strengthen our problem solving skills on a daily basic and practice leetcode is a perfect way to do so. Obviously, sliding window pattern is one of the most popular patterns that are the key to many optimal solutions to problems involving consecutive array elements (sub-array or sub-string). However, it maybe a bit overwhelming for any beginners to digest this pattern easily. Based on my own learning experience, I think we can break this pattern into two key concepts: fixed and dynamic. Fixed sliding window means the window size does not change while dynamic sliding window means the window size expands or shrinks (based on problem constraints). In this article, I would like to share some thoughts about the fixed sliding window.
Key Observations
When should we use this pattern ?
- Problem involves iterating through sub-array/sub-string
- Input: an array and an integer k (a fixed window size)
- Output: some calculations (sum/average/min/max from sub-array) or distinct characters (from sub-string)