algoadvance

Leetcode 904. Fruit Into Baskets

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 i-th tree produces.

You want to collect as much fruit as possible, but there is a catch: You only have two baskets, and each basket can only hold a single type of fruit. However, each basket can hold an unlimited amount of fruit of its type.

Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the starting tree) while moving to the right. The goal is to move in such a way that you maximize the total amount of fruit you can collect.

Return the maximum number of fruits you can collect with the two baskets.

Clarifying Questions

  1. Q: Is the input array always non-empty? A: Yes, you can assume the array has at least one element.

  2. Q: Can the elements of the array be negative? A: No, the elements represent types of fruits, which are non-negative integers.

  3. Q: What if the fruits array has fewer than 2 types of fruits? A: You can collect all fruits in that case.

Strategy

The problem can be approached using the sliding window technique. We can use two pointers to maintain a window with at most two different types of fruits. Here are the steps:

  1. Use a hashmap to keep track of the count of each type of fruit in the current window.
  2. Expand the window by moving the right pointer. Add the current fruit to the hashmap.
  3. If the hashmap contains more than two types of fruits, move the left pointer to make the window valid again by removing fruits until we have only two types.
  4. Keep track of the maximum size of the window during the process.

Code

import java.util.HashMap;

public class Solution {
    public int totalFruit(int[] fruits) {
        if (fruits.length == 0) return 0;
        
        HashMap<Integer, Integer> fruitCount = new HashMap<>();
        int left = 0, right = 0, maxFruits = 0;

        while (right < fruits.length) {
            fruitCount.put(fruits[right], fruitCount.getOrDefault(fruits[right], 0) + 1);
            right++;

            while (fruitCount.size() > 2) {
                fruitCount.put(fruits[left], fruitCount.get(fruits[left]) - 1);
                if (fruitCount.get(fruits[left]) == 0) {
                    fruitCount.remove(fruits[left]);
                }
                left++;
            }

            maxFruits = Math.max(maxFruits, right - left);
        }

        return maxFruits;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] fruits1 = {1, 2, 1};
        int[] fruits2 = {0, 1, 2, 2};
        int[] fruits3 = {1, 2, 3, 2, 2};
        System.out.println(sol.totalFruit(fruits1)); // Output: 3
        System.out.println(sol.totalFruit(fruits2)); // Output: 3
        System.out.println(sol.totalFruit(fruits3)); // Output: 4
    }
}

Time Complexity

This solution optimizes both time and space by leveraging the sliding window technique and is effective for large input arrays.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI