Why is the number on "find the smallest missing positive number in an N element array problem" always <= N + 1?

user_11375031 0
Viewed 213

Like for example the smallest missing number on these LeetCode examples below are always between 1 and N where N is the array size.
What is the proof of that?

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

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:

  • 0 <= nums.length <= 300
  • -231 <= nums[i] <= 231 - 1
arrays algorithm
1 Answers

This is due to the fact that you can't fit more integer than N integers in an array. If you fill it with all indexes with the smallest positive integers out there, of course, your answer will be N + 1, otherwise it will always be smaller or equal to N.

I think a few examples will explain it better than words

Array filled with 0s

[0,0,0]

The smallest missing positive integer for this one will be 1, thus smaller than the size of the array + 1.

Array filled sequentially with each index storing its value + 1

[1,2,3]

Here, the smallest missing positive integer will be 4, and it is equal to N + 1.

Array filled with bigger numbers

[100,101,102]

Here, the smallest missing positive integer is 1 and is of course smaller than the size of the array.

user_50506670
Related