Leetcode 150 | দিন ৫: স্টক কেনা এবং বিক্রির সেরা সময়
Leetcode 121 আপনাকে একটি স্টক কেনা এবং বিক্রির সেরা সময় খুঁজে বের করতে বলে। আপনাকে দামের একটি অ্যারে (array) দেওয়া হবে। প্রতিটি ইনডেক্স হলো একটি দিন এবং এর মান হলো সেই দিনের দাম।
লক্ষ্যটি সহজ। সবচেয়ে বেশি মুনাফা পেতে একটি দিনে কিনুন এবং ভবিষ্যতের কোনো একদিনে বিক্রি করুন। যদি কোনো মুনাফা সম্ভব না হয়, তবে 0 রিটার্ন করুন।
সমস্যার সীমাবদ্ধতা (Problem Constraints):
- অ্যারের দৈর্ঘ্য ১০০,০০০ পর্যন্ত।
- দাম ১০,০০০ পর্যন্ত।
- আপনাকে অবশ্যই কেনার পরে বিক্রি করতে হবে।
পদ্ধতি ১: সাধারণ পদ্ধতি (Brute Force)
Brute force পদ্ধতিতে প্রতিটি কেনা এবং বিক্রির জোড়া পরীক্ষা করা হয়। এতে দুটি লুপ (loop) ব্যবহার করা হয়।
- Time Complexity: O(n²)
- সমস্যা: এটি অনেক ধীরগতির।
যদি আপনার কাছে ১,০০০ দিন থাকে, তবে আপনাকে ১,০০০,০০০ বার পরীক্ষা করতে হবে। যদি ১,০০,০০০ দিন থাকে, তবে আপনাকে ১০,০০০,০০০,০০০ বার পরীক্ষা করতে হবে। এর ফলে Leetcode-এ টাইমআউট (timeout) হতে পারে।
পদ্ধতি ২: অপ্টিমাইজড পদ্ধতি (One Pass)
আপনি দুটি ভেরিয়েবল (variable) ব্যবহার করে এটি এক পাশেই (one pass) সমাধান করতে পারেন: minPrice এবং maxProfit।
- Time Complexity: O(n)
- Space Complexity: O(1)
এটি যেভাবে কাজ করে:
minPrice-কে Infinity সেট করুন।maxProfit-কে 0 সেট করুন।- প্রতিটি দামের ওপর লুপ চালান।
- যদি বর্তমান দাম
minPrice-এর চেয়ে কম হয়, তবেminPriceআপডেট করুন। - যদি (বর্তমান দাম -
minPrice) এর মানmaxProfit-এর চেয়ে বেশি হয়, তবেmaxProfitআপডেট করুন।
[7, 1, 5, 3, 6, 4] দামের উদাহরণটি লক্ষ্য করুন:
- দিন ১: দাম ৭।
minPriceহলো ৭।maxProfit০-ই থাকে। - দিন ২: দাম ১।
minPriceহলো ১।maxProfit০-ই থাকে। - দিন ৩: দাম ৫। ৫ - ১ = ৪।
maxProfitহলো ৪। - দিন ৪: দাম ৩। ৩ - ১ = ২।
maxProfit৪-ই থাকে। - দিন ৫: দাম ৬। ৬ - ১ = ৫।
maxProfitহলো ৫। - দিন ৬: দাম ৪। ৪ - ১ = ৩।
maxProfit৫-ই থাকে।
চূড়ান্ত উত্তর: ৫।
অপ্টিমাইজড সংস্করণটি বেশি কার্যকর কারণ এটি প্রতিটি দাম মাত্র একবার দেখে। এটি বড় ডেটাসেটের জন্য খুব ভালো কাজ করে।
উৎস: https://dev.to/afuji/leetcode-150-day-5-best-time-to-buy-and-sell-stock-naive-vs-optimized-4mk1