Fruit Into Baskets
Medium About 20 min Free, no account needed
Longest stretch of trees using at most two fruit types.
The brief
You walk along a row of fruit trees, fruits[i] being the type at tree i.
You carry two baskets, each holding one type only. Starting at any tree and
moving right, you pick one fruit per tree until a third type appears.
Return the maximum number of fruits you can pick, i.e. the longest contiguous window containing at most two distinct values.
The obvious approach re-walks from every starting tree, O(n2) on long uniform stretches, like the hidden 100,000-tree orchard, so it's too slow. You will need a single pass over the trees, O(n).
Starter code
using System;
public class Solution
{
// TODO: return the length of the longest contiguous window with at most two distinct values.
public int TotalFruit(int[] fruits)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
Related guides
What it practices
- Sliding window
- Grow and shrink a contiguous range while maintaining its state incrementally.
Related katas
- Find All Anagram Start Indices Medium Free Every position where an anagram of the pattern begins.
- Longest Repeating Character Replacement Medium Free Longest uniform run you can create with k character replacements.
- Minimum Size Subarray Sum Medium Free The shortest window of positive numbers reaching a target sum.
- Longest Rising Streak Easy Free Measure a consecutive telemetry climb without rescanning every possible starting point.