আমার LeetCode 41 ওবসেশন: প্রথম অনুপস্থিত ধনাত্মক ধাঁধার একটি গভীর ডাইভ

লিটকোডের "ফার্স্ট মিসিং পজিটিভ" সমস্যা (নম্বর ৪১) আমার সাম্প্রতিক কোডিং আসক্তির কেন্দ্রবিন্দুতে পরিণত হয়েছে। এটি একটি ছদ্মবেশী সরল ধাঁধা যা আমার চিন্তাভাবনাকে গ্রাস করে ফেলেছে, আমাকে এর জটিলতা অন্বেষণ করতে এবং যতটা সম্ভব দক্ষ টাইপস্ক্রিপ্ট সমাধান তৈরি করতে প্রেরণা দিয়েছে। এই পোস্টটি কেবলমাত্র কোডিং ইন্টারভিউতে সফল হওয়ার বিষয় নয় (যদিও এটি একটি ভালো সুবিধা)। এটি সমস্যা সমাধানের বিশুদ্ধ আনন্দ, অপ্টিমাইজেশনের উত্তেজনা এবং দক্ষ কোডের মার্জিত সৌন্দর্যের সাথে সম্পর্কিত। এবং যেহেতু আমি একটু গণিতপ্রিয়, আমরা সমাধানের গাণিতিক ভিত্তির মধ্যেও তন্ন তন্ন করে দেখব।

সমস্যা: ভেড়ার পোশাকে একটা নেকড়ে

এই সমস্যাটি পূর্ণসংখ্যার একটি অবিন্যস্ত অ্যারে উপস্থাপন করে। আপনার কাজ: সবচেয়ে ছোটো অনুপস্থিত ধনাত্মক পূর্ণসংখ্যা খুঁজে বের করা। সহজ মনে হচ্ছে? আবার ভাবুন। O(n) সময় এবং O(1) স্পেস জটিলতার নিয়ন্ত্রণ এই প্রতীতিতে সহজ কাজটিকে একটি চ্যালেঞ্জিং অ্যালগরিদমিক ধাঁধায় রূপান্তরিত করে।

প্রাথমিক সংগ্রাম: ব্রুট ফোর্স ফাঁদ

আমার প্রাথমিক প্রচেষ্টাগুলির মধ্যে ছিল সাজানো (O(n) সময়ের সীমা লঙ্ঘন করে) এবং হ্যাশ সেট (O(1) স্পেস সীমা অতিক্রম করে)। স্পষ্টতই, আরও উন্নত পদ্ধতির প্রয়োজন ছিল।

ইউরেকা মুহূর্ত: ইন-প্লেস ট্রান্সফরমেশন

মূল অন্তর্দৃষ্টি ছিল এই বুঝতে পারা যে আমি ইনপুট অ্যারেটিকে নিজেই একটি হ্যাশ টেবিল হিসেবে ব্যবহার করতে পারি। উপাদানগুলিকে পুনর্বিন্যাস করে, আমি সংখ্যা x কে সূচক x - 1 এ রাখতে পারি (যদি 1 ≤ x ≤ n হয়, যেখানে n হল অ্যারের দৈর্ঘ্য)। এই ইন-প্লেস ট্রান্সফরমেশন একটি দক্ষ সমাধানের পথ উন্মোচন করে।

কোড ইভোলিউশন: একটি টাইপস্ক্রিপ্ট সাগা

এখানে আমার কোডের উন্নয়নের বৃত্তান্ত, বিস্তারিত ব্যাখ্যা এবং গাণিতিক অন্তর্দৃষ্টি সহ:

সংস্করণ ১: নির্বোধ পদ্ধতি (অতিরিক্ত সোয়াপ সহ)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length

  // Place each number in its correct position if it's in the range [1, n]
  for (let i = 0; i < n; i++) {
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const correctIndex = nums[i] - 1
      ;[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]] // Swap
    }
  }

  // Find the first missing positive
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  // If all numbers are in their correct positions, the missing number is n + 1
  return n + 1
}

এই সংস্করণটি, কার্যকর হলেও, অতিরিক্ত সোয়াপের কারণে ভোগে। সবচেয়ে খারাপ ক্ষেত্রে সোয়াপের সংখ্যা O(n²) এর কাছাকাছি, যদিও গড় ক্ষেত্রে এটি O(n) এর কাছাকাছি।

ব্যাখ্যা:

1. অ্যারে পুনর্বিন্যাস: প্রতিটি সংখ্যা nums[i] তার "সঠিক" সূচকে (nums[i] - 1) স্থাপন করা হয় যদি এটি [1, n] পরিসীমায় থাকে এবং ইতিমধ্যে সঠিক অবস্থানে না থাকে।

