# 015 — Next Greater Element II

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

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

- **Original source:** Classic monotonic-stack exercise (circular)
- **Platform:** LeetCode — <https://leetcode.com/problems/next-greater-element-ii/>
- **Topic:** stack (monotonic, circular)
- **Difficulty:** Medium
- **Pattern:** monotonic stack — circular
- **Basic idea inherited from:** Problem 9 (daily temperatures / next greater) + "array-দুবার-scan" trick

</div>

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

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

তোমাকে একটা **circular** array দেওয়া আছে — মানে শেষ element-এর পরে আবার প্রথম element আসে, রিং-এর মতো। প্রতিটা element-এর জন্য তার **next greater element** বের করতে হবে: রিং বরাবর সামনে এগোতে গিয়ে প্রথম যে value তার চেয়ে strictly বড়। ঘুরে এসেও না পেলে উত্তর `-1`।

```text
nums : [1, 2, 1]   (circular: ...1,2,1,1,2,1...)
ans  : [2,-1, 2]
- index 0 (1): সামনে 2 -> 2
- index 1 (2): সামনে 1, তারপর wrap করে 1,2... কেউ বড় নয় -> -1
- index 2 (1): wrap করে 1, তারপর 2 -> 2
```

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

```text
Input : [1, 2, 1]      -> Output: [2, -1, 2]
Input : [1, 2, 3, 4, 3]-> Output: [2, 3, 4, -1, 4]
Input : [5, 4, 3, 2, 1]-> Output: [-1, 5, 5, 5, 5]   (wrap করে সবাই 5 পায়)

Edge case 1 (একটা element) : [1]       -> [-1]
Edge case 2 (সব সমান)      : [1, 1, 1] -> [-1, -1, -1]  (strictly বড় নেই)
Edge case 3 (কঠোর বাড়তি)   : [1, 2, 3] -> [2, 3, -1]
```

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

ভাবো একটা গোল টেবিলে কয়েকজন বসে আছে, প্রত্যেকের হাতে একটা সংখ্যা-কার্ড। প্রত্যেকে জানতে চায় — ঘড়ির কাঁটার দিকে এগোলে প্রথম কে তার চেয়ে বড় সংখ্যা ধরে আছে। টেবিল গোল বলে তুমি নিজের জায়গা পেরিয়েও খুঁজতে পারো — তাই পুরো টেবিল একবার ঘুরে দেখলেই হয়। কেউ যদি পুরো চক্করেও বড় কাউকে না পায়, সে বুঝে নেয় "আমিই সবচেয়ে বড়" → `-1`।

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

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

এটা **Problem 9 (next greater, monotonic stack)**-এর সাথে একটা ছোট কিন্তু চমৎকার মোচড় — array **circular**। মূল machinery হুবহু এক: index-এর একটা decreasing stack, নতুন element এসে নিজের চেয়ে ছোটদের answer deliver করে। নতুন উপাদান শুধু **array দুবার scan** করার trick — index `i % n` দিয়ে — যাতে wrap-around-এর next greater-ও ধরা পড়ে।

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

লুকানো logic: একটা circular array-তে যেকোনো element-এর next greater খুঁজতে হলে বড়জোর আর একবার পুরো array ঘুরলেই যথেষ্ট — কারণ এক পূর্ণ চক্করেই সব সম্ভাব্য পরবর্তী element একবার করে দেখা হয়ে যায়। তাই আমরা `2*n` ধাপ hাঁটি, প্রতিবার আসল index `i % n` ব্যবহার করি।

invariant একই থাকে: stack-এ থাকে এমন index-রা যাদের answer এখনো অজানা, তাদের value নিচ-থেকে-উপর decreasing। দ্বিতীয় চক্করে আমরা শুধু আগের চক্করে অমীমাংসিতদের resolve করি — নতুন করে কাউকে push করি না।

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

একটা **monotonic stack** যেখানে **index** রাখি (`Python`-এ সাধারণ `list`)। সাথে একটা `result` array শুরুতে সব `-1` দিয়ে ভরা — যে element ঘুরেও বড় কিছু পায় না, তার `-1`-ই থেকে যায়। index রাখি যাতে `result[idx]`-এ সরাসরি লিখতে পারি।

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

"next greater" = "সবচেয়ে কাছের সামনের বড় value" — monotonic stack-এর ক্লাসিক কাজ। circular অংশটা structure বদলায় না, শুধু loop দ্বিগুণ চালাই। প্রতিটা index বড়জোর একবার push আর একবার pop হয় (push শুধু প্রথম চক্করে), তাই `2*n` iteration সত্ত্বেও কাজ O(n)। index রাখায় answer লেখা O(1)।

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

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

