Problem Explanation: Given an unsorted array of integers, write a function to find the smallest positive integer that is not present in the array.
Example:
Input: [3, 5, -1, 1, 2, 8, 10, -7, 9, 4, 6]
Output: 7
Input: [1, 2, 3]
Output: 4
Expected Time and Space Complexity: The time complexity of the algorithm should be O(n), where n is the length of the input array. The space complexity should be O(1), meaning that the algorithm should not use any additional data structures or use constant amount of additional space.
Constraints:
- The input array can contain duplicates and negative numbers.
- The range of input integers is [-10^6, 10^6].
- The length of the input array can be up to 10^6.
Kotlin Solution :
Kotlin
fun findSmallestPositiveInteger(nums: IntArray): Int {
val n = nums.size
// Marking the presence of elements in the array
val presence = BooleanArray(n + 1) { false }
// Only marking positive elements and ignoring negative elements
for (i in 0 until n) {
if (nums[i] > 0 && nums[i] <= n) {
presence[nums[i]] = true
}
}
// Finding the smallest positive integer not present in the array
for (i in 1..n) {
if (!presence[i]) {
return i
}
}
// If all positive integers are present, the smallest missing positive integer is n + 1
return n + 1
}
fun main() {
val nums = intArrayOf(3, 5, -1, 1, 2, 8, 10, -7, 9, 4, 6)
println(findSmallestPositiveInteger(nums)) // Output: 7
val nums2 = intArrayOf(1, 2, 3)
println(findSmallestPositiveInteger(nums2)) // Output: 4
}