Fruit Into Baskets

Fruit Into Baskets is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.

Problem statement

You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

- You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.

- Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.

- Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array fruits, return the maximum number of fruits you can pick.

Example 1:

Input: fruits = [1,2,1] Output: 3 Explanation: We can pick from all 3 trees.

Example 2:

Input: fruits = [0,1,2,2] Output: 3 Explanation: We can pick from trees [1,2,2]. If we had started at the first tree, we would only pick from trees [0,1].

Example 3:

Input: fruits = [1,2,3,2,2] Output: 4 Explanation: We can pick from trees [2,3,2,2]. If we had started at the first tree, we would only pick from trees [1,2].

Constraints:

- 1 <= fruits.length <= 105

- 0 <= fruits[i] < fruits.length

Topics and companies

Topics: Array, Hash Table, Sliding Window.

Reported in interviews at Google, Akamai.

How to practise Fruit Into Baskets on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open Fruit Into Baskets in the code editor, or read the Fruit Into Baskets editorial for a worked solution with its approach and complexity analysis.

Where Fruit Into Baskets sits in the DSA pattern sheet

• Sliding Window pattern guide
• Variable Size (Condition-Based) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Fruit Into Baskets

Other problems that use the same Variable Size (Condition-Based) and Sliding Window techniques:

• Contains Duplicate II — Easy, same subpattern
• Continuous Subarrays — Medium, same subpattern
• Find Longest Special Substring That Occurs Thrice I — Medium, same subpattern
• Frequency of the Most Frequent Element — Medium, same subpattern
• Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit — Medium, same subpattern
• Longest Repeating Character Replacement — Medium, same subpattern