Skip to content

The Missing Ticket Number

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 12 Session 2 (Click for link to problem statements)

The Missing Ticket Number

A raffle drum holds an unsorted array nums of integers, some negative or duplicated. You need the smallest positive integer that is not present, using O(n) time and constant extra space.

Return that smallest missing positive integer.

def first_missing_positive(nums):
    pass

Problem Highlights

  • 💡 Difficulty: Hard
  • ⏰ Time to complete: 30-40 mins
  • 🛠️ Topics: Arrays, Cyclic Sort, In-Place Index Marking

1: U-nderstand

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

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Q: What values in nums actually matter for the answer?
    • A: Only the positive integers in the range 1 to n (where n is the length of the array). Negatives, zeros, and values greater than n can never be the answer's "present" evidence, because the answer must lie between 1 and n + 1.
  • Q: Can we sort the array or use a hash set to track which numbers appear?
    • A: No. Sorting costs O(n log n) time and a hash set costs O(n) extra space. The constraints require O(n) time and constant extra space, so we must reuse the input array itself as our bookkeeping structure.
  • Q: What should we return if every ticket number from 1 to n is in the drum?
    • A: Return n + 1, the first positive integer past the end of the array.
HAPPY CASE
Input: nums = [1, 2, 0]
Output: 3
Explanation: 1 and 2 are present, so the smallest missing positive is 3.

Input: nums = [3, 4, -1, 1]
Output: 2
Explanation: 1 is present but 2 is not, so the answer is 2.

EDGE CASE
Input: nums = [7, 8, 9, 11, 12]
Output: 1
Explanation: No ticket numbered 1 exists in the drum, so the answer is 1.

Input: nums = [2, 2]
Output: 1
Explanation: Duplicates of 2 do not supply a 1, so the smallest missing positive is still 1.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Finding a Missing Number In-Place, we can consider the following approaches:

  • Cyclic Sort: When an array's meaningful values fall in the range 1 to n, we can swap each value v into its "home" index v - 1. After one pass, the first index whose value is out of place reveals the missing number.
  • Index Marking: Alternatively, use the sign of the value at index v - 1 as a "seen" flag for value v, which also achieves constant extra space.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use cyclic sort to place every value v with 1 <= v <= n at index v - 1, swapping repeatedly until the current slot holds either an out-of-range value or a value already in its home position. Then scan left to right: the first index i where nums[i] != i + 1 means ticket i + 1 is missing. If every slot is correct, the answer is n + 1.

1) Let n = length of nums.
2) For each index i from 0 to n - 1:
   a) While nums[i] is between 1 and n, and nums[i] is not already sitting
      at its home index (nums[nums[i] - 1] != nums[i]):
      - Swap nums[i] with nums[nums[i] - 1].
3) Scan i from 0 to n - 1:
   a) If nums[i] != i + 1, return i + 1.
4) If every index holds its home value, return n + 1.

⚠️ Common Mistakes

  • Writing the swap as nums[i], nums[nums[i] - 1] = ... — Python evaluates the left-hand targets after nums[i] changes, corrupting the swap. Save the target index first.
  • Using if instead of while in the placement step, which leaves values one swap short of home.
  • Forgetting the duplicate check (nums[nums[i] - 1] != nums[i]), causing an infinite swap loop when duplicates occupy each other's slots.
  • Ignoring the constant-space requirement and reaching for a hash set out of habit.

4: I-mplement

Implement the code to solve the algorithm.

def first_missing_positive(nums):
    n = len(nums)

    # Cyclic sort: place each value v in 1..n at index v - 1
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            correct = nums[i] - 1
            nums[i], nums[correct] = nums[correct], nums[i]

    # The first index whose value is out of place names the missing ticket
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1

    # All tickets 1..n are present
    return n + 1

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: nums = [1, 2, 0]

    • Cyclic sort leaves the array as [1, 2, 0]: 1 and 2 are already home, and 0 is out of range.
    • Scan: index 0 holds 1 ✓, index 1 holds 2 ✓, index 2 holds 0 ≠ 3.
    • Output: 3

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

    • Swaps: 3 goes to index 2 → [-1, 4, 3, 1]; 4 goes to index 3 → [-1, 1, 3, 4]; then 1 goes to index 0 → [1, -1, 3, 4].
    • Scan: index 0 holds 1 ✓, index 1 holds -1 ≠ 2.
    • Output: 2

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

    • Every value is greater than n = 5, so no swaps occur.
    • Scan: index 0 holds 7 ≠ 1.
    • Output: 1

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of elements in nums.

  • Time Complexity: O(N). Although the placement step contains a nested while loop, each swap moves one value into its final home position, so the total number of swaps across the whole array is at most N. The final scan is another O(N) pass.
  • Space Complexity: O(1) extra space. All bookkeeping happens inside the input array itself; only a few index variables are used.

Clone this wiki locally