কনটেন্টে যান

007 — Best Time to Buy and Sell Stock

Problem link ও উৎস

  • Original source: Classic running-min / one-pass exercise
  • Platform: LeetCode — https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
  • Topic: array
  • Difficulty: Easy
  • Pattern: running min (Kadane-flavored one pass)
  • Basic idea inherited from: prefix-min thinking, math level 5 — "এ পর্যন্ত সবচেয়ে ছোট কত দেখেছি" মনে রাখা

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা array prices দেওয়া, যেখানে prices[i] হলো i-তম দিনে একটা share-এর দাম। তুমি একবার কিনে পরে একবার বেচতে পারো (আগে কিনতে হবে, পরে বেচতে)। সবচেয়ে বেশি কত profit করা সম্ভব? কোনো profit সম্ভব না হলে 0।

উদাহরণ
prices = [7, 1, 5, 3, 6, 4]
সবচেয়ে সস্তা দিনে (1) কেনো, পরে বড় দিনে (6) বেচো -> profit 5

Input ও output

উদাহরণ
Input : [7, 1, 5, 3, 6, 4]  -> 5   (1-এ কেনো, 6-এ বেচো)
Input : [7, 6, 4, 3, 1]     -> 0   (দাম শুধু কমেছে, লাভ নেই)

Edge case 1 (খালি):    []      -> 0
Edge case 2 (V-shape): [2,4,1] -> 2 (2-এ কেনো, 4-এ বেচো)

চেনা উদাহরণে বোঝা

তুমি প্রতিদিন একটা জিনিসের দাম খাতায় টুকছ। আজ যদি বেচতে, তোমার সেরা লাভ = আজকের দাম − এ যাবৎ দেখা সবচেয়ে সস্তা দিন। তাই শুধু দুটো জিনিস মনে রাখো: "এখন পর্যন্ত সবচেয়ে সস্তা কত" আর "এখন পর্যন্ত সেরা লাভ কত"।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

ভিত math level 5-এর prefix-min thinking: আজকের দিনে বেচলে সেরা profit = আজকের দাম − আগের দিনগুলোর সবচেয়ে কম দাম। তাই বাঁ থেকে হাঁটতে হাঁটতে "এ পর্যন্ত দেখা minimum" মনে রাখলেই হয়। গভীর derivation: ../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/।

ভেতরের যুক্তি

লুকানো logic: max profit = max over j ( prices[j] - min over i<j prices[i] )। অর্থাৎ প্রতিটা "বেচার দিন" j-এর জন্য সেরা "কেনার দিন" হলো তার আগের সবচেয়ে সস্তা দিন। এই দুটো (running min আর running best) একসাথে এক pass-এ track করা যায় — এটাই Kadane-এর চিন্তার ছোট ভাই।

কী দিয়ে তথ্য রাখব

কোনো data structure লাগে না — শুধু দুটো scalar variable: min_price (এ পর্যন্ত সবচেয়ে কম দাম) আর best (এ পর্যন্ত সেরা profit)। O(1) extra space।

এটি কেন উপযুক্ত

পুরো prefix-min array জমিয়ে রাখার দরকার নেই — যেকোনো দিনে শুধু এই মুহূর্ত পর্যন্ত minimum-টুকুই দরকার, যা একটা variable-এ ধরে রাখা যায়। array-র O(1) sequential read + দুটো variable update = সবচেয়ে হালকা সমাধান।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: প্রতিটা জোড়া দিন (i, j) যেখানে i < j, profit prices[j] - prices[i] হিসাব করে সবচেয়ে বড়টা রাখি — দুটো nested loop।

উদাহরণ
best = 0
for i in range(n):
    for j in range(i+1, n):
        best = max(best, prices[j] - prices[i])

কোথায় বেশি কাজ হচ্ছে

দুটো nested loop মানে O(n^2) জোড়া। বারবার একই কাজ: প্রতিটা বেচার দিনের জন্য আগের সব দিন আবার scan করে minimum খুঁজছি — অথচ সেই minimum এক pass-এ চলতে চলতেই track করা যায়।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: একটা বেচার দিন j fix করলে, সেরা কেনার দিন সবসময় তার আগের সবচেয়ে সস্তা দিন — আর কিছু না। তাই সব জোড়া না দেখে শুধু running minimum রাখলেই প্রতিটা দিনের সেরা profit পাওয়া যায়।