2. অনুপস্থিত ধনাত্মক সংখ্যা চিহ্নিতকরণ: পুনর্বিন্যাসের পর, প্রথম সূচক i যেখানে nums[i] !== i + 1 তার মানে হল i + 1 হল অনুপস্থিত ধনাত্মক পূর্ণসংখ্যা।

3. প্রয়োজন হলে n + 1 প্রত্যাবর্তন: যদি 1 থেকে n পর্যন্ত সমস্ত সংখ্যা সঠিক অবস্থানে থাকে, তাহলে অনুপস্থিত সংখ্যাটি হল n + 1।

মূল বিষয়গুলি:

• ইন-প্লেস পুনর্বিন্যাস: অতিরিক্ত স্থান ব্যবহার এড়াতে আমরা অ্যারেটিকে নিজেই পরিবর্তন করি।
• দক্ষতা: পুনর্বিন্যাস এবং চূড়ান্ত স্ক্যান উভয়ই O(n) সময় নেয়, অপ্টিমাল কর্মক্ষমতা নিশ্চিত করে।

সংস্করণ ২: পারফরম্যান্স বুস্ট (অতিরিক্ত সোয়াপ বাদ দেওয়া)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  // Rearrange numbers to their correct positions if possible
  while (idx < n) {
    const correctIdx = nums[idx] - 1
    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      // Swap without using a temporary variable
      ;[nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]
    } else {
      idx++
    }
  }

  // Identify the first missing positive
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return n + 1
}

ব্যাখ্যা:

1. দক্ষ পুনর্বিন্যাস:

   • while লুপ উপাদানগুলিকে সরাসরি তাদের সঠিক অবস্থানে (nums[idx] - 1) স্থাপন করে শুধুমাত্র যখন সংখ্যাটি বৈধ পরিসীমা [1, n]-এর মধ্যে থাকে এবং ইতিমধ্যে তার সঠিক অবস্থানে নেই।
   • if শর্তটি নিশ্চিত করে যে অবৈধ বা ইতিমধ্যে সঠিক সংখ্যাগুলি অপ্রয়োজনীয় সোয়াপ ছাড়াই এড়িয়ে যাওয়া হয়।

2. সরাসরি সূচক পরীক্ষা:

   • পুনর্বিন্যাসের সময়, অবৈধ সোয়াপ এবং অপ্রয়োজনীয় কার্যক্রম nums[idx]-এর পরিসীমা এবং মান পরীক্ষা করে এড়ানো হয়।

3. মেমরি-দক্ষ সোয়াপ:

   • ডিস্ট্রাকচারিং ([nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]) ব্যবহার একটি অস্থায়ী ভেরিয়েবলের প্রয়োজনীয়তা দূর করে, মেমরি ব্যবহার কমিয়ে আনে।

4. ন্যূনতম লুপ:

   • অ্যালগরিদমটি কেবলমাত্র দুটি রৈখিক পাস ব্যবহার করে:
     • একটি অ্যারে ইন-প্লেস পুনর্বিন্যাস করার জন্য।
     • আরেকটি প্রথম অনুপস্থিত ধনাত্মক সংখ্যা খুঁজে বের করার জন্য।

জটিলতা বিশ্লেষণ:

• সময় জটিলতা:
  • while লুপ এবং for লুপ উভয়ই O(n) সময়ে চলে, মোট সময় জটিলতা O(n) করে তোলে।
• স্থান জটিলতা:
  • অ্যালগরিদমটি কোনও সহায়ক ডেটা স্ট্রাকচার ব্যবহার না করে ইন-প্লেসে কাজ করে, তাই স্থান জটিলতা O(1)।

কেন এই কোডটি অপ্টিমাল:

• কর্মক্ষমতা: সুগঠিত while লুপ অপ্রয়োজনীয় কার্যক্রম কমিয়ে আনে, গতি সর্বাধিক করে।
• মেমরি দক্ষতা: ইন-প্লেস সোয়াপ এবং অতিরিক্ত ভেরিয়েবল এড়ানোর ব্যবহার সর্বনিম্ন মেমরি ফুটপ্রিন্ট নিশ্চিত করে।

সংস্করণ ৩: মেমরির জন্য অপ্টিমাইজড (ন্যূনতম স্পেস ব্যবহার)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  while (idx < n) {
    const correctIdx = nums[idx] - 1

    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      nums[idx] = nums[correctIdx]
      nums[correctIdx] = correctIdx + 1
    } else {
      idx++
    }
  }

  for (let idx = 0; idx < n; idx++) {
    if (nums[idx] !== idx + 1) {
      return idx + 1
    }
  }

  return nums.length + 1
}

