সমস্যা বিবরণ
আমাদের কাছে n সংখ্যক পূর্ণসংখ্যা বিশিষ্ট একটি অ্যারে দেওয়া আছে। আমাদের কাজ হলো যাচাই করা যে শুধুমাত্র একটি উপাদান পরিবর্তন করে কি এই অ্যারেটিকে নন-ডিক্রিজিং (non-decreasing) করা সম্ভব। একটি অ্যারে নন-ডিক্রিজিং হয় যদি প্রতিটি i (১ ≤ i < n) এর জন্য array[i] ≤ array[i + 1] সত্য হয়।
উদাহরণস্বরূপ, অ্যারে [4,2,3] কে নন-ডিক্রিজিং করা যাবে যদি 4 কে 1 করে দিই, ফলে অ্যারে হয়ে যাবে [1,2,3]।
সমাধানের পদ্ধতি
- যদি অ্যারেতে ২ বা তার কম উপাদান থাকে, তবে true ফেরত দিন।
- একটি ফ্ল্যাগ ভেরিয়েবল ans = False সেট করুন।
- অ্যারেটি ০ থেকে (n-2) ইনডেক্স পর্যন্ত লুপ চালান।
- যদি arr[i] > arr[i+1] হয়:
- যদি ans ইতিমধ্যে True হয়, তবে false ফেরত দিন (কারণ একাধিক পরিবর্তন প্রয়োজন)।
- অন্যথায় ans = True সেট করুন।
- যদি i > 0 এবং arr[i-1] > arr[i+1] হয়, তবে arr[i+1] = arr[i] করুন (পिछের উপাদান বড় হলে বর্তমান উপাদান বড় করতে হয়)।
- লুপ শেষে true ফেরত দিন।
পাইথন উদাহরণ
class Solution(object):
def checkPossibility(self, nums):
if len(nums) <= 2:
return True
ans = False
for i in range(len(nums)-1):
if nums[i] > nums[i+1]:
if ans:
return False
else:
ans = True
if i > 0:
if nums[i-1] > nums[i+1]:
nums[i+1] = nums[i]
return True
ob1 = Solution()
print(ob1.checkPossibility([4,2,3,5]))
ইনপুট
[4,2,3,5]
আউটপুট
True
