Skip to content

022 — First Missing Positive

Source

  • Original source: Classic in-place index-marking exercise
  • Platform: LeetCode — https://leetcode.com/problems/first-missing-positive/
  • Topic: array / in-place hashing
  • Difficulty: Hard
  • Pattern: in-place index marking (cyclic placement)
  • Basic idea inherited from: array-কেই নিজের hash map বানানোর trick — মান v-কে index v-1-এ বসানো

1. Problem in simple words

একটা integer array nums দেওয়া (ধনাত্মক, ঋণাত্মক, শূন্য — যেকোনো কিছু থাকতে পারে)। সবচেয়ে ছোট যে ধনাত্মক পূর্ণসংখ্যা (1, 2, 3, ...) array-তে নেই, সেটা বের করো। শর্ত: O(n) সময় এবং O(1) extra space — অর্থাৎ আলাদা set/array বানানো যাবে না।

nums = [3, 4, -1, 1]
আছে: 1, 3, 4 ; নেই: 2  ->  উত্তর 2

2. Which basic idea does this inherit from?

ভিত একটা চালাকি: array-কেই নিজের hash map বানাও। আলাদা hash set হলে membership O(1)-এ দেখা যেত, কিন্তু সেটা O(n) extra space। বদলে আমরা মানটাকে তার "ঘরে" রাখি — মান v (যদি 1..n-এর মধ্যে) বসে index v-1-এ। তাহলে index নিজেই বলে দেয় কোন সংখ্যা উপস্থিত। এটা hashing-এর সবচেয়ে minimal রূপ; গভীরে: ../../05-hashing/।

3. What is the hidden math or logic?

লুকানো logic pigeonhole principle: n-দৈর্ঘ্যের array-তে সবচেয়ে ছোট অনুপস্থিত ধনাত্মক সংখ্যা সবসময় 1 থেকে n+1-এর মধ্যেই থাকবে। কেন? কারণ nটা ঘরে বড়জোর 1..n সবগুলো ধরা সম্ভব; সব ধরলে উত্তর n+1, নইলে 1..n-এর কোনোটা বাদ পড়েছে। তাই n-এর বাইরের বা অধনাত্মক মান অগ্রাহ্য করা যায় — শুধু 1..n রাখার চেষ্টা করি।

4. Which data structure is needed?

কোনো নতুন structure নয় — input array nums নিজেই data structure। প্রতিটা মান v ∈ [1, n]-কে তার সঠিক ঘরে (index v-1) swap করে বসাই (cyclic sort)। সাথে শুধু কয়েকটা integer। মোট O(1) extra space।

5. Why this data structure fits

প্রশ্নটা আসলে "কোন সংখ্যা উপস্থিত?" — যা একটা membership query, hash-এর কাজ। কিন্তু value-গুলো ছোট পরিসরে (1..n) সীমাবদ্ধ বলে আমরা value-কেই index বানিয়ে array-টাকে perfect hash table হিসেবে ব্যবহার করতে পারি: ঘর i-তে যদি i+1 থাকে, তবে i+1 উপস্থিত। array mutable বলে in-place এই বিন্যাস সম্ভব, extra memory ছাড়াই।

6. Real-life analogy

ভাবো ক্লোকরুমে 1 থেকে n নম্বরের হুক, আর প্রতিটা কোটে একটা টোকেন-নম্বর লেখা। নিয়ম: টোকেন k-ওয়ালা কোট হুক k-তেই ঝুলবে। সবাইকে নিজ নিজ হুকে সাজিয়ে দাও (যাদের নম্বর 1..n)। শেষে হুকগুলো বাঁ থেকে দেখো — প্রথম যে হুকে ভুল/অনুপস্থিত কোট, সেই হুক-নম্বরই হারানো প্রথম টোকেন।

7. Visual explanation

nums = [3, 4, -1, 1] (n=4) — প্রতিটা মান v-কে index v-1-এ swap:

শুরু:        [ 3,  4, -1,  1]
i=0: 3 -> idx2 (swap):  [-1,  4,  3,  1]   (idx0=-1, range বাইরে, থামো)
i=1: 4 -> idx3 (swap):  [-1,  1,  3,  4]   1 -> idx0 (swap): [ 1, -1, 3, 4]  থামো
i=2: 3 ঠিক জায়গায় (idx2);  i=3: 4 ঠিক জায়গায় (idx3)

