Summary of "BS-16. Kth Missing Positive Number | Maths + Binary Search"

Summary of “BS-16. Kth Missing Positive Number | Maths + Binary Search”

This video explains how to solve the problem of finding the kth missing positive number in an increasing array of positive integers using binary search. It is part of a binary search playlist in a DSA course.

---

Problem Statement

• Given a sorted (increasing) array of positive integers.
• Find the kth missing positive integer that does not appear in the array.

Example:

• Array: [2, 3, 4, 7, 11], k = 5
• Positive numbers start from 1: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
• Missing numbers are: 1, 5, 6, 8, 9, 10, …
• The 5th missing number is 9 → return 9.

---

Key Concepts and Lessons

1. Understanding the Problem

• The array is sorted and contains positive integers.
• Missing numbers are positive integers not in the array but less than or equal to the last element or beyond.
• If the array starts at a number greater than 1, the missing numbers include all positive integers before the start of the array.

2. Brute Force Approach

• Iterate from 1 upwards.
• For each number, check if it is missing in the array.
• Count missing numbers until the kth missing number is found.
• Time complexity: O(n)
• Space complexity: O(1)

3. Motivation for Binary Search

• Since the array is sorted, a linear search is not optimal.
• Binary search can reduce time complexity from O(n) to O(log n).
• However, typical binary search cannot be applied directly because:
  • We are searching for a missing number (not present in the array).
  • We cannot binary search for the number itself.

4. Applying Binary Search on the Index Range

• Define a function to calculate how many numbers are missing up to a given index.
• Missing count at index i = arr[i] - (i + 1)
  • This works because if no numbers were missing, arr[i] should be exactly i + 1.
• Use binary search on the index range to find the smallest index where the number of missing numbers is at least k.

5. Binary Search Algorithm Steps

• Initialize low = 0, high = n - 1.
• While low <= high:
  • Calculate mid = low + (high - low) // 2.
  • Calculate missing numbers till mid: missing = arr[mid] - (mid + 1).
  • If missing < k, move low to mid + 1 (search right half).
  • Else move high to mid - 1 (search left half).
• After the loop, low will be the smallest index where missing numbers are at least k.

6. Calculating the kth Missing Number

• After binary search, the kth missing number can be found by: answer = low + k

• Explanation:

  • low is the number of elements before the missing number’s position.
  • Adding k accounts for the missing numbers.

7. Edge Cases

• If kth missing number is before the first element (e.g., array starts at 5 and k=4), the answer is just k.
• The binary search handles cases where high might become -1 (kth missing number before the first element).

---

Detailed Methodology / Instructions

1. Understand the array and k.

2. Define a function to calculate missing numbers till index i: missing(i) = arr[i] - (i + 1)

3. Set binary search boundaries: low = 0, high = len(arr) - 1

4. Perform binary search:

   • While low <= high:
     • mid = low + (high - low) // 2
     • Calculate missing = arr[mid] - (mid + 1)
     • If missing < k, low = mid + 1
     • Else high = mid - 1

5. After binary search ends, the kth missing number is: answer = low + k

6. Return answer.

---

Time and Space Complexity

• Time Complexity: O(log n) due to binary search.
• Space Complexity: O(1).

---

Additional Notes

• The video explains the intuition behind the formula for missing numbers.
• It discusses why typical binary search on values or answers does not work directly.
• The presenter derives the formula for the answer and explains the edge cases.
• Code snippets and example walkthroughs are provided.
• Links to code in multiple languages (C++, Java, Python, JavaScript) are available in the video description.

---

Speakers / Sources

• The video features a single speaker, commonly known as Striver, a popular educator in competitive programming and data structures & algorithms.

---

This summary captures the core ideas, the problem-solving approach, and the binary search methodology to find the kth missing positive number efficiently.

Category

Educational

---

Share this summary

Share on X/Twitter Share on Facebook Share on LinkedIn Share on Reddit Share on WhatsApp Share on Telegram

---

Is the summary off?

If you think the summary is inaccurate, you can reprocess it with the latest model.

Reprocess summary

Video