Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Sliding Window

Guide 6 of 6 · Path 6 of 6

← PreviousNext pattern: Two Pointers →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumsliding-window

Fruit Into Baskets

Problem (restated)

Fruits grow in a row; each tree has a type. You may pick from at most two types in one contiguous subarray. Return the maximum number of fruits you can pick.

Intuition

Longest subarray with at most 2 distinct values. classic constrained window.

Approaches

At most two types window

Tested only
Time O(n)Space O(1)

Idea. Expand right adding types to a map. While map has >2 keys, drop from left. Track max window length.

Walkthrough. [1,2,1,2,3] → windows of [1,2,1,2] length 4, then [2,3] length 2 → answer 4.

Trade-offs. Map size ≤ 3 transiently; equivalent to two pointers with counters.

Solution
export function totalFruit(fruits: number[]): number {
  const map = new Map<number, number>();
  let left = 0, best = 0;
  for (let right = 0; right < fruits.length; right++) {
    const x = fruits[right]!;
    map.set(x, (map.get(x) ?? 0) + 1);
    while (map.size > 2) {
      const y = fruits[left]!;
      const c = map.get(y)! - 1;
      if (c === 0) map.delete(y);
      else map.set(y, c);
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

export function totalFruit(fruits: number[]): number {
  const map = new Map<number, number>();
  let left = 0, best = 0;
  for (let right = 0; right < fruits.length; right++) {
    const x = fruits[right]!;
    map.set(x, (map.get(x) ?? 0) + 1);
    while (map.size > 2) {
      const y = fruits[left]!;
      const c = map.get(y)! - 1;
      if (c === 0) map.delete(y);
      else map.set(y, c);
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Reflection