সরল চিন্তা: প্রতিটা index `i`-এর জন্য `j = 1, 2, ..., n-1` ধাপ সামনে এগোও, প্রতিবার circular index `(i + j) % n` দেখো; প্রথম যেখানে `nums[(i+j)%n] > nums[i]` সেখানে থেমে সেই value লেখো; পুরো চক্করেও না পেলে `-1`।

```text
for i: for j in 1..n-1: if nums[(i+j)%n] > nums[i]: ans=that; break
না পেলে ans[i] = -1
```

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

প্রতিটা element-এর জন্য সবচেয়ে খারাপ ক্ষেত্রে প্রায় পুরো রিং (`n-1` ধাপ) ঘুরতে হয় → **O(n^2)**। বড় বা strictly-নামতে-থাকা array-তে এটা খুবই ব্যয়বহুল, আর একই element বারবার অন্যদের খোঁজে scan হয়। monotonic stack প্রতিটা element-কে বড়জোর একবার ছুঁয়ে O(n)-তে শেষ করে।

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

মূল observation: linear next-greater-এর সমস্যা circular-এ পরিণত হয় শুধু "array-টা মাথায় দুবার জোড়া আছে" ভাবলে — `[1,2,1]`-কে `[1,2,1,1,2,1]` ভাবো। তখন প্রথম অর্ধেকের যে কারো wrap-around answer দ্বিতীয় অর্ধেকেই পাওয়া যায়। আর monotonic stack-এর "নতুন এসে ছোটদের resolve করে" idea অবিকল কাজ করে।

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

`result` সব `-1` দিয়ে শুরু করো, index-এর একটা decreasing stack রাখো। `i` চালাও `0` থেকে `2*n - 1`। প্রতিবার আসল index `idx = i % n`; যতক্ষণ stack খালি নয় আর top-এর value `nums[idx]`-এর চেয়ে ছোট, ততক্ষণ pop করে pop-করা index-এর `result`-এ `nums[idx]` লেখো। তারপর — শুধু প্রথম চক্করে (`i < n`) — `idx` push করো। দ্বিতীয় চক্কর শুধু অমীমাংসিতদের resolve করে।

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

**মোচড়:** circular-কে আলাদা সমস্যা না ভেবে ভাবো "array-টা পরপর দুবার লেখা, আমি শুধু index মুড়ে নিচ্ছি `% n` দিয়ে"। তখন একটা পরিচিত linear monotonic-stack solution-ই প্রায় হুবহু কাজ করে — শুধু loop দ্বিগুণ আর দ্বিতীয়বার push বন্ধ।

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

`[1, 2, 1]`, `n = 3`, তাই `i` চলে `0..5`, আসল index `i % 3` (stack-এ index, top ডানে):

```text
i  idx val  action                                   stack   result
0   0   1   কেউ নেই -> push (i<n)                     [0]     [-1,-1,-1]
1   1   2   nums[0]=1<2 -> pop0, res[0]=2; push1      [1]     [2,-1,-1]
2   2   1   nums[1]=2<1? না -> push2                  [1,2]   [2,-1,-1]
3   0   1   nums[2]=1<1? না -> (i>=n, push না)        [1,2]   [2,-1,-1]
4   1   2   nums[2]=1<2 -> pop2, res[2]=2;
            nums[1]=2<2? না -> (push না)              [1]     [2,-1, 2]
5   2   1   nums[1]=2<1? না -> (push না)              [1]     [2,-1, 2]
end index 1 কখনো resolve হয়নি -> res[1]=-1
result: [2, -1, 2]
```

### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}

Input `[1, 2, 3]`, `n = 3`:

1. `result = [-1, -1, -1]`, `stack = []`
2. `i=0, idx=0, val=1` — stack খালি; `i<3` push → `stack=[0]`
3. `i=1, idx=1, val=2` — `nums[0]=1<2` pop 0, `result[0]=2`; push 1 → `stack=[1]`, `result=[2,-1,-1]`
4. `i=2, idx=2, val=3` — `nums[1]=2<3` pop 1, `result[1]=3`; push 2 → `stack=[2]`, `result=[2,3,-1]`
5. `i=3, idx=0, val=1` — `nums[2]=3<1?` না; `i>=3`, push না
6. `i=4, idx=1, val=2` — `nums[2]=3<2?` না; push না
7. `i=5, idx=2, val=3` — `nums[2]=3<3?` না; push না
8. শেষ → index 2 কখনো বড় কিছু পায়নি, `result=[2,3,-1]`

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

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

