LeetCode Entry

1792. Maximum Average Pass Ratio

01.09.2025 medium 2025 kotlin

Max avg ratio after assigning extra to ratios

1792. Maximum Average Pass Ratio medium blog post substack youtube

1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1099

Problem TLDR

Max avg ratio after assigning extra to ratios #medium

Intuition

Greedy works: for each extra choose the class that will make the most difference.

    //[1,2],[3,5],[2,2]]
    // 2/3 vs 3/5
    // 10/15  9/15
    //
    // 2/3 4/6 2/2   vs   3/4 3/5 2/2
    // a/b c/d
    // a+1/b+1 +c/d   vs   a/b + c+1/d+1

Approach

  • we don’t have to validate in the end; choose only available numbers
  • there is a bitmask optimization
  • we can prioritize rows, cols or subs with more numbers filled

Complexity

  • Time complexity: \(O(nlogn)\)

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

Code


// 332ms
    fun maxAverageRatio(cls: Array<IntArray>, ext: Int): Double {
        val q = PriorityQueue<IntArray>(compareBy { (a,b) -> 1.0*a/b-1.0*(a+1)/(b+1)})
        q += cls; for (e in 1..ext) q += q.poll().also { ++it[0]; ++it[1] }
        return cls.sumOf { (a,b) -> 1.0*a/b } / cls.size
    }