আরও কম কাজে সমাধান

বাঁ থেকে ডানে একবার হাঁটো। প্রতিটা দাম p-এ: যদি p এ-যাবৎ minimum-এর চেয়ে কম, min_price update করো (নতুন সস্তা কেনার দিন)। নাহলে p - min_price দিয়ে best update করার চেষ্টা করো (আজ বেচলে কত লাভ)। এক pass, O(n)।

ভাবনার পরিবর্তন

মোচড়: "সব (কেনা, বেচা) জোড়া try করব" (O(n^2)) ভুলে গিয়ে ভাবো "আজ বেচলে সেরা লাভ = আজকের দাম − এ যাবৎ সবচেয়ে সস্তা।" একটাই running minimum পুরো ভেতরের loop-টা মুছে দেয়।

ছবিতে বোঝা

prices = [7, 1, 5, 3, 6, 4]:

উদাহরণ
min_price শুরুতে +inf, best=0

p=7: 7<inf      -> min=7
p=1: 1<7        -> min=1
p=5: 5-1=4 > 0  -> best=4
p=3: 3-1=2      (best 4 অপরিবর্তিত)
p=6: 6-1=5 > 4  -> best=5
p=4: 4-1=3      (best 5 অপরিবর্তিত)

answer: best = 5

ছোট input-এ ধাপে ধাপে

Input [2, 4, 1]:

  1. শুরু: min_price=+inf, best=0।
  2. p=2: 2 < inf → min_price=2।
  3. p=4: 4 < 2 মিথ্যা → 4 - 2 = 2 > best → best=2।
  4. p=1: 1 < 2 সত্য → min_price=1 (best 2 অপরিবর্তিত)।
  5. ফল: best = 2।

কোড ও ব্যাখ্যা

Python

Python
def max_profit(prices):
    min_price = float("inf")          # এ যাবৎ সবচেয়ে কম দাম
    best = 0                          # এ যাবৎ সেরা profit
    for p in prices:
        if p < min_price:
            min_price = p             # নতুন সস্তা কেনার দিন
        elif p - min_price > best:
            best = p - min_price      # আজ বেচলে আরো ভালো লাভ
    return best

# ---- tests ----
assert max_profit([7, 1, 5, 3, 6, 4]) == 5
assert max_profit([7, 6, 4, 3, 1]) == 0     # লাভ নেই
assert max_profit([]) == 0                   # খালি
assert max_profit([2, 4, 1]) == 2
print("সব test pass!")

কোডের প্রতিটি অংশ

  • min_price = float("inf") — শুরুতে কোনো দাম দেখিনি, তাই "অসীম বড়" ধরি যাতে প্রথম দামই minimum হয়।
  • best = 0 — কোনো লাভ না হলে উত্তর 0 (কিছু না কেনা)।
  • if p < min_price — আজকের দাম এ যাবৎ সবচেয়ে সস্তা হলে কেনার দিন update।
  • elif p - min_price > best — নাহলে আজ বেচলে লাভ আগের সেরা ছাড়াবে কিনা দেখি।
  • return best — পুরো pass শেষে সেরা সম্ভব profit।

Output মিলিয়ে দেখা

[7,1,5,3,6,4]: min নামতে নামতে 1, তারপর 6-এর দিন 6-1=5 সেরা → 5, assert pass। শুধু কমতে থাকা array-তে best 0-ই থাকে; খালি array-তে loop চলে না, 0; [2,4,1] দেয় 2। শেষে print: সব test pass!।

JavaScript ও test cases

running min + best — এক pass-এ "এ যাবৎ সবচেয়ে সস্তা" আর "এ যাবৎ সেরা profit" track করি।

JavaScript
// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function maxProfit(prices) {
  let minPrice = Infinity;          // এ যাবৎ সবচেয়ে কম দাম
  let best = 0;                      // এ যাবৎ সেরা profit (লাভ না হলে 0)
  for (const p of prices) {
    if (p < minPrice) minPrice = p;                 // নতুন সস্তা কেনার দিন
    else if (p - minPrice > best) best = p - minPrice;  // আজ বেচলে ভালো লাভ?
  }
  return best;
}

