# 007 — Best Time to Buy and Sell Stock

<div class="problem-source" markdown="1">

<p class="source-label" id="source">Problem link ও উৎস</p>

- **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 — "এ পর্যন্ত সবচেয়ে ছোট কত দেখেছি" মনে রাখা

</div>

## প্রশ্ন ও উদাহরণ {#problem}

### সহজ করে প্রশ্ন {#1-problem-in-simple-words}

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

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

### Input ও output {#8-example-input-and-output}

```text
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-এ বেচো)
```

### চেনা উদাহরণে বোঝা {#6-real-life-analogy}

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

## ভিত্তির ধারণা {#idea}

### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}

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

### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}

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

### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}

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

### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}

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

## ধাপে ধাপে সমাধান {#walkthrough}

### প্রথম সরল উপায় {#9-brute-force-thinking}

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

```text
best = 0
for i in range(n):
    for j in range(i+1, n):
        best = max(best, prices[j] - prices[i])
```

### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}

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

### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}

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

### আরও কম কাজে সমাধান {#12-optimized-intuition}

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

### ভাবনার পরিবর্তন {#13-thinking-tweak}

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

### ছবিতে বোঝা {#7-visual-explanation}

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

```text
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-এ ধাপে ধাপে {#14-step-by-step-dry-run}

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`।

## কোড ও ব্যাখ্যা {#code}

### Python {#15-python-solution}

```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!")
```

### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}

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

### Output মিলিয়ে দেখা {#17-output-walkthrough}

`[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 {#25-javascript-solution-with-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 {#26-typescript-solution-with-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 ভাঙে না।

## খরচ ও সাধারণ ভুল {#cost}

### সময় {#18-time-complexity}

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

### অতিরিক্ত জায়গা {#19-space-complexity}

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

### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}

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

## শেখা ও পরের অনুশীলন {#practice}

### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}

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

### পরের অনুশীলন {#22-similar-harder-problems}

- Best Time to Buy and Sell Stock II (যত খুশি transaction) — <https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/>
- Maximum Subarray (Kadane) — <https://leetcode.com/problems/maximum-subarray/> (#11)
- Best Time to Buy and Sell Stock with Cooldown — <https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/>

### কৌশলটি মনে রাখুন {#23-pattern-learned}

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

### নিজেকে যাচাই করুন {#24-final-summary}

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

### কোথায় কাজে লাগে {#27-real-world-use}

- **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।