904. Fruit Into Baskets

 

904. Fruit Into Baskets

Medium

---

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

 

이 문제는 2개의 바구니에 과일을 최대 몇 개 담을 수 있는지 확인하는 문제입니다.

이때 각 바구니에는 한 가지 타입의 과일을 담을 수 있으며

각 과일의 타입은 fruits[i] 입니다.

ex) [1,2,3,4,1]의 fruits가 있다면 여기서 타입의 개수는 4개입니다. 

 

처음에는 brute force 방법으로 풀었으나 매번 left에서 바구니 개수가

초과할 때까지 더하다 보니 시간 초과가 발생했습니다.

var totalFruit = function(fruits) {
     let ans = 0
    
     for(let left=0; left<fruits.length; left++){
         let right = left
         const basket = new Set()
        
         while(right < fruits.length){
             if(!basket.has(fruits[right]) && basket.size === 2) break
            
             basket.add(fruits[right])
             right++ 
         }

         ans = Math.max(ans, right - left)
     }
     return ans
}

 

그래서 조금 더 효율적인 sliding window 방법으로 다시 풀었습니다.

 

의사 코드

1. 과일의 타입과 개수를 기록할 basket, window의 시작과 끝을 나타내는 left, right, 최댓값 max를 초기화해 줍니다.
2. fruits.length까지 fruits 배열을 순회한다.
   1.  basket에 과일의 타입과 개수를 할당해 준다.
   2. basket의 사이즈가 2보다 큰 경우 즉 과일 타입의 개수가 2개 이상인 경우 while문을 통해 하나가 될 때까지 왼쪽(sliding window의 시작 부분)에서 지워준다.
   3. max 업데이트
3. return max

 

/**
 * @param {number[]} fruits
 * @return {number}
 */
var totalFruit = function(fruits) {
    const basket = new Map()
    let left = 0, right;
    let max = 0 
    
    for(right=0; right < fruits.length; right++){
        basket.set(fruits[right], (basket.get(fruits[right])||0)+1)
        
        // type이 2개 이상이면 2개가 될때까지 지워준다.
        while(basket.size > 2){
            basket.set(fruits[left], basket.get(fruits[left]) - 1)
            
            if(basket.get(fruits[left]) === 0){
                basket.delete(fruits[left])
            }
            left++
        }
        
        max = Math.max(max, right - left + 1)
    }
    
    return max
};