Leetcode 150 | Day 5: स्टॉक खरीदने और बेचने का सबसे अच्छा समय

Leetcode 121 आपसे स्टॉक खरीदने और बेचने का सबसे अच्छा समय खोजने के लिए कहता है। आपको कीमतों का एक array मिलता है। प्रत्येक index एक दिन है। मान (value) उस दिन की लागत है।

लक्ष्य सरल है। अधिकतम लाभ प्राप्त करने के लिए एक दिन खरीदें और भविष्य के किसी दिन बेचें। यदि कोई लाभ संभव नहीं है, तो 0 लौटाएं।

समस्या की सीमाएं (Problem Constraints):

  • Array की लंबाई 100,000 तक।
  • कीमतें 10,000 तक।
  • आपको खरीदने के बाद ही बेचना होगा।

दृष्टिकोण 1: सरल तरीका (Brute Force)

Brute force तरीका हर एक खरीदने और बेचने के जोड़े (pair) की जांच करता है। इसमें दो loops का उपयोग होता है।

  • Time Complexity: O(n²)
  • समस्या: यह बहुत धीमा है।

यदि आपके पास 1,000 दिन हैं, तो आप 1,000,000 जांच करते हैं। यदि आपके पास 100,000 दिन हैं, तो आप 10,000,000,000 जांच करते हैं। इससे Leetcode पर timeout हो जाता है।

दृष्टिकोण 2: अनुकूलित तरीका (One Pass)

आप दो variables का उपयोग करके इसे एक ही pass में हल कर सकते हैं: minPrice और maxProfit।

  • 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] के साथ उदाहरण का विवरण:

  • दिन 1: कीमत 7. minPrice 7 हो जाता है। maxProfit 0 रहता है।
  • दिन 2: कीमत 1. minPrice 1 हो जाता है। maxProfit 0 रहता है।
  • दिन 3: कीमत 5. 5 - 1 = 4. maxProfit 4 हो जाता है।
  • दिन 4: कीमत 3. 3 - 1 = 2. maxProfit 4 रहता है।
  • दिन 5: कीमत 6. 6 - 1 = 5. maxProfit 5 हो जाता है।
  • दिन 6: कीमत 4. 4 - 1 = 3. maxProfit 5 रहता है।

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

अनुकूलित संस्करण (optimized version) इसलिए बेहतर है क्योंकि यह प्रत्येक कीमत को केवल एक बार देखता है। यह बड़े डेटासेट के लिए बहुत प्रभावी है।

स्रोत: https://dev.to/afuji/leetcode-150-day-5-best-time-to-buy-and-sell-stock-naive-vs-optimized-4mk1