```python
def next_greater_elements(nums):
    n = len(nums)
    result = [-1] * n
    stack = []                                   # index দের stack, value decreasing
    for i in range(2 * n):                        # array দুবার scan
        idx = i % n
        while stack and nums[stack[-1]] < nums[idx]:
            result[stack.pop()] = nums[idx]      # ছোটদের next greater পাওয়া গেল
        if i < n:
            stack.append(idx)                    # push শুধু প্রথম চক্করে
    return result

# ---- tests ----
assert next_greater_elements([1, 2, 1]) == [2, -1, 2]
assert next_greater_elements([1, 2, 3, 4, 3]) == [2, 3, 4, -1, 4]
assert next_greater_elements([5, 4, 3, 2, 1]) == [-1, 5, 5, 5, 5]   # wrap
assert next_greater_elements([1]) == [-1]                           # একটা element
assert next_greater_elements([1, 1, 1]) == [-1, -1, -1]             # সব সমান
assert next_greater_elements([1, 2, 3]) == [2, 3, -1]               # কঠোর বাড়তি
print("সব test pass!")
```

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

- `result = [-1] * n` — default `-1`; ঘুরেও বড় না পেলে এটাই থাকে।
- `stack = []` — index জমবে, value decreasing থাকবে।
- `for i in range(2 * n):` — দুবার scan, circular wrap সামলাতে।
- `idx = i % n` — `i` যত বড়ই হোক, আসল array index `0..n-1`-এ মুড়ে নেয়।
- `while stack and nums[stack[-1]] < nums[idx]:` — top-এর value ছোট হলে তার next greater হলো `nums[idx]`।
- `result[stack.pop()] = nums[idx]` — pop করা index-এর answer লেখা।
- `if i < n: stack.append(idx)` — push শুধু প্রথম চক্করে; দ্বিতীয় চক্কর কেবল অবশিষ্টদের resolve করে, নতুন কাউকে যোগ করে না।

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

`next_greater_elements([5,4,3,2,1])` → প্রথম চক্করে সবাই decreasing বলে কেউ resolve হয় না, সবাই stack-এ; দ্বিতীয় চক্করে `5` এসে `1,2,3,4` সবাইকে resolve করে (`-1, 5, 5, 5, 5`), আর `5` নিজে কখনো বড় কিছু পায় না → `-1`। `next_greater_elements([1,1,1])` → `<` strict, সমান value pop করায় না, সব `-1`। সব assert pass করে শেষে print: `সব test pass!`।

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

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

**O(n)** — loop `2n` বার চললেও প্রতিটা index বড়জোর একবার push আর একবার pop হয়; মোট stack operation `≤ 2n`।

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

**O(n)** — stack সবচেয়ে খারাপ ক্ষেত্রে (strictly নামতে-থাকা array) প্রথম চক্করের পর সব `n` index ধরে রাখে; result-ও O(n)।

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

- দ্বিতীয় চক্করেও push করা — তখন একই index দুবার ঢুকে আবার অমীমাংসিত থেকে যায়; push শুধু `i < n`-এ।
- `idx = i % n` ভুলে `i` সরাসরি ব্যবহার করা — index array-র বাইরে চলে যায়।
- `<` বনাম `<=` — "strictly greater" চাই, তাই সমান value pop করানো যাবে না; `nums[stack[-1]] < nums[idx]` লাগে।

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

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

ভিত্তি: Problem 9-এর monotonic stack (next greater), Problem 7-এর "most recent unfinished"। chapter-এর [../patterns.md](../patterns.md)-এর Pattern 4 (Monotonic Stack) এখানে circular রূপে; নতুন অংশ শুধু array-দুবার-scan।

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

- Daily Temperatures (linear next greater) — <https://leetcode.com/problems/daily-temperatures/> (এই tracker-এর #9)
- Online Stock Span — <https://leetcode.com/problems/online-stock-span/> (#16)
- Largest Rectangle in Histogram — <https://leetcode.com/problems/largest-rectangle-in-histogram/> (#20)

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

**Circular monotonic stack:** "circular array"-তে next/previous greater দেখলে array দুবার scan করো (`i % n`), কিন্তু push শুধু প্রথম চক্করে; বাকি সব linear next-greater-এর মতো।

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

ভবিষ্যতের আমাকে: circular = array দুবার ভাবো; `for i in range(2*n)`, `idx = i % n`, push শুধু `i < n`-এ, default `-1`। monotonic-stack core একই — নতুন এসে ছোটদের resolve করে। "circular", "wrap around", "next greater" দেখলে এই trick মনে করবে।

---

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