LeetCode Entry

1980. Find Unique Binary String

16.11.2023 medium 2023 kotlin

First absent number in a binary string array

1980. Find Unique Binary String medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/406

Problem TLDR

First absent number in a binary string array

Intuition

The naive solution would be searching in all the numbers 0..2^n. However, if we convert strings to ints and sort them, we can do a linear scan to detect first absent.

Approach

  • use padStart to convert back

Complexity

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

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

Code


    fun findDifferentBinaryString(nums: Array<String>): String {
      var next = 0
      for (x in nums.sorted()) {
        if (x.toInt(2) > next) break
        next++
      }
      return next.toString(2).padStart(nums[0].length, '0')
    }