LeetCode Entry

1921. Eliminate Maximum Number of Monsters

07.11.2023 medium 2023 kotlin

Count possible 1-minute kills in a game of dist[] targets falling with speed[]

1921. Eliminate Maximum Number of Monsters medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/396

Problem TLDR

Count possible 1-minute kills in a game of dist[] targets falling with speed[]

Intuition

Each target has it’s own arrival time_i = dist[i] / speed[i]. We must prioritize targets by it.

Approach

Let’s use Kotlin API:

  • indices
  • sortedBy
  • withIndex
  • takeWhile
  • time becomes just a target index

Complexity

  • Time complexity: \(O(nlog(n))\)

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

Code


    fun eliminateMaximum(dist: IntArray, speed: IntArray): Int =
      dist.indices.sortedBy { dist[it].toDouble() / speed[it] }
      .withIndex()
      .takeWhile { (time, ind) -> speed[ind] * time < dist[ind] }
      .count()