LeetCode Entry

2483. Minimum Penalty for a Shop

29.08.2023 medium 2023 kotlin

First index of minimum penalty in array, penalty 'Y'-> 1, 'N' -> -1

2483. Minimum Penalty for a Shop medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/323

Problem TLDR

First index of minimum penalty in array, penalty ‘Y’-> 1, ‘N’ -> -1

Intuition

Iterate from the end and compute the suffix penalty.

Approach

Suffix penalty is a difference between p_closed - p_opened.

Complexity

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

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

Code


    fun bestClosingTime(customers: String): Int {
      var p = 0
      var iMin = customers.length
      var pMin = 0
      for (i in customers.lastIndex downTo 0) {
        if (customers[i] == 'Y') p++ else p--
        if (p <= pMin) {
          iMin = i
          pMin = p
        }
      }
      return iMin
    }