মূল মেমরি অপ্টিমাইজেশন:

1. ন্যূনতম অস্থায়ী ভেরিয়েবল সহ ইন-প্লেস আপডেট:

   • সোয়াপ করার জন্য একটি temp ভেরিয়েবল ব্যবহার করার পরিবর্তে, এই কোড nums[idx] = nums[correctIdx]; nums[correctIdx] = correctIdx + 1 দিয়ে অ্যারেটিকে সরাসরি পরিবর্তন করে।
   • এটি একটি অস্থায়ী ভেরিয়েবলের প্রয়োজনীয়তা দূর করে, মেমরি ওভারহেড একটি ধ্রুবক পরিমাণে কমিয়ে আনে।

2. লুপে কম অস্থায়ী মান:

   • কোডটি লুপে সরাসরি correctIdx গণনা করে, কোর লজিকের বাইরে অতিরিক্ত মধ্যবর্তী ভেরিয়েবল সংরক্ষণের প্রয়োজনীয়তা এড়িয়ে যায়।
   • কম ভেরিয়েবল নিয়োগ মানে প্রতি পুনরাবৃত্তিতে সামান্য কম মেমরি ব্যবহার।

3. পুনর্বিন্যাসের জন্য একক পাস:

   • প্রথম কোড যা while লুপে নেস্টেড শর্ত ব্যবহার করে, তার বিপরীতে, এই বাস্তবায়ন আরও সুগঠিতভাবে সোয়াপ সম্পূর্ণ করে বা সূচককে এগিয়ে নিয়ে যায়, রানটাইম স্ট্যাক গভীরতা এবং মেমরি ব্যবহার কমিয়ে আনে।
   • লুপ গঠন (while একটি একক বৃদ্ধি বা পুনর্বিন্যাস সহ) আরও সরাসরি, কম সহায়ক মানের প্রয়োজন।

4. কোন অতিরিক্ত চেক নেই:

   • correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]-এর জন্য চেকগুলি সংক্ষিপ্ত এবং অপ্রয়োজনীয় অপারেশন এড়িয়ে যায় যা অস্থায়ীভাবে স্ট্যাক বা CPU ক্যাশে মেমরি ব্যবহার করতে পারে।
   • এটি ফলাফলে অবদান রাখবে না এমন অপারেশনের জন্য অতিরিক্ত সম্পদ বরাদ্দ করার প্রয়োজন এড়িয়ে যায়।

কেন এটি মেমরিতে পার্থক্য তৈরি করে:

• কম অস্থায়ী স্টোরেজ: একটি temp ভেরিয়েবলে নির্ভর না করে এবং মধ্যবর্তী গণনাকে কমিয়ে আনার মাধ্যমে, মেমরি ফুটপ্রিন্ট ছোট হয়।
• সুগঠিত নির্বাহ: কম ধাপ এবং সহজ লজিক প্রতি অপারেশনে কম মেমরি ব্যবহারের দিকে নির্দেশ করে।
• উন্নত ক্যাশ ব্যবহার: অ্যালগরিদমের রৈখিক, পূর্বাভাসযোগ্য অ্যাক্সেস প্যাটার্ন CPU ক্যাশ কর্মক্ষমতা উন্নত করে, পরোক্ষভাবে মেমরি ওভারহেড কমায়।

এই সমাধানের সরাসরি ইন-প্লেস আপডেট, ন্যূনতম ভেরিয়েবল ব্যবহার এবং কার্যকর মেমরি অ্যাক্সেস প্যাটার্নের উপর ফোকাস এটিকে মেমরি দক্ষতার দিক থেকে সর্বোত্তম করে তোলে। যদিও সঞ্চয় ধ্রুবক (O(1)), তবে লিটকোডের মতো প্রতিযোগিতামূলক প্ল্যাটফর্মে, বিশেষ করে বৃহৎ ডেটা সেটের জন্য, এটি যথেষ্ট উল্লেখযোগ্য।

সংস্করণ ৪: অপ্টিমাইজড মাস্টারপিস (ইন-প্লেস সোয়াপিং, কোন টেম্প নেই)

function firstMissingPositive(nums: number[]): number {
  for (let i = 0; i < nums.length; i++) {
    while (nums[i] !== i + 1) {
      if (nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]) {
        break
      }

      const temp = nums[i]
      nums[i] = nums[temp - 1]
      nums[temp - 1] = temp
    }
  }

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return nums.length + 1
}

