Fruits Into Baskets

🎯

Fruits Into Baskets

mediumSLIDING_WINDOWAmazonGoogle

Imagine you have two baskets and want to collect fruits from a row of trees, but you can only carry two types of fruits at a time. How do you pick the longest stretch of trees to maximize your haul?

💡 This problem is a classic example of using a variable-size sliding window to find the longest subarray with at most two distinct elements. Beginners often struggle because they try to use fixed-size windows or brute force, missing the efficient approach that dynamically adjusts the window size.

📋

Problem Statement

You are given an integer array fruits where fruits[i] represents the type of fruit on the i-th tree. You have two baskets, and each basket can only hold one type of fruit. You want to pick fruits from a contiguous segment of trees such that you only have at most two different types of fruits in total. Return the length of the longest such segment.

1 ≤ fruits.length ≤ 10^50 ≤ fruits[i] < fruits.length

💡

Example

Input"[1, 2, 1]"

Output3

All fruits can be picked since there are only two types: 1 and 2.

Input"[0, 1, 2, 2]"

Output3

The longest segment with at most two types is [1, 2, 2].

Input"[1, 2, 3, 2, 2]"

Output4

The longest segment is [2, 3, 2, 2] with types 2 and 3.

• All fruits are the same type → output is length of entire array
• Array length is 1 → output is 1
• Array with all distinct fruits → output is 2 (since only two baskets)
• Array with exactly two types of fruits → output is length of entire array

⚠️

Common Mistakes

Not shrinking the window correctly when more than two fruit types appear

Window contains invalid segments, leading to wrong max length

✅ Use a while loop to shrink from left until only two fruit types remain

Using a fixed-size window instead of variable-size

Misses longer valid segments, returns incorrect answer

✅ Implement two pointers that expand and shrink the window based on distinct fruit count

Not removing fruit types from hashmap/frequency map when count reaches zero

Hashmap size remains > 2 incorrectly, causing unnecessary shrinking

✅ Delete fruit type from map when its count drops to zero

Assuming fruit types are small integers and using frequency array without checking max fruit type

Array index out of bounds or excessive memory usage

✅ Check max fruit type before using frequency array or fallback to hashmap

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem constraints and what makes it inefficient, setting the stage for optimization.

Intuition

Check every possible contiguous subarray and count the number of distinct fruit types. Track the longest subarray with at most two distinct types.

Algorithm

1. Initialize max_length to 0.
2. For each start index i in the array:
3. For each end index j from i to end:
4. Count distinct fruit types in fruits[i..j].
5. If distinct types ≤ 2, update max_length.
6. Return max_length.

💡 The nested loops and counting distinct fruits inside the inner loop make this approach slow and hard to optimize directly.

</>

Code

def totalFruit(fruits):
    max_length = 0
    n = len(fruits)
    for i in range(n):
        basket = {}
        for j in range(i, n):
            basket[fruits[j]] = basket.get(fruits[j], 0) + 1
            if len(basket) > 2:
                break
            max_length = max(max_length, j - i + 1)
    return max_length

# Driver code
if __name__ == '__main__':
    print(totalFruit([1,2,1]))  # Output: 3
    print(totalFruit([0,1,2,2]))  # Output: 3
    print(totalFruit([1,2,3,2,2]))  # Output: 4

Line Notes

max_length = 0Initialize the variable to keep track of the longest valid segment found so far

for i in range(n):Outer loop picks the start index of the subarray

basket = {}Dictionary to count fruit types in the current window

for j in range(i, n):Inner loop expands the window to the right

basket[fruits[j]] = basket.get(fruits[j], 0) + 1Add current fruit to basket or increment count

if len(basket) > 2:If more than two fruit types, stop expanding this window

max_length = max(max_length, j - i + 1)Update max_length if current window is valid and longer

return max_lengthReturn the longest valid window length found

