𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟱: 𝗕𝗲𝘀𝘁 𝗧𝗶𝗺𝗲 𝘁𝗼 𝗕𝘂𝘆 𝗮𝗻𝗱 𝗦𝗲𝗹𝗹 𝗦𝘁𝗼𝗰𝗸

𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟱: 𝗕𝗲𝘀𝘁 𝗧𝗶𝗺𝗲 𝘁𝗼 𝗕𝘂𝘆 𝗮𝗻𝗱 𝗦𝗲𝗹𝗹 𝗦𝘁𝗼𝗰𝗸

Leetcode 121 मध्ये तुम्हाला शेअर खरेदी आणि विक्री करण्यासाठी सर्वोत्तम वेळ शोधण्यास सांगितले जाते. तुम्हाला किमतींचा एक array मिळतो. प्रत्येक index हा एक दिवस आहे आणि त्या index ची value म्हणजे त्या दिवसाची किंमत आहे.

ध्येय साधे आहे. जास्तीत जास्त नफा मिळवण्यासाठी एका दिवशी खरेदी करा आणि भविष्यातील एखाद्या दिवशी विक्री करा. जर कोणताही नफा शक्य नसेल, तर 0 रिटर्न करा.

समस्येच्या मर्यादा (Problem Constraints):

• Array ची लांबी १००,००० पर्यंत असू शकते.
• किमती १०,००० पर्यंत असू शकतात.
• तुम्हाला खरेदी केल्यानंतरच विक्री करावी लागेल.

दृष्टिकोन १: साधी पद्धत (Brute Force)

Brute force पद्धतीत खरेदी आणि विक्रीच्या प्रत्येक जोडीची तपासणी केली जाते. यासाठी दोन loops वापरले जातात.

• Time Complexity: O(n²)
• समस्या: ही पद्धत खूप संथ आहे.

जर तुमच्याकडे १,००० दिवस असतील, तर तुम्हाला १,०००,००० तपासण्या कराव्या लागतील. जर तुमच्याकडे १००,००० दिवस असतील, तर तुम्हाला १०,०००,०००,००० तपासण्या कराव्या लागतील. यामुळे Leetcode वर 'timeout' होऊ शकतो.

दृष्टिकोन २: ऑप्टिमाइझ केलेली पद्धत (One Pass)

तुम्ही minPrice आणि maxProfit या दोन variables वापरून हे एकाच वेळी (one pass) सोडवू शकता.

• Time Complexity: O(n)
• Space Complexity: O(1)

हे कसे कार्य करते:

1. minPrice ची किंमत Infinity सेट करा.
2. maxProfit ची किंमत 0 सेट करा.
3. प्रत्येक किमतीसाठी loop चालवा.
4. जर सध्याची किंमत minPrice पेक्षा कमी असेल, तर minPrice अपडेट करा.
5. जर (सध्याची किंमत - minPrice) ही maxProfit पेक्षा जास्त असेल, तर maxProfit अपडेट करा.

[7, 1, 5, 3, 6, 4] या किमतींसह उदाहरण:

• दिवस १: किंमत ७. minPrice ७ होईल. maxProfit ० राहील.
• दिवस २: किंमत १. minPrice १ होईल. maxProfit ० राहील.
• दिवस ३: किंमत ५. ५ - १ = ४. maxProfit ४ होईल.
• दिवस ४: किंमत ३. ३ - १ = २. maxProfit ४ राहील.
• दिवस ५: किंमत ६. ६ - १ = ५. maxProfit ५ होईल.
• दिवस ६: किंमत ४. ४ - १ = ३. maxProfit ५ राहील.

अंतिम उत्तर: 5.

ऑप्टिमाइझ केलेली आवृत्ती (optimized version) अधिक प्रभावी आहे कारण ती प्रत्येक किमतीकडे फक्त एकदाच पाहते. मोठ्या डेटासेटसाठी ही पद्धत उत्तम प्रकारे काम करते.

Source: https://dev.to/afuji/leetcode-150-day-5-best-time-to-buy-and-sell-stock-naive-vs-optimized-4mk1