এই চূড়ান্ত সংস্করণটি অস্থায়ী ভেরিয়েবল ছাড়া মার্জিত ইন-প্লেস সোয়াপিংয়ের মাধ্যমে অপ্টিমাল কর্মক্ষমতা এবং ন্যূনতম মেমরি ব্যবহার উভয়ই অর্জন করে। সময় জটিলতা এখন দৃঢ়ভাবে O(n), এবং স্থান জটিলতা O(1), সমস্ত প্রয়োজনীয়তা পূরণ করে। গাণিতিকভাবে, আমরা উপাদানগুলি তাদের "সঠিক" অবস্থানে স্থাপন করার জন্য অ্যারের মধ্যে একটি চক্রীয় পুনর্বিন্যাস সম্পাদন করছি।

nums[i] === nums[nums[i] - 1] চেক যোগ করে, আমরা অপ্রয়োজনীয় সোয়াপগুলি এড়িয়ে যাই। এটি কর্মক্ষমতা উল্লেখযোগ্যভাবে উন্নত করে, সময় জটিলতা ইচ্ছিত O(n)-এর কাছাকাছি নিয়ে আসে।

বাস্তবায়নের মূল পার্থক্য:

1. অতিরিক্ত সোয়াপ এড়ানো:

   • প্রদত্ত কোড সোয়াপ করার আগে স্পষ্টতই পরীক্ষা করে দেখে যে nums[i] === nums[nums[i] - 1]। এটি অপ্রয়োজনীয় সোয়াপ এড়িয়ে যায় যখন সংখ্যাটি ইতিমধ্যে সঠিক অবস্থানে থাকে বা অনুলিপি বিদ্যমান।
   • প্রথম বাস্তবায়নে, এই চেকটি বাদ দেওয়া হয়েছে, অপ্রয়োজনীয় সোয়াপের দিকে নিয়ে যেতে পারে। প্রতিটি অতিরিক্ত সোয়াপ ওভারহেড যোগ করে, বিশেষ করে বৃহত্তর অ্যারের জন্য।

2. সরাসরি সূচক তুলনা:

   • প্রদত্ত কোডটি একটি সংখ্যা বারবার তার সঠিক অবস্থানে সোয়াপ করা হয় কিনা তা নিশ্চিত করার জন্য while (nums[i] !== i + 1) ব্যবহার করে যতক্ষণ না এটি সঠিকভাবে স্থাপন করা হয় বা একটি অবৈধ শর্ত পূরণ হয়। এটি অপ্রয়োজনীয় লুপ পুনরাবৃত্তি দূর করে।
   • প্রথম কোড লুপ শর্তের মধ্যে সংখ্যাটিকে তার উদ্দেশ্য সূচকের সাথে স্পষ্টতই তুলনা করে না। সংখ্যাগুলির ক্ষেত্রে কম স্থানান্তরের প্রয়োজন হলে এটি আরও অপারেশন করতে পারে।

3. অপ্টিমাইজড শর্তাধীন চেক:

   • একক if ব্লকে শর্তগুলি একত্রিত করে (যেমন, nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]), কোডটি অপ্রয়োজনীয় চেক বা গণনার অতিরিক্ত ওভারহেড এড়িয়ে যায়।

কেন লিটকোডে এটি গুরুত্বপূর্ণ:

• রানটাইম সামঞ্জস্য:

  • লিটকোডের রানটাইম পরিমাপ অপ্রয়োজনীয় অপারেশনের প্রতি সংবেদনশীল হতে পারে, যেমন অতিরিক্ত সোয়াপ বা অতিরিক্ত তুলনা।
  • প্রদত্ত কোড এই কার্যক্রমগুলি কমিয়ে আনে, গড়ে দ্রুত রানটাইমের দিকে নিয়ে যায়।

• ক্যাশ দক্ষতা:

  • কম সোয়াপ এবং সহজ লুপ লজিক উন্নত CPU ক্যাশ ব্যবহারের ফলে। আধুনিক প্রসেসর পূর্বাভাসযোগ্য এবং সুগঠিত অ্যাক্সেস প্যাটার্নের সুবিধা পায়, যা প্রদত্ত কোড প্রদর্শন করে।

ফলাফল

এখানে একটি টেবিল ফরম্যাটে উপস্থাপিত সারসংক্ষেপ:

এই টেবিলটি ট্রেড-অফ এবং চূড়ান্ত সমাধানের অপ্টিমালিটি হাইলাইট করে।

