Leetcode 150 | Day 5: ਸਟਾਕ ਖਰੀਦਣ ਅਤੇ ਵੇਚਣ ਦਾ ਸਭ ਤੋਂ ਵਧੀਆ ਸਮਾਂ
Leetcode 121 ਤੁਹਾਨੂੰ ਇੱਕ ਸਟਾਕ ਖਰੀਦਣ ਅਤੇ ਵੇਚਣ ਦਾ ਸਭ ਤੋਂ ਵਧੀਆ ਸਮਾਂ ਲੱਭਣ ਲਈ ਕਹਿੰਦਾ ਹੈ। ਤੁਹਾਨੂੰ ਕੀਮਤਾਂ ਦਾ ਇੱਕ ਐਰੇ (array) ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ। ਹਰ ਇੰਡੈਕਸ (index) ਇੱਕ ਦਿਨ ਹੈ। ਮੁੱਲ ਉਸ ਦਿਨ ਦੀ ਕੀਮਤ ਹੈ।
ਟੀਚਾ ਸਰਲ ਹੈ। ਸਭ ਤੋਂ ਵੱਧ ਮੁਨਾਫਾ ਕਮਾਉਣ ਲਈ ਇੱਕ ਦਿਨ ਖਰੀਦੋ ਅਤੇ ਭਵਿੱਖ ਦੇ ਕਿਸੇ ਦਿਨ ਵੇਚੋ। ਜੇਕਰ ਕੋਈ ਮੁਨਾਫਾ ਸੰਭਵ ਨਹੀਂ ਹੈ, ਤਾਂ 0 ਰਿਟਰਨ ਕਰੋ।
ਸਮੱਸਿਆ ਦੀਆਂ ਸੀਮਾਵਾਂ (Problem Constraints):
- ਐਰੇ ਦੀ ਲੰਬਾਈ 100,000 ਤੱਕ।
- ਕੀਮਤਾਂ 10,000 ਤੱਕ।
- ਤੁਹਾਨੂੰ ਖਰੀਦਣ ਤੋਂ ਬਾਅਦ ਹੀ ਵੇਚਣਾ ਚਾਹੀਦਾ ਹੈ।
Approach 1: The Naive Method (Brute Force)
Brute force ਤਰੀਕਾ ਹਰ ਇੱਕ ਖਰੀਦ ਅਤੇ ਵੇਚ ਦੇ ਜੋੜ ਦੀ ਜਾਂਚ ਕਰਦਾ ਹੈ। ਇਸ ਵਿੱਚ ਦੋ ਲੂਪਸ (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)
ਤੁਸੀਂ ਦੋ ਵੇਰੀਏਬਲਸ (variables) ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਇਸਨੂੰ ਇੱਕ ਵਾਰ (one pass) ਵਿੱਚ ਹੱਲ ਕਰ ਸਕਦੇ ਹੋ: minPrice ਅਤੇ maxProfit।
- Time Complexity: O(n)
- Space Complexity: O(1)
ਇਹ ਕਿਵੇਂ ਕੰਮ ਕਰਦਾ ਹੈ:
minPriceਨੂੰ Infinity 'ਤੇ ਸੈੱਟ ਕਰੋ।maxProfitਨੂੰ 0 'ਤੇ ਸੈੱਟ ਕਰੋ।- ਹਰ ਕੀਮਤ ਰਾਹੀਂ ਲੂਪ ਚਲਾਓ।
- ਜੇਕਰ ਮੌਜੂਦਾ ਕੀਮਤ
minPriceਤੋਂ ਘੱਟ ਹੈ, ਤਾਂminPriceਨੂੰ ਅਪਡੇਟ ਕਰੋ। - ਜੇਕਰ ਮੌਜੂਦਾ ਕੀਮਤ ਮਿਨਸ
minPricemaxProfitਤੋਂ ਵੱਧ ਹੈ, ਤਾਂmaxProfitਨੂੰ ਅਪਡੇਟ ਕਰੋ।
ਕੀਮਤਾਂ [7, 1, 5, 3, 6, 4] ਦੇ ਨਾਲ ਉਦਾਹਰਣ ਦਾ ਟ੍ਰੇਸ (trace):
- ਦਿਨ 1: ਕੀਮਤ 7।
minPrice7 ਹੋ ਜਾਂਦਾ ਹੈ।maxProfit0 ਰਹਿੰਦਾ ਹੈ। - ਦਿਨ 2: ਕੀਮਤ 1।
minPrice1 ਹੋ ਜਾਂਦਾ ਹੈ।maxProfit0 ਰਹਿੰਦਾ ਹੈ। - ਦਿਨ 3: ਕੀਮਤ 5। 5 - 1 = 4।
maxProfit4 ਹੋ ਜਾਂਦਾ ਹੈ। - ਦਿਨ 4: ਕੀਮਤ 3। 3 - 1 = 2।
maxProfit4 ਰਹਿੰਦਾ ਹੈ। - ਦਿਨ 5: ਕੀਮਤ 6। 6 - 1 = 5।
maxProfit5 ਹੋ ਜਾਂਦਾ ਹੈ। - ਦਿਨ 6: ਕੀਮਤ 4। 4 - 1 = 3।
maxProfit5 ਰਹਿੰਦਾ ਹੈ।
ਅੰਤਿਮ ਉੱਤਰ: 5।
ਅਪਟੀਮਾਈਜ਼ਡ ਵਰਜ਼ਨ ਇਸ ਲਈ ਬਿਹਤਰ ਹੈ ਕਿਉਂਕਿ ਇਹ ਹਰ ਕੀਮਤ ਨੂੰ ਸਿਰਫ ਇੱਕ ਵਾਰ ਦੇਖਦਾ ਹੈ। ਇਹ ਵੱਡੇ ਡੇਟਾਸੈਟਾਂ ਲਈ ਵਧੀਆ ਕੰਮ ਕਰਦਾ ਹੈ।
ਸਰੋਤ: https://dev.to/afuji/leetcode-150-day-5-best-time-to-buy-and-sell-stock-naive-vs-optimized-4mk1