LeetCode-in-Scala.github.io

41. First Missing Positive

Hard

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

Example 1:

Input: nums = [1,2,0]

Output: 3

Example 2:

Input: nums = [3,4,-1,1]

Output: 2

Example 3:

Input: nums = [7,8,9,11,12]

Output: 1

Constraints:

• 1 <= nums.length <= 5 * 105
• -231 <= nums[i] <= 231 - 1

Solution

import scala.annotation.tailrec

object Solution {
    def firstMissingPositive(nums: Array[Int]): Int = {
        for (i <- nums.indices) {
            if (nums(i) <= 0 || nums(i) > nums.length || nums(i) == i + 1) {
                // Continue the loop
            } else {
                dfs(nums, nums(i))
            }
        }

        for (i <- nums.indices) {
            if (nums(i) != i + 1) {
                return i + 1
            }
        }

        nums.length + 1
    }

    @tailrec
    private def dfs(nums: Array[Int], value: Int): Unit = {
        if (value <= 0 || value > nums.length || value == nums(value - 1)) {
            return
        }
        val temp = nums(value - 1)
        nums(value - 1) = value
        dfs(nums, temp)
    }
}

This site is open source. Improve this page.