Leetcode 150 | Day 5: ಷೇರುಗಳನ್ನು ಖರೀದಿಸಲು ಮತ್ತು ಮಾರಾಟ ಮಾಡಲು ಉತ್ತಮ ಸಮಯ

Leetcode 121 ಒಂದು ಷೇರನ್ನು ಖರೀದಿಸಲು ಮತ್ತು ಮಾರಾಟ ಮಾಡಲು ಉತ್ತಮ ಸಮಯವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕೇಳುತ್ತದೆ. ನಿಮಗೆ ಬೆಲೆಗಳ ಒಂದು ಅರೇ (array) ನೀಡಲಾಗುತ್ತದೆ. ಪ್ರತಿ ಇಂಡೆಕ್ಸ್ ಒಂದು ದಿನವನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಆ ದಿನದ ಬೆಲೆ ಅದರ ಮೌಲ್ಯವಾಗಿರುತ್ತದೆ.

ಗುರಿ ಸರಳವಾಗಿದೆ. ಗರಿಷ್ಠ ಲಾಭವನ್ನು ಪಡೆಯಲು ಒಂದು ದಿನ ಖರೀದಿಸಿ ಮತ್ತು ಭವಿಷ್ಯದ ದಿನದಂದು ಮಾರಾಟ ಮಾಡಿ. ಯಾವುದೇ ಲಾಭ ಸಾಧ್ಯವಾಗದಿದ್ದರೆ, 0 ಅನ್ನು ಹಿಂತಿರುಗಿಸಿ.

ಸಮಸ್ಯೆಯ ಮಿತಿಗಳು (Problem Constraints):

  • ಅರೇ ಉದ್ದ 100,000 ವರೆಗೆ ಇರಬಹುದು.
  • ಬೆಲೆಗಳು 10,000 ವರೆಗೆ ಇರಬಹುದು.
  • ನೀವು ಖರೀದಿಸಿದ ನಂತರವೇ ಮಾರಾಟ ಮಾಡಬೇಕು.

ವಿಧಾನ 1: ಸರಳ ವಿಧಾನ (Brute Force)

Brute force ವಿಧಾನವು ಪ್ರತಿಯೊಂದು ಖರೀದಿ ಮತ್ತು ಮಾರಾಟದ ಜೋಡಿಗಳನ್ನು ಪರಿಶೀಲಿಸುತ್ತದೆ. ಇದು ಎರಡು ಲೂಪ್‌ಗಳನ್ನು (loops) ಬಳಸುತ್ತದೆ.

  • ಸಮಯದ ಸಂಕೀರ್ಣತೆ (Time Complexity): O(n²)
  • ಸಮಸ್ಯೆ: ಇದು ತುಂಬಾ ನಿಧಾನವಾಗಿದೆ.

ನಿಮ್ಮ ಬಳಿ 1,000 ದಿನಗಳಿದ್ದರೆ, ನೀವು 1,000,000 ಪರಿಶೀಲನೆಗಳನ್ನು ನಡೆಸುತ್ತೀರಿ. ನಿಮ್ಮ ಬಳಿ 100,000 ದಿನಗಳಿದ್ದರೆ, ನೀವು 10,000,000,000 ಪರಿಶೀಲನೆಗಳನ್ನು ನಡೆಸುತ್ತೀರಿ. ಇದು Leetcode ನಲ್ಲಿ 'timeout' ಆಗಲು ಕಾರಣವಾಗುತ್ತದೆ.

ವಿಧಾನ 2: ಉತ್ತಮಗೊಳಿಸಿದ ವಿಧಾನ (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] ನೊಂದಿಗೆ ಉದಾಹರಣೆಯ ಟ್ರೇಸ್ (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.

ಉತ್ತಮಗೊಳಿಸಿದ ಆವೃತ್ತಿಯು ಗೆಲ್ಲುತ್ತದೆ ಏಕೆಂದರೆ ಇದು ಪ್ರತಿ ಬೆಲೆಯನ್ನು ಕೇವಲ ಒಂದು ಬಾರಿ ಮಾತ್ರ ಪರಿಶೀಲಿಸುತ್ತದೆ. ಇದು ದೊಡ್ಡ ಡೇಟಾ ಸೆಟ್‌ಗಳಿಗೆ (datasets) ಉತ್ತಮವಾಗಿ ಹೊಂದಿಕೊಳ್ಳುತ್ತದೆ.

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