ধরুন একটি পূর্ণসংখ্যার অ্যারে আছে যেখানে সব এলিমেন্ট পজিটিভ। প্রাথমিক স্টার্টিং পয়েন্ট ইনডেক্স ১। প্রতিটি এলিমেন্ট ঐ পজিশনে আমাদের সর্বোচ্চ জাম্প দৈর্ঘ্য নির্দেশ করে। লক্ষ্য হল ফাইনাল সেলে কম জাম্পে পৌঁছানো। যেমন [2,3,1,1,4] অ্যারেটি জন্য আউটপুট ২, কারণ ইনডেক্স ০ থেকে ১-এ জাম্প, তারপর ৪-এ (লাস্ট ইনডেক্স)।
সমাধানের ধাপগুলো −
- end := 0, jumps := 0, farthest := 0
- i = 0 থেকে len(nums)-1 পর্যন্ত − farthest = max(farthest, nums[i]+i); যদি i == end এবং i != len(nums)-1 হয় তবে jumps++; end = farthest
- jumps রিটার্ন করুন
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন −
class Solution(object):
def jump(self, nums):
end = 0
jumps = 0
farthest = 0
for i in range(len(nums)):
farthest = max(farthest,nums[i]+i)
if i == end and i != len(nums)-1:
jumps+=1
end = farthest
return jumps
ob = Solution()
print(ob.jump([2,3,1,1,4]))
ইনপুট
[2,3,1,1,4]
আউটপুট
2