// ---- test cases (file-এর example + edge case) ----
assert(maxProfit([7, 1, 5, 3, 6, 4]) === 5, "1-এ কেনো, 6-এ বেচো");
assert(maxProfit([7, 6, 4, 3, 1]) === 0, "শুধু কমেছে → 0");
assert(maxProfit([]) === 0, "খালি");
assert(maxProfit([2, 4, 1]) === 2, "V-shape");
assert(maxProfit([1]) === 0, "এক দিন → লাভ নেই");
assert(maxProfit([3, 3, 3]) === 0, "সমান দাম → 0");
console.log("সব JS test pass!");

JS টীকা: "অসীম বড়" শুরু হিসেবে Infinity (Python float("inf")-এর বদলি), যাতে প্রথম দামই minPrice হয়। best 0 থেকে শুরু — লাভ না হলে উত্তর 0 (কিছু না কেনা), কখনো negative নয়। else if যথেষ্ট: যেদিন নতুন min, সেদিন বেচলে লাভ ≤ 0।

TypeScript ও test cases

TypeScript
function maxProfit(prices: number[]): number {
  let minPrice = Infinity;
  let best = 0;
  for (const p of prices) {
    if (p < minPrice) minPrice = p;
    else if (p - minPrice > best) best = p - minPrice;
  }
  return best;
}

function expect(actual: number, expected: number, msg = ""): void {
  if (actual !== expected) throw new Error(`FAIL ${msg}: ${actual}`);
}

const cases: ReadonlyArray<readonly [number[], number]> = [
  [[7, 1, 5, 3, 6, 4], 5], [[7, 6, 4, 3, 1], 0], [[], 0],
  [[2, 4, 1], 2], [[1], 0], [[3, 3, 3], 0],
];
for (const [arr, want] of cases) expect(maxProfit(arr), want, `[${arr}]`);
console.log("সব TS test pass!");

TS টীকা: prices: number[] ও return number declare করায় ভুল ধরনের input বাদ, আর profit সবসময় number — empty array-তেও 0 ফেরে, type ভাঙে না।

খরচ ও সাধারণ ভুল

সময়

O(n) — array-তে একবার হাঁটা; প্রতিটা step-এ O(1) compare/update।

অতিরিক্ত জায়গা

O(1) — শুধু দুটো scalar (min_price, best)।

যে ভুলগুলো এড়াতে হবে

  • best-কে negative হতে দেওয়া — কোনো লাভ না হলে উত্তর 0 (কিছু না করা), negative নয়।
  • আগে বেচে পরে কেনার ভুল — running minimum সবসময় current দিনের আগের দাম থেকে আসে বলে এই code-এ এটা আপনাআপনি ঠিক থাকে।
  • প্রতিটা দিনে min_price আর best দুটোই একসাথে update করার চেষ্টা — যেদিন নতুন min, সেদিন বেচলে লাভ ≤ 0, তাই elif যথেষ্ট।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: prefix-min / running aggregate (math level 5)। এটা Kadane (maximum subarray, #11)-এর জমজ — "best ending here" বনাম "best so far"। chapter-এর ../patterns.md-এর "Pattern 7 — Kadane's Algorithm" দেখো।

পরের অনুশীলন

কৌশলটি মনে রাখুন

Running min + running best (one pass): prefix-aggregate মনে রেখে প্রতিটা index-এ local সেরা decision — O(n) time, O(1) space, Kadane-ঘরানার।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "max profit = আজকের দাম − এ যাবৎ minimum; min আর best দুটোই এক pass-এ রাখো।" "best buy/sell" বা "max difference (later − earlier)" দেখলেই running-min মনে করবে।

কোথায় কাজে লাগে

  • Best buy/sell / max gain: কোনো time-series-এ "পরে − আগের সবচেয়ে ছোট" সর্বোচ্চ পার্থক্য — দাম, metric, score।
  • Running min/max tracking: dashboard-এ চলমান lowest/peak, drawdown হিসাব (finance, monitoring)।
  • One-pass aggregate: পুরো history না রেখে শুধু দরকারি running state — stream/online algorithm।
  • Kadane-গোত্রের decision: "best ending here vs best so far" — maximum subarray, max profit with cooldown-এর ভিত্তি। মূল pattern — "prefix-min মনে রেখে প্রতিটা index-এ local সেরা সিদ্ধান্ত (one pass, O(1) space)" — running aggregate, Kadane, sliding optimum জুড়ে বড় ছবিতে ফেরে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।