LeetCode Entry

287. Find the Duplicate Number

19.09.2023 medium 2023 kotlin

Found duplicate in array, each value is in 1..

287. Find the Duplicate Number medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/344

Problem TLDR

Found duplicate in array, each value is in 1..<arr.size

Intuition

Hint: 4 2 2 2 2 ... 2 is also the case. What we can see, is that every value is in the 1..<arr.size range, so we can temporarly store the flag in here, then revert it back in the end.

    //   0 1 2 3 4  sz = 5
    //   3 1 3 4 2
    // 3       *
    // 1   *
    // 3       x
    //

Approach

For a flag we can just add some big value to the number, or make it negative, for example.

Let’s write it using some Kotlin’s API:

  • first
  • also - notice how it doesn’t require brackets

Complexity

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

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

Code


    fun findDuplicate(nums: IntArray) = nums.first { n ->
        nums[n % nums.size] >= nums.size
        .also { nums[n % nums.size] += nums.size }
      } % nums.size
      .also { for (j in nums.indices) nums[j] %= nums.size }