সারসংক্ষেপ ইঙ্গিত করে যে সর্বোত্তম কর্মক্ষমতা এবং মেমরির জন্য প্রচেষ্টা সত্যই সবচেয়ে অপ্টিমাইজড, অর্জন করেছে:

• ১ ms রানটাইম: কর্মক্ষমতার দিক থেকে দ্রুততম ফলাফলের সাথে মেলে।
• ৫৮.৯ MB মেমরি ব্যবহার: "সর্বোত্তম মেমরি" ক্লোনের চেয়ে সামান্য বেশি কিন্তু অন্যান্য প্রচেষ্টার চেয়ে কম।

বিশ্লেষণ:

1. রানটাইম:

   • ১ ms রানটাইম দেখায় যে অপ্টিমাইজড পদ্ধতি অপ্রয়োজনীয় চেক এবং অপ্রয়োজনীয় সোয়াপগুলি দূর করে।
   • O(n)-এর সামঞ্জস্যপূর্ণ সময় জটিলতা বৃহত্তর ডেটা সেটের জন্য স্কেলেবিলিটি নিশ্চিত করে।

2. মেমরি:

   • ৫৮.৯ MB প্রতিযোগিতামূলক, দেখায় যে দ্রুত নির্বাহ সত্ত্বেও মেমরি ফুটপ্রিন্ট কম। "সর্বোত্তম মেমরি" (৫৮.৫ MB)-এর তুলনায় এই সামান্য বৃদ্ধি ডিস্ট্রাকচারিং বা ইঞ্জিন-নির্দিষ্ট অপ্টিমাইজেশনের পার্থক্যের কারণে হতে পারে।

3. ট্রেড-অফ:

   • "সর্বোত্তম মেমরি" সমাধান কম মেমরি ব্যবহারের জন্য সামান্য রানটাইম উৎসর্গ করে।
   • "সর্বোত্তম কর্মক্ষমতা" সমাধান আরও গতির উপর ফোকাস করে তবে সামান্য বেশি মেমরি ব্যবহার করে।

উপসংহার:

অপ্টিমাইজড সমাধান একটি ভাল ভারসাম্য তৈরি করে:

• ১ ms রানটাইম সর্বোত্তম-কর্মক্ষমতা কোডের মতোই দ্রুত।
• ৫৮.৯ MB মেমরি ব্যবহার সর্বোত্তম-মেমরি ফলাফলের কাছাকাছি, নগণ্য ওভারহেড সহ।

বিশেষ করে এমন পরিস্থিতির জন্য এটি একটি সুগঠিত পছন্দ যেখানে কর্মক্ষমতা এবং মেমরি উভয়ই গুরুত্বপূর্ণ।

গাণিতিক ভিত্তি: চক্রীয় পুনর্বিন্যাস এবং পিজনহোল নীতি

মূল ধারণাটি চক্রীয় পুনর্বিন্যাসের ধারণার চারপাশে ঘোরে। আমরা এমন একটি চক্র তৈরি করার লক্ষ্য রাখি যেখানে প্রতিটি সংখ্যা x সূচক x - 1 এ স্থাপন করা হয়। while লুপ কার্যকরভাবে এই চক্রগুলি পার করে, প্রতিটি উপাদান তার নির্দিষ্ট স্থান খুঁজে পেতে নিশ্চিত করে।

পিজনহোল নীতি এখানে সূক্ষ্মভাবে ভূমিকা পালন করে। যেহেতু আমাদের n সম্ভাব্য অবস্থান (সূচক 0 থেকে n-1) আছে এবং আমরা [1, n+1] পরিসীমায় একটি অনুপস্থিত ধনাত্মক পূর্ণসংখ্যা খুঁজছি, যদি 1 থেকে n পর্যন্ত সমস্ত সংখ্যা উপস্থিত থাকে, তাহলে অনুপস্থিত সংখ্যাটি অবশ্যই n + 1 হতে হবে।

আসক্তি অব্যাহত...

লিটকোড ৪১-এর প্রতি আমার আগ্রহ অব্যাহত রয়েছে। আমি ক্রমাগত আরও অপ্টিমাইজেশন এবং গভীর অন্তর্দৃষ্টি অনুসন্ধান করছি। এই অন্বেষণে আমার সাথে যোগ দিন! আপনার চিন্তাভাবনা, আপনার নিজস্ব সমাধানগুলি শেয়ার করুন এবং আসুন গণিত এবং অ্যালগরিদমের মার্জিত ছেদ একসাথে অন্বেষণ করি।