জাভাস্ক্রিপ্টে প্রায় উর্ধ্বক্রমী অ্যারে যাচাই

একটি পূর্ণসংখ্যা অ্যারে দেওয়া আছে। নির্ধারণ করতে হবে যে অ্যারেতে από অতি সীমিত একটি উপাদান (০ বা ১টি) সরিয়ে কি সেটিকে স্ট্রিক্টলি উর্ধ্বক্রমী (strictly increasing) বানানো সম্ভব।

নোট: সিকোয়েন্স a0, a1, ..., an কে স্ট্রিক্টলি উর্ধ্বক্রমী বলা হয় যদি a0 < a1 < ... < an। একক উপাদানযুক্ত সিকোয়েন্সও স্ট্রিক্টলি উর্ধ্বক্রমী বলে মনে করা হয়।

উদাহরণ

• sequence = [1, 3, 2, 1] → আউটপুট: false। কারণ একক উপাদান সরিয়ে স্ট্রিক্টলি উর্ধ্বক্রমী বানানো সম্ভব নয়।
• sequence = [1, 3, 2] → আউটপুট: true। ৩ বা ২ যেকোনো একটি সরালে [1, 2] বা [1, 3] স্ট্রিক্টলি উর্ধ্বক্রমী হয়।

উদাহরণ কোড

const arr1 = [3, 5, 67, 98, 3];
const arr2 = [4, 3, 5, 67, 98, 3];

const almostIncreasingSequence = sequence => {
  let removed = 0;
  let i = 0;
  let prev = -Infinity;
  
  while (removed < 2 && i < sequence.length) {
    if (sequence[i] > prev) {
      prev = sequence[i];
    } else {
      prev = Math.min(prev, sequence[i]);
      removed++;
    }
    i++;
  }
  
  return removed < 2;
};

console.log(almostIncreasingSequence(arr1)); // true
console.log(almostIncreasingSequence(arr2)); // false

আউটপুট

true false

অ্যালগরিদম ব্যাখ্যা

• removed ভেরিয়েবল ট্র্যাক করে কতগুলো উপাদান "সরানো" হয়েছে।
• prev ভেরিয়েবল আগের বৈধ মান সংরক্ষণ করে।
• যদি বর্তমান উপাদান prev থেকে বড় হয়, তবে সেটি গ্রহণযোগ্য, prev আপডেট করা হয়।
• অন্যথায়, একটি উপাদান "সরানো" হয়েছে ধরে removed বাড়ানো হয় এবং prev হলো বর্তমান এবং আগের মানের ন্যূনতম।
• লুপ চলবে যতক্ষণ removed < 2 এবং অ্যারে শেষ না হয়।
• ফলাফল true যদি শুধু ০ বা ১টি উপাদান সরাতে হয়।