LeetCode Entry

904. Fruit Into Baskets

7.02.2023 medium 2023 kotlin

careful with corner cases

904. Fruit Into Baskets medium

blog post

    fun totalFruit(fruits: IntArray): Int {
        if (fruits.size <= 2) return fruits.size
        var type1 = fruits[fruits.lastIndex]
        var type2 = fruits[fruits.lastIndex - 1]
        var count = 2
        var max = 2
        var prevType = type2
        var prevTypeCount = if (type1 == type2) 2 else 1
        for (i in fruits.lastIndex - 2 downTo 0) {
            val type = fruits[i]
            if (type == type1 || type == type2 || type1 == type2) {
                if (type1 == type2 && type != type1) type2 = type
                if (type == prevType) prevTypeCount++
                else prevTypeCount = 1
                count++
            } else {
                count = prevTypeCount + 1
                type2 = type
                type1 = prevType
                prevTypeCount = 1
            }
            max = maxOf(max, count)
            prevType = type
        }
        return max
    }

Join daily telegram

https://t.me/leetcode_daily_unstoppable/111

Intuition

We can scan fruits linearly from the tail and keep only two types of fruits.

Approach

• careful with corner cases

  Complexity

• Time complexity: \(O(n)\)
• Space complexity: \(O(1)\)