import java.util.*;
public class Solution {
    public static int totalFruit(int[] fruits) {
        int maxLength = 0;
        int n = fruits.length;
        for (int i = 0; i < n; i++) {
            Map<Integer, Integer> basket = new HashMap<>();
            for (int j = i; j < n; j++) {
                basket.put(fruits[j], basket.getOrDefault(fruits[j], 0) + 1);
                if (basket.size() > 2) {
                    break;
                }
                maxLength = Math.max(maxLength, j - i + 1);
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        System.out.println(totalFruit(new int[]{1,2,1})); // 3
        System.out.println(totalFruit(new int[]{0,1,2,2})); // 3
        System.out.println(totalFruit(new int[]{1,2,3,2,2})); // 4
    }
}

Line Notes

int maxLength = 0;Initialize max length to track longest valid segment

for (int i = 0; i < n; i++) {Outer loop selects start index

Map<Integer, Integer> basket = new HashMap<>();Map to count fruit types in current window

for (int j = i; j < n; j++) {Inner loop expands window to the right

basket.put(fruits[j], basket.getOrDefault(fruits[j], 0) + 1);Add or increment fruit count

if (basket.size() > 2) {Stop if more than two fruit types

maxLength = Math.max(maxLength, j - i + 1);Update max length if current window valid

return maxLength;Return the longest valid window length

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int totalFruit(vector<int>& fruits) {
    int maxLength = 0;
    int n = fruits.size();
    for (int i = 0; i < n; i++) {
        unordered_map<int, int> basket;
        for (int j = i; j < n; j++) {
            basket[fruits[j]]++;
            if (basket.size() > 2) {
                break;
            }
            maxLength = max(maxLength, j - i + 1);
        }
    }
    return maxLength;
}

int main() {
    vector<int> fruits1 = {1,2,1};
    cout << totalFruit(fruits1) << endl; // 3
    vector<int> fruits2 = {0,1,2,2};
    cout << totalFruit(fruits2) << endl; // 3
    vector<int> fruits3 = {1,2,3,2,2};
    cout << totalFruit(fruits3) << endl; // 4
    return 0;
}

Line Notes

int maxLength = 0;Initialize max length to track longest valid segment

for (int i = 0; i < n; i++) {Outer loop selects start index

unordered_map<int, int> basket;Map to count fruit types in current window

for (int j = i; j < n; j++) {Inner loop expands window to the right

basket[fruits[j]]++;Add or increment fruit count

if (basket.size() > 2) {Stop if more than two fruit types

maxLength = max(maxLength, j - i + 1);Update max length if current window valid

return maxLength;Return the longest valid window length

function totalFruit(fruits) {
    let maxLength = 0;
    const n = fruits.length;
    for (let i = 0; i < n; i++) {
        const basket = new Map();
        for (let j = i; j < n; j++) {
            basket.set(fruits[j], (basket.get(fruits[j]) || 0) + 1);
            if (basket.size > 2) {
                break;
            }
            maxLength = Math.max(maxLength, j - i + 1);
        }
    }
    return maxLength;
}

// Test cases
console.log(totalFruit([1,2,1])); // 3
console.log(totalFruit([0,1,2,2])); // 3
console.log(totalFruit([1,2,3,2,2])); // 4

Line Notes

let maxLength = 0;Initialize max length to track longest valid segment

for (let i = 0; i < n; i++) {Outer loop selects start index

const basket = new Map();Map to count fruit types in current window

for (let j = i; j < n; j++) {Inner loop expands window to the right

basket.set(fruits[j], (basket.get(fruits[j]) || 0) + 1);Add or increment fruit count

if (basket.size > 2) {Stop if more than two fruit types

maxLength = Math.max(maxLength, j - i + 1);Update max length if current window valid

return maxLength;Return the longest valid window length

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Two nested loops over n elements, and counting distinct fruits inside inner loop can be O(1) with hashmap but repeated for each subarray, resulting in O(n^2) overall.

💡 For n=20, this means about 400 operations, which is okay, but for n=100000, it becomes 10 billion operations, which is too slow.

Interview Verdict: TLE

This approach is too slow for large inputs, but it helps understand the problem and why we need a better method.

🧠

Sliding Window with Hash Map (Optimal)

💡 This approach uses a variable-size sliding window to efficiently track at most two distinct fruit types, making it much faster than brute force.

Intuition

Expand the window by moving the right pointer and track fruit counts. If more than two types appear, shrink the window from the left until only two types remain.

Algorithm

1. Initialize two pointers left and right at 0, and a hashmap to count fruit types.
2. Expand right pointer, add fruits[right] to hashmap.
3. If hashmap size exceeds 2, move left pointer forward, decrementing counts, removing fruit types with zero count.
4. Track the maximum window size where hashmap size ≤ 2.
5. Return the maximum window size found.

💡 The key is maintaining the window so it always contains at most two distinct fruit types, which requires careful incrementing and decrementing counts.

</>

Code

def totalFruit(fruits):
    basket = {}
    left = 0
    max_length = 0
    for right in range(len(fruits)):
        basket[fruits[right]] = basket.get(fruits[right], 0) + 1
        while len(basket) > 2:
            basket[fruits[left]] -= 1
            if basket[fruits[left]] == 0:
                del basket[fruits[left]]
            left += 1
        max_length = max(max_length, right - left + 1)
    return max_length

# Driver code
if __name__ == '__main__':
    print(totalFruit([1,2,1]))  # Output: 3
    print(totalFruit([0,1,2,2]))  # Output: 3
    print(totalFruit([1,2,3,2,2]))  # Output: 4

Line Notes

basket = {}Initialize hashmap to count fruit types in current window

left = 0Left pointer starts at beginning of window

for right in range(len(fruits))Right pointer expands window to the right

basket[fruits[right]] = basket.get(fruits[right], 0) + 1Add current fruit to basket or increment count

while len(basket) > 2:If more than two fruit types, shrink window from left

basket[fruits[left]] -= 1Decrement count of fruit at left pointer

if basket[fruits[left]] == 0:Remove fruit type if count reaches zero

left += 1Move left pointer forward to shrink window

max_length = max(max_length, right - left + 1)Update max length if current window valid

return max_lengthReturn the longest valid window length

import java.util.*;
public class Solution {
    public static int totalFruit(int[] fruits) {
        Map<Integer, Integer> basket = new HashMap<>();
        int left = 0, maxLength = 0;
        for (int right = 0; right < fruits.length; right++) {
            basket.put(fruits[right], basket.getOrDefault(fruits[right], 0) + 1);
            while (basket.size() > 2) {
                basket.put(fruits[left], basket.get(fruits[left]) - 1);
                if (basket.get(fruits[left]) == 0) {
                    basket.remove(fruits[left]);
                }
                left++;
            }
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        System.out.println(totalFruit(new int[]{1,2,1})); // 3
        System.out.println(totalFruit(new int[]{0,1,2,2})); // 3
        System.out.println(totalFruit(new int[]{1,2,3,2,2})); // 4
    }
}

Line Notes

Map<Integer, Integer> basket = new HashMap<>();Initialize map to count fruit types in current window

int left = 0, maxLength = 0;Left pointer and max length initialization

for (int right = 0; right < fruits.length; right++) {Right pointer expands window

basket.put(fruits[right], basket.getOrDefault(fruits[right], 0) + 1);Add or increment fruit count

while (basket.size() > 2) {Shrink window if more than two fruit types

basket.put(fruits[left], basket.get(fruits[left]) - 1);Decrement count of fruit at left

if (basket.get(fruits[left]) == 0) {Remove fruit type if count zero

left++;Move left pointer forward

maxLength = Math.max(maxLength, right - left + 1);Update max length if current window valid

return maxLength;Return longest valid window length

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int totalFruit(vector<int>& fruits) {
    unordered_map<int, int> basket;
    int left = 0, maxLength = 0;
    for (int right = 0; right < (int)fruits.size(); right++) {
        basket[fruits[right]]++;
        while ((int)basket.size() > 2) {
            basket[fruits[left]]--;
            if (basket[fruits[left]] == 0) {
                basket.erase(fruits[left]);
            }
            left++;
        }
        maxLength = max(maxLength, right - left + 1);
    }
    return maxLength;
}

int main() {
    vector<int> fruits1 = {1,2,1};
    cout << totalFruit(fruits1) << endl; // 3
    vector<int> fruits2 = {0,1,2,2};
    cout << totalFruit(fruits2) << endl; // 3
    vector<int> fruits3 = {1,2,3,2,2};
    cout << totalFruit(fruits3) << endl; // 4
    return 0;
}

Line Notes

unordered_map<int, int> basket;Map to count fruit types in current window

int left = 0, maxLength = 0;Initialize left pointer and max length

for (int right = 0; right < (int)fruits.size(); right++) {Right pointer expands window

basket[fruits[right]]++;Add or increment fruit count

while ((int)basket.size() > 2) {Shrink window if more than two fruit types

basket[fruits[left]]--;Decrement count of fruit at left

if (basket[fruits[left]] == 0) {Remove fruit type if count zero

left++;Move left pointer forward

maxLength = max(maxLength, right - left + 1);Update max length if current window valid

return maxLength;Return longest valid window length

function totalFruit(fruits) {
    const basket = new Map();
    let left = 0, maxLength = 0;
    for (let right = 0; right < fruits.length; right++) {
        basket.set(fruits[right], (basket.get(fruits[right]) || 0) + 1);
        while (basket.size > 2) {
            basket.set(fruits[left], basket.get(fruits[left]) - 1);
            if (basket.get(fruits[left]) === 0) {
                basket.delete(fruits[left]);
            }
            left++;
        }
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

// Test cases
console.log(totalFruit([1,2,1])); // 3
console.log(totalFruit([0,1,2,2])); // 3
console.log(totalFruit([1,2,3,2,2])); // 4

Line Notes

const basket = new Map();Map to count fruit types in current window

let left = 0, maxLength = 0;Initialize left pointer and max length

for (let right = 0; right < fruits.length; right++) {Right pointer expands window

basket.set(fruits[right], (basket.get(fruits[right]) || 0) + 1);Add or increment fruit count

while (basket.size > 2) {Shrink window if more than two fruit types

basket.set(fruits[left], basket.get(fruits[left]) - 1);Decrement count of fruit at left

if (basket.get(fruits[left]) === 0) {Remove fruit type if count zero

left++;Move left pointer forward

maxLength = Math.max(maxLength, right - left + 1);Update max length if current window valid

return maxLength;Return longest valid window length

⏱

Complexity

TimeO(n)

SpaceO(1)

Each element is visited at most twice (once when right pointer moves forward, once when left pointer moves forward). The hashmap size is at most 3 during shrinking, so operations are O(1).

💡 For n=100000, this means roughly 200000 operations, which is efficient and runs comfortably within time limits.

Interview Verdict: Accepted

This is the optimal approach and what interviewers expect for this problem.

🧠

Sliding Window with Two Pointers and Frequency Array

💡 This approach replaces the hashmap with a fixed-size frequency array for faster access when fruit types are bounded by input size.

Intuition

Use two pointers to maintain a window with at most two distinct fruits, and a frequency array indexed by fruit type to track counts.

Algorithm

1. Initialize frequency array of size max fruit type + 1, left and right pointers, and distinct count.
2. Expand right pointer, increment frequency of fruits[right].
3. If a new fruit type is added, increment distinct count.
4. While distinct count > 2, shrink window from left, decrement frequency, and update distinct count.
5. Track maximum window size where distinct count ≤ 2.
6. Return maximum window size.

💡 This approach trades hashmap overhead for array indexing, which can be faster but requires bounded fruit types.

</>

Code

def totalFruit(fruits):
    max_fruit = max(fruits) if fruits else 0
    freq = [0] * (max_fruit + 1)
    left = 0
    distinct = 0
    max_length = 0
    for right in range(len(fruits)):
        if freq[fruits[right]] == 0:
            distinct += 1
        freq[fruits[right]] += 1
        while distinct > 2:
            freq[fruits[left]] -= 1
            if freq[fruits[left]] == 0:
                distinct -= 1
            left += 1
        max_length = max(max_length, right - left + 1)
    return max_length

# Driver code
if __name__ == '__main__':
    print(totalFruit([1,2,1]))  # Output: 3
    print(totalFruit([0,1,2,2]))  # Output: 3
    print(totalFruit([1,2,3,2,2]))  # Output: 4

Line Notes

max_fruit = max(fruits) if fruits else 0Find max fruit type to size frequency array

freq = [0] * (max_fruit + 1)Frequency array to count fruit occurrences

left = 0Left pointer initialization

distinct = 0Count of distinct fruit types in current window

for right in range(len(fruits))Right pointer expands window

if freq[fruits[right]] == 0:New fruit type encountered, increment distinct

freq[fruits[right]] += 1Increment frequency of current fruit

while distinct > 2:Shrink window if more than two distinct fruits

freq[fruits[left]] -= 1Decrement frequency of fruit at left

if freq[fruits[left]] == 0:If frequency zero, decrement distinct count

left += 1Move left pointer forward

max_length = max(max_length, right - left + 1)Update max length if current window valid

return max_lengthReturn longest valid window length

public class Solution {
    public static int totalFruit(int[] fruits) {
        int maxFruit = 0;
        for (int f : fruits) maxFruit = Math.max(maxFruit, f);
        int[] freq = new int[maxFruit + 1];
        int left = 0, distinct = 0, maxLength = 0;
        for (int right = 0; right < fruits.length; right++) {
            if (freq[fruits[right]] == 0) distinct++;
            freq[fruits[right]]++;
            while (distinct > 2) {
                freq[fruits[left]]--;
                if (freq[fruits[left]] == 0) distinct--;
                left++;
            }
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        System.out.println(totalFruit(new int[]{1,2,1})); // 3
        System.out.println(totalFruit(new int[]{0,1,2,2})); // 3
        System.out.println(totalFruit(new int[]{1,2,3,2,2})); // 4
    }
}

Line Notes

int maxFruit = 0;Find max fruit type to size frequency array

int[] freq = new int[maxFruit + 1];Frequency array for fruit counts

int left = 0, distinct = 0, maxLength = 0;Initialize pointers and counters

for (int right = 0; right < fruits.length; right++) {Right pointer expands window

if (freq[fruits[right]] == 0) distinct++;New fruit type encountered

freq[fruits[right]]++;Increment frequency

while (distinct > 2) {Shrink window if more than two distinct fruits

freq[fruits[left]]--;Decrement frequency at left

if (freq[fruits[left]] == 0) distinct--;Update distinct count

left++;Move left pointer forward

maxLength = Math.max(maxLength, right - left + 1);Update max length

return maxLength;Return longest valid window length

#include <iostream>
#include <vector>
using namespace std;

int totalFruit(vector<int>& fruits) {
    int maxFruit = 0;
    for (int f : fruits) maxFruit = max(maxFruit, f);
    vector<int> freq(maxFruit + 1, 0);
    int left = 0, distinct = 0, maxLength = 0;
    for (int right = 0; right < (int)fruits.size(); right++) {
        if (freq[fruits[right]] == 0) distinct++;
        freq[fruits[right]]++;
        while (distinct > 2) {
            freq[fruits[left]]--;
            if (freq[fruits[left]] == 0) distinct--;
            left++;
        }
        maxLength = max(maxLength, right - left + 1);
    }
    return maxLength;
}

int main() {
    vector<int> fruits1 = {1,2,1};
    cout << totalFruit(fruits1) << endl; // 3
    vector<int> fruits2 = {0,1,2,2};
    cout << totalFruit(fruits2) << endl; // 3
    vector<int> fruits3 = {1,2,3,2,2};
    cout << totalFruit(fruits3) << endl; // 4
    return 0;
}

Line Notes

int maxFruit = 0;Find max fruit type to size frequency array

vector<int> freq(maxFruit + 1, 0);Frequency array for fruit counts

int left = 0, distinct = 0, maxLength = 0;Initialize pointers and counters

for (int right = 0; right < (int)fruits.size(); right++) {Right pointer expands window

if (freq[fruits[right]] == 0) distinct++;New fruit type encountered

freq[fruits[right]]++;Increment frequency

while (distinct > 2) {Shrink window if more than two distinct fruits

freq[fruits[left]]--;Decrement frequency at left

if (freq[fruits[left]] == 0) distinct--;Update distinct count

left++;Move left pointer forward

maxLength = max(maxLength, right - left + 1);Update max length

return maxLength;Return longest valid window length

function totalFruit(fruits) {
    const maxFruit = Math.max(...fruits);
    const freq = new Array(maxFruit + 1).fill(0);
    let left = 0, distinct = 0, maxLength = 0;
    for (let right = 0; right < fruits.length; right++) {
        if (freq[fruits[right]] === 0) distinct++;
        freq[fruits[right]]++;
        while (distinct > 2) {
            freq[fruits[left]]--;
            if (freq[fruits[left]] === 0) distinct--;
            left++;
        }
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

// Test cases
console.log(totalFruit([1,2,1])); // 3
console.log(totalFruit([0,1,2,2])); // 3
console.log(totalFruit([1,2,3,2,2])); // 4

Line Notes

const maxFruit = Math.max(...fruits);Find max fruit type to size frequency array

const freq = new Array(maxFruit + 1).fill(0);Frequency array for fruit counts

let left = 0, distinct = 0, maxLength = 0;Initialize pointers and counters

for (let right = 0; right < fruits.length; right++) {Right pointer expands window

if (freq[fruits[right]] === 0) distinct++;New fruit type encountered

freq[fruits[right]]++;Increment frequency

while (distinct > 2) {Shrink window if more than two distinct fruits

freq[fruits[left]]--;Decrement frequency at left

if (freq[fruits[left]] === 0) distinct--;Update distinct count

left++;Move left pointer forward

maxLength = Math.max(maxLength, right - left + 1);Update max length

return maxLength;Return longest valid window length

⏱

Complexity

TimeO(n)

SpaceO(m) where m is max fruit type

Each element is visited at most twice. Frequency array access is O(1). Space depends on max fruit type value.

💡 If fruit types are small integers, this approach is very fast and memory efficient.

Interview Verdict: Accepted

This is a practical optimization when fruit types are bounded, showing mastery of sliding window technique.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always aim to code the sliding window with hashmap approach (Approach 2) as it balances clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code due to inefficiency
2. Sliding Window with Hash Map	O(n)	O(1)	No	Yes	Code this approach in 95% of interviews
3. Sliding Window with Frequency Array	O(n)	O(m) where m is max fruit type	No	Yes	Use if fruit types are small integers and interviewer allows

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the sliding window approach, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach and its inefficiency.Step 3: Introduce the sliding window technique and explain how it maintains at most two distinct fruits.Step 4: Write clean, optimized code using a hashmap or frequency array.Step 5: Test your code with edge cases and explain your complexity analysis.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test & Explain: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to recognize the sliding window pattern, handle variable window sizes, and optimize from brute force to linear time.

Common Follow-ups

• What if baskets can hold at most k types of fruits? → Use sliding window with hashmap size ≤ k.
• Can you return the actual segment instead of length? → Track start index when max length updates.

💡 These follow-ups test your ability to generalize the solution and modify it to return more information.

🔍

Pattern Recognition

When to Use

1. Problem asks for longest/shortest subarray or substring. 2. Constraint on number of distinct elements (e.g., at most two). 3. Input is an array or string. 4. Need efficient O(n) or O(n log n) solution.

Signature Phrases

'at most two distinct fruits''longest contiguous segment''two baskets to hold fruits'

NOT This Pattern When

Problems requiring fixed-size windows or exact counts (e.g., exact k distinct) are different and may need other techniques.

Similar Problems

Longest Substring with At Most Two Distinct Characters - same pattern on stringsLongest Substring Without Repeating Characters - sliding window with distinct count = 1Sliding Window Maximum - variable window size but different condition

Practice

1. The following code attempts to find the length of the longest substring with at most k distinct characters. Identify the bug that causes incorrect results on some inputs.

from collections import OrderedDict

def length_of_longest_substring_k_distinct(s: str, k: int) -> int:
    if k == 0 or not s:
        return 0
    left = 0
    max_length = 0
    last_seen = OrderedDict()
    for right, char in enumerate(s):
        if char in last_seen:
            del last_seen[char]
        last_seen[char] = right
        max_length = max(max_length, right - left + 1)
        if len(last_seen) > k:
            _, idx = last_seen.popitem(last=False)
            left = idx + 1
    return max_length

medium

A. Not handling the case when k is zero or string is empty

B. Deleting the character from last_seen before re-inserting it

C. Updating max_length before shrinking the window when distinct chars exceed k

D. Using OrderedDict instead of a frequency map

Solution

1. Step 1: Locate max_length update position

   max_length is updated before shrinking the window when distinct chars exceed k, so invalid windows are counted.

2. Step 2: Understand impact

   This causes max_length to include substrings with more than k distinct characters, violating constraints.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Moving max_length update after shrinking fixes correctness [OK]

Hint: Update max_length only after ensuring window is valid [OK]

Common Mistakes:

• Updating max_length too early before shrinking window
• Confusing order of operations in sliding window

2. What is the time complexity of the optimized sliding window algorithm that uses a hash map to track the last seen indices of characters for finding the longest substring without repeating characters?

medium

A. O(n) because each character is visited at most twice by the right and left pointers

B. O(n^2) because each character may cause the left pointer to move multiple times

C. O(n log n) due to hash map operations on each character

D. O(n * m) where m is the size of the character set

Solution

1. Step 1: Analyze pointer movements

   Right pointer moves forward once per character. Left pointer only moves forward when duplicates are found, never backward. Each character is visited at most twice.

2. Step 2: Consider hash map operations

   Hash map lookups and updates are O(1) average. Thus total time is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer sliding window with hash map -> linear time [OK]

Hint: Each character visited max twice -> O(n) [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing hash map average with worst-case

3. The following code attempts to find the maximum average subarray of size k using a sliding window. Identify the line containing the subtle bug that could cause incorrect results or runtime errors.

medium

A. Line 3: initializing current_sum with sum of first k elements

B. Line 6: updating current_sum by adding nums[i] and nums[i - k]

C. Line 5: loop range starting from k to n

D. Line 8: updating max_sum if current_sum is greater

Solution

1. Step 1: Examine update to current_sum

   The line adds nums[i] and nums[i - k], but it should add nums[i] and subtract nums[i - k] to slide the window correctly.

2. Step 2: Identify impact of bug

   Adding both elements inflates current_sum incorrectly, leading to wrong maximum average or runtime errors if indices go out of range.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window requires subtracting the element leaving the window [OK]

Hint: Sliding window sum updates by adding new and subtracting old element [OK]

Common Mistakes:

• Using addition instead of subtraction in window update
• Off-by-one errors in loop boundaries

4. The following code attempts to count the number of contiguous subarrays where the product of all elements is less than k. Identify the line containing the subtle bug that causes incorrect results or infinite loops.

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0
    product = 1
    count = 0
    left = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k and left <= right:
            product = product // nums[left]
            left += 1
        count += right - left + 1
    return count

medium

A. Line 3: Using integer 1 instead of floating point 1.0 for product initialization.

B. Line 11: Incrementing count by 'right - left + 1' instead of 1.

C. Line 2: Returning 0 when k <= 1.

D. Line 9: Using integer division '//' instead of floating point division '/' when updating product.

Solution

1. Step 1: Identify division operation

   Line 9 uses integer division '//' which truncates product, causing incorrect product updates.

2. Step 2: Consequences of integer division

   Integer division can cause product to never reach below k properly, leading to infinite loops or wrong counts.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Replacing '//' with '/' fixes product update and loop termination [OK]

Hint: Integer division breaks product update -> infinite loop [OK]

Common Mistakes:

• Using integer division instead of float
• Incorrect count increment

5. Suppose the problem is modified so you can pick cards from the start or end any number of times, including reusing cards multiple times (infinite picks allowed). Which approach correctly adapts to this variant?

hard

A. Use a dynamic programming approach to find the maximum sum of k picks allowing repeated cards from ends.

B. Use prefix sums only on the first k cards from the start, ignoring the end cards.

C. Use a greedy approach that always picks the card with the highest point value from either end until k picks are made.

D. Use the original sliding window approach on the middle subarray since it still finds the minimal subarray to exclude.

Solution

1. Step 1: Understand the new constraint

   Reusing cards means picks are not limited to unique cards; the problem becomes unbounded with repetition allowed.

2. Step 2: Recognize sliding window limitation

   The sliding window approach assumes each card can be picked once; it fails with infinite reuse.

3. Step 3: Use dynamic programming

   DP can model picking cards with repetition from ends, tracking maximum sums for each number of picks.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP handles repeated picks; sliding window does not [OK]

Hint: Reusing cards breaks sliding window; DP needed [OK]

Common Mistakes:

• Assuming sliding window still works with repeated picks
• Greedy fails to consider future picks
• Ignoring picks from the end