DMITRII’s Substack

Share this post

Leetcode daily # 4.05.2023

dmitriisamoilenko.substack.com

Leetcode daily # 4.05.2023

[649. Dota2 Senate]

DMITRII SAMOILENKO
May 4, 2023
Share
Share this post

Leetcode daily # 4.05.2023

dmitriisamoilenko.substack.com

4.05.2023

649. Dota2 Senate medium

fun predictPartyVictory(senate: String): String {
    val queue = ArrayDeque<Char>()
        senate.forEach { queue.add(it) }
        var banR = 0
        var banD = 0
        while (true) {
            var haveR = false
            var haveD = false
            repeat(queue.size) {
                val c = queue.poll()
                if (c == 'R') {
                    haveR = true
                    if (banR > 0) banR--
                    else {
                        queue.add(c)
                        banD++
                    }
                } else {
                    haveD = true
                    if (banD > 0) banD--
                    else {
                        queue.add(c)
                        banR++
                    }
                }
            }
            if (!haveR) return "Dire"
            if (!haveD) return "Radiant"
        }
    }

blog post

Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/202

Intuition

One can ban on any length to the right.
We can just simulate the process, and it will take at most two rounds.

Approach

Use Queue and count how many bans are from the Radiant and from the Dire.

Complexity

  • Time complexity:
    O(n)

  • Space complexity:
    O(n)

Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.

Share
Share this post

Leetcode daily # 4.05.2023

dmitriisamoilenko.substack.com
Previous
Next
Comments
Top
New

No posts

Ready for more?

© 2023 DMITRII SAMOILENKO
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing