Leetcode 150 | دن 5: اسٹاک خریدنے اور بیچنے کا بہترین وقت

Leetcode 121 آپ سے اسٹاک خریدنے اور بیچنے کا بہترین وقت تلاش کرنے کا کہتا ہے۔ آپ کو قیمتوں کا ایک array ملتا ہے۔ ہر index ایک دن ہے۔ قیمت اس دن کی لاگت ہے۔

مقصد سادہ ہے۔ زیادہ سے زیادہ منافع حاصل کرنے کے لیے ایک دن خریدیں اور مستقبل کے کسی دن بیچیں۔ اگر کوئی منافع ممکن نہ ہو تو 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 استعمال کرتے ہوئے اسے ایک ہی بار (one 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] کے ساتھ مثال کا ٹریس (trace):

  • دن 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۔

بہتر ورژن اس لیے جیت جاتا ہے کیونکہ یہ ہر قیمت کو صرف ایک بار دیکھتا ہے۔ یہ بڑے ڈیٹا سیٹس کے لیے بہترین ہے۔

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