Leetcode 150 | Day 5: స్టాక్‌లను కొనడానికి మరియు అమ్మడానికి ఉత్తమ సమయం

Leetcode 121 ఒక స్టాక్‌ను కొనడానికి మరియు అమ్మడానికి ఉత్తమ సమయాన్ని కనుగొనమని మిమ్మల్ని అడుగుతుంది. మీకు ధరల యొక్క ఒక array ఇవ్వబడుతుంది. ప్రతి index ఒక రోజును సూచిస్తుంది. ఆ విలువ ఆ రోజు యొక్క ధరను సూచిస్తుంది.

దీని లక్ష్యం చాలా సరళమైనది. గరిష్ట లాభం పొందడానికి ఒక రోజున కొని, భవిష్యత్తులో మరొక రోజున అమ్మాలి. ఒకవేళ లాభం వచ్చే అవకాశం లేకపోతే, 0 ని రిటర్న్ చేయాలి.

సమస్య యొక్క పరిమితులు (Problem Constraints):

  • Array పొడవు 100,000 వరకు ఉండవచ్చు.
  • ధరలు 10,000 వరకు ఉండవచ్చు.
  • మీరు కొన్న తర్వాతే అమ్మాలి.

Approach 1: The Naive Method (Brute Force)

Brute force పద్ధతిలో ప్రతి కొనుగోలు మరియు అమ్మకం జతలను (buy and sell pairs) తనిఖీ చేస్తారు. దీని కోసం రెండు loops ఉపయోగిస్తారు.

  • Time Complexity: O(n²)
  • సమస్య: ఇది చాలా నెమ్మదిగా ఉంటుంది.

మీకు 1,000 రోజులు ఉంటే, మీరు 1,000,000 తనిఖీలు చేస్తారు. మీకు 100,000 రోజులు ఉంటే, మీరు 10,000,000,000 తనిఖీలు చేస్తారు. దీనివల్ల Leetcode లో timeout అవుతుంది.

Approach 2: The Optimized Method (One Pass)

మీరు minPrice మరియు maxProfit అనే రెండు వేరియబుల్స్ ఉపయోగించి దీనిని ఒకే పాస్‌లో (one pass) పరిష్కరించవచ్చు.

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

ఇది ఎలా పనిచేస్తుంది:

  1. minPrice ని Infinity గా సెట్ చేయండి.
  2. maxProfit ని 0 గా సెట్ చేయండి.
  3. ప్రతి ధర ద్వారా లూప్ చేయండి.
  4. ప్రస్తుత ధర minPrice కంటే తక్కువగా ఉంటే, minPrice ని అప్‌డేట్ చేయండి.
  5. ప్రస్తుత ధర నుండి minPrice తీసివేసినప్పుడు వచ్చే విలువ maxProfit కంటే ఎక్కువగా ఉంటే, maxProfit ని అప్‌డేట్ చేయండి.

[7, 1, 5, 3, 6, 4] ధరలతో ఉదాహరణ:

  • Day 1: ధర 7. minPrice 7 అవుతుంది. maxProfit 0 గానే ఉంటుంది.
  • Day 2: ధర 1. minPrice 1 అవుతుంది. maxProfit 0 గానే ఉంటుంది.
  • Day 3: ధర 5. 5 - 1 = 4. maxProfit 4 అవుతుంది.
  • Day 4: ధర 3. 3 - 1 = 2. maxProfit 4 గానే ఉంటుంది.
  • Day 5: ధర 6. 6 - 1 = 5. maxProfit 5 అవుతుంది.
  • Day 6: ధర 4. 4 - 1 = 3. maxProfit 5 గానే ఉంటుంది.

తుది సమాధానం (Final Answer): 5.

Optimized వెర్షన్ మెరుగైనది, ఎందుకంటే ఇది ప్రతి ధరను ఒక్కసారి మాత్రమే పరిశీలిస్తుంది. ఇది పెద్ద డేటాసెట్‌లకు (large datasets) బాగా సరిపోతుంది.

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