Exercise 2: Find First Missing Positive (simple version)
Problem Statement
Given an array of integers, create a function `firstMissingPositive(arr)` that returns the smallest missing positive integer.
Constraint: simple approach allowed (O(n log n) ok).
Sample Output:
firstMissingPositive([3, 4, -1, 1]) => 2 firstMissingPositive([1, 2, 3]) => 4
Solution
const firstMissingPositive = (arr) => {
const set = new Set(arr.filter((n) => Number.isInteger(n) && n > 0));
for (let x = 1; ; x++) if (!set.has(x)) return x;
};Explanation
Overall Goal:
- Array me sabse chhota missing positive integer find karna.
- Example: [3, 4, -1, 1] → missing: 2 (kyunki 1, 3, 4 hai, lekin 2 nahi).
Line 1: Function header
const firstMissingPositive = (arr) => {→ function jo array lega.
Line 2: Filter aur Set creation
const set = new Set(arr.filter((n) => Number.isInteger(n) && n > 0));arr.filter((n) => ...)→ array se sirf valid positive integers filter karte hain:Number.isInteger(n)→ kya ye integer hai? (decimal nahi).n > 0→ kya ye positive hai? (negative/zero nahi).new Set(...)→ filtered array ko Set me convert:- Set fast lookup deta hai (O(1) vs O(n) for array).
- Duplicates automatically remove ho jate hain.
Line 3: Incremental search
for (let x = 1; ; x++) if (!set.has(x)) return x;- Infinite loop
for (let x = 1; ; x++)→ 1 se start, har iteration me x++: - Condition missing hai (middle part empty), to infinite loop.
- Lekin
returnstatement loop ko break karega. !set.has(x)→ kyaxSet me nahi hai?- Agar missing hai →
return x(ye hi answer hai). - Agar present hai → next iteration (x++).
Example:
- Input:
[3, 4, -1, 1] - Filter:
[3, 4, 1](positive integers only). - Set:
{1, 3, 4} - Loop: x=1 → Set me hai → continue, x=2 → Set me nahi → return 2.
Real world:
- Database IDs me gaps find karna.
- Sequence validation me missing numbers detect karna.