Missing Integer - codepath/compsci_guides GitHub Wiki

Unit 3 Session 2 (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the smallest missing positive integer in the list [1, 2, 3, 4, 6, 7, 8]?
  • A: The smallest missing positive integer is 5.
• Q: Does the list always start at 1?
  • A: Yes, the list always starts at 1.
• Q: Are there any duplicate numbers in the list?
  • A: No, there are no duplicates in the list.
• Q: Is the list always sorted?
  • A: Yes, the list is always sorted from smallest to largest.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Iterate through the list and check if each element matches its index + 1. If it doesn't, return the index + 1. If all elements match, return the next integer after the last element.

1) Initialize an index variable `i` to 0.
2) Iterate through the list:
   - Check if the current element `nums[i]` equals `i + 1`.
   - If it does, move to the next index by incrementing `i`.
   - If it doesn't, return `i + 1` as the smallest missing positive integer.
3) If the loop completes, return `i + 1` as the smallest missing positive integer because all elements matched their expected values.

**⚠️ Common Mistakes**

- Not accounting for lists that are complete with no missing integers, in which case the next integer after the last element is the smallest missing positive integer.
- Assuming the list may contain duplicates or is unsorted, which is not the case here.
- Off-by-one errors when comparing the current element to `i + 1`.

## I-mplement

```python
def find_missing_positive(nums):
    i = 0
    while i < len(nums):
        if nums[i] == i + 1:
            i += 1
        else:
            return i + 1
    return i + 1