সাজানো:      [ 1, -1,  3,  4]
scan: idx0=1 ✓, idx1=-1 ✗ -> অনুপস্থিত 2

8. Example input and output

Input : [1, 2, 0]        -> 3
Input : [3, 4, -1, 1]    -> 2
Input : [7, 8, 9, 11, 12]-> 1   (1-ই নেই)

Edge case 1 (সব আছে): [1]  -> 2   (উত্তর n+1)
Edge case 2 (খালি):   []   -> 1

9. Brute force thinking

প্রথম সরল চিন্তা: সব সংখ্যা একটা hash set-এ ভরো, তারপর 1, 2, 3, ... করে গুনতে গুনতে যেটা set-এ নেই সেটাই উত্তর।

seen = set(nums)
i = 1
while i in seen:
    i += 1
return i

10. Why brute force is slow

এটা O(n) time-এ ঠিক উত্তর দেয়, কিন্তু hash set-টা O(n) extra space নেয় — অথচ problem কড়াভাবে O(1) extra চায়। চালাকিটা হলো: আলাদা set-এর বদলে input array-র index-কেই "এই সংখ্যা আছে কিনা"-র চিহ্ন হিসেবে ব্যবহার করা, তাই বাড়তি memory লাগে না।

11. Key observation

দুটো observation: (১) উত্তর সবসময় 1..n+1-এর মধ্যে (pigeonhole), তাই 1..n-এর বাইরের মান অপ্রাসঙ্গিক। (২) মান v ∈ [1,n]-কে index v-1-এ বসিয়ে দিলে, পরে শুধু বাঁ-থেকে scan করে প্রথম যে index i-তে nums[i] != i+1, সেই i+1-ই হারানো সংখ্যা — index নিজেই membership বলে দেয়।

12. Optimized intuition

দুই pass:

  • Pass 1 (placement): প্রতিটা i-তে যতক্ষণ nums[i] মান 1..n-এর মধ্যে এবং নিজের সঠিক ঘরে (nums[nums[i]-1] != nums[i]) নেই, ততক্ষণ swap করে তাকে index nums[i]-1-এ পাঠাও (cyclic)। ডুপ্লিকেট/range-বাইরের মান এমনিতেই এড়ানো হয়।
  • Pass 2 (scan): বাঁ থেকে দেখো প্রথম কোন index i-তে nums[i] != i+1 — উত্তর i+1। সব মিললে উত্তর n+1।

মোট O(n): প্রতিটা swap অন্তত একটা সংখ্যাকে তার চিরস্থায়ী ঘরে বসায়, তাই মোট swap ≤ n।

13. Thinking tweak

মোচড়: "membership জানতে আলাদা set লাগবেই" ধারণা ছাড়ো। ভাবো "মানটাকে তার নিজের ঘরে (v → index v-1) বসিয়ে দিই — তখন array-র index-ই hash key, আর ঘরে কী আছে সেটাই value-র উপস্থিতি বলে দেয়।" এতে hash table আর input array এক হয়ে যায়, extra space 0।

14. Step-by-step dry run

Input [1, 2, 0] (n=3):

  1. i=0: nums[0]=1, range-এ, nums[0]==1 ঠিক জায়গায় → থামো।
  2. i=1: nums[1]=2, nums[1]==2 ঠিক জায়গায় → থামো।
  3. i=2: nums[2]=0, range-এর বাইরে (1..3 নয়) → থামো। array [1,2,0]।
  4. scan: idx0=1✓, idx1=2✓, idx2=0 ≠ 3 → উত্তর 3।

15. Python solution

def first_missing_positive(nums):
    n = len(nums)
    for i in range(n):
        # nums[i] কে তার সঠিক ঘরে (index nums[i]-1) পাঠাও
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            correct = nums[i] - 1
            nums[i], nums[correct] = nums[correct], nums[i]
    for i in range(n):
        if nums[i] != i + 1:          # প্রথম বেমানান ঘর
            return i + 1
    return n + 1                      # 1..n সব আছে -> উত্তর n+1

