LeetCode in Kotlin

3479. Fruits Into Baskets III

Medium

You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the ith type of fruit, and baskets[j] represents the capacity of the jth basket.

From left to right, place the fruits according to these rules:

Return the number of fruit types that remain unplaced after all possible allocations are made.

Example 1:

Input: fruits = [4,2,5], baskets = [3,5,4]

Output: 1

Explanation:

Since one fruit type remains unplaced, we return 1.

Example 2:

Input: fruits = [3,6,1], baskets = [6,4,7]

Output: 0

Explanation:

Since all fruits are successfully placed, we return 0.

Constraints:

Solution

import kotlin.math.max

class Solution {
    fun numOfUnplacedFruits(fruits: IntArray, baskets: IntArray): Int {
        val n = baskets.size
        var size = 1
        while (size < n) {
            size = size shl 1
        }
        val seg = IntArray(2 * size)
        for (i in 0..<n) {
            seg[size + i] = baskets[i]
        }
        for (i in n..<size) {
            seg[size + i] = 0
        }
        for (i in size - 1 downTo 1) {
            seg[i] = max(seg[i shl 1].toDouble(), seg[i shl 1 or 1].toDouble()).toInt()
        }
        var ans = 0
        for (f in fruits) {
            if (seg[1] < f) {
                ans++
                continue
            }
            var idx = 1
            while (idx < size) {
                if (seg[idx shl 1] >= f) {
                    idx = idx shl 1
                } else {
                    idx = idx shl 1 or 1
                }
            }
            update(seg, idx - size, 0, size)
        }
        return ans
    }

    private fun update(seg: IntArray, pos: Int, `val`: Int, size: Int) {
        var i = pos + size
        seg[i] = `val`
        i /= 2
        while (i > 0) {
            seg[i] = max(seg[i shl 1].toDouble(), seg[i shl 1 or 1].toDouble()).toInt()
            i /= 2
        }
    }
}