# ---- tests ----
assert first_missing_positive([1, 2, 0]) == 3
assert first_missing_positive([3, 4, -1, 1]) == 2
assert first_missing_positive([7, 8, 9, 11, 12]) == 1
assert first_missing_positive([1]) == 2      # সব আছে -> n+1
assert first_missing_positive([]) == 1       # খালি
print("সব test pass!")

16. Line-by-line code explanation

  • n = len(nums) — পরিসর 1..n; এর বাইরের কিছু লাগবে না।
  • while 1 <= nums[i] <= n and nums[nums[i]-1] != nums[i]: — মান range-এ আছে এবং এখনো নিজের ঘরে নেই, তবেই swap; দ্বিতীয় শর্ত duplicate-এ অসীম loop ঠেকায়।
  • correct = nums[i] - 1 — মান v-এর প্রাপ্য index v-1।
  • nums[i], nums[correct] = nums[correct], nums[i] — swap করে মানটাকে তার ঘরে পাঠাই; নতুন আসা মান নিয়ে while আবার পরীক্ষা করে।
  • দ্বিতীয় loop — প্রথম যে index-এ nums[i] != i+1, সেই i+1 অনুপস্থিত।
  • return n + 1 — 1..n সব সাজানো থাকলে সবচেয়ে ছোট অনুপস্থিত n+1।

17. Output walkthrough

[1,2,0] → placement-এর পর [1,2,0], idx2 বেমানান → 3, assert pass। [3,4,-1,1] → সাজানোর পর [1,-1,3,4], idx1 বেমানান → 2; [7,8,9,11,12] → সব range-বাইরে, কিছুই বসে না, idx0 ≠ 1 → 1; [1] → সব ঠিক, n+1=2; [] → 0+1=1। শেষে print: সব test pass!।

18. Time complexity

O(n) — বাইরের loop n বার; ভেতরের while-এর প্রতিটা সফল swap একটা সংখ্যাকে তার চিরস্থায়ী ঘরে বসায়, তাই সব মিলিয়ে swap সংখ্যা ≤ n। দ্বিতীয় scan O(n)।

19. Space complexity

O(1) — শুধু কয়েকটা integer; input array-র ভেতরেই সব কাজ, কোনো extra set/array নেই।

20. Common mistakes

  • while-এর duplicate-গার্ড (nums[nums[i]-1] != nums[i]) বাদ দেওয়া — একই মান দুবার থাকলে অসীম swap-loop।
  • swap-এ ভুল ক্রমে assignment (Python tuple-swap ঠিক, কিন্তু temp দিয়ে করলে আগে nums[i] বদলে ফেললে correct-এর হিসাব নষ্ট)।
  • range-শর্ত (1 <= nums[i] <= n) ভুলে negative/বড় মান নিয়েও swap করতে যাওয়া — index error বা ভুল।
  • i+1-এর বদলে i ফেরত দেওয়া — index 0-based, কিন্তু সংখ্যা 1-based।

21. Which basic problem this inherits from

ভিত্তি: "array-কেই hash map বানানো" (value→index placement), যা cyclic-sort ঘরানার core। membership-by-index idea-র জন্য ../../05-hashing/ দেখো; আর pigeonhole-এর গণিত ../../01-math-based-programming-fundamentals/03-counting-combinatorics/-এ। chapter-এর ../patterns.md-এ এটা index-marking-এর hard প্রতিনিধি।

22. Similar harder problems

23. Pattern learned

In-place index marking (array as hash): value ছোট পরিসরে (1..n) থাকলে আলাদা set না বানিয়ে মানটাকে তার নিজের ঘরে (v→v-1) বসাও বা চিহ্নিত করো; index নিজেই membership বলে — O(n) time, O(1) space।

24. Final summary

ভবিষ্যতের আমাকে: "first missing positive = মানকে নিজ ঘরে (v→index v-1) cyclic swap করো; প্রথম যেখানে nums[i] != i+1, সেটাই উত্তর; সব ঠিক হলে n+1।" "O(1) space-এ missing/duplicate খোঁজো" দেখলেই array-as-hash index-marking মনে করবে — pigeonhole-এ উত্তর 1..n+1।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।