Problem link ও উৎস
- **Original source:** Classic monotonic-stack exercise
- **Platform:** LeetCode —
- **Topic:** stack, hash map
- **Difficulty:** Easy
- **Pattern:** monotonic stack
- **Basic idea inherited from:** matching — "most recent unresolved" element-কে নতুন আসা element answer দিয়ে যায়
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে দুটো array দেওয়া আছে: `nums1` আর `nums2`, যেখানে `nums1`-এর সব element `nums2`-তেও আছে (`nums1` হলো `nums2`-এর একটা subset)। `nums2`-তে প্রতিটা element-এর জন্য তার **ডানদিকের প্রথম strictly greater value** খুঁজতে হবে। তারপর `nums1`-এর প্রতিটা element-এর সেই answer ফেরত দিতে হবে। ডানদিকে বড় কিছু না থাকলে answer `-1`।
### Input ও output {#8-example-input-and-output}
```text
Input : nums1=[4,1,2], nums2=[1,3,4,2] -> Output: [-1, 3, -1]
Input : nums1=[2,4], nums2=[1,2,3,4] -> Output: [3, -1]
Edge case (সবচেয়ে বড়টাই শেষে): nums1=[4], nums2=[1,2,3,4] -> [-1]
Edge case (একটাই element): nums1=[1], nums2=[1] -> [-1]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
লাইনে দাঁড়ানো একদল মানুষ ভাবো, প্রত্যেকে নিজের চেয়ে লম্বা প্রথম মানুষ খুঁজছে যে তাদের পরে আসবে। যতক্ষণ কেউ লম্বা না আসছে, খাটো মানুষগুলো "অপেক্ষায়" দাঁড়িয়ে থাকে (stack)। একজন লম্বা মানুষ এলে, তার সামনে দাঁড়ানো যত খাটো মানুষ আছে — সবাই একসাথে উত্তর পেয়ে যায় ("ও-ই আমার next greater!") আর লাইন ছেড়ে দেয়। নতুন লম্বা মানুষ তখন অপেক্ষমাণদের পেছনে দাঁড়ায়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা problem 1-এর **matching** discipline-এর বুদ্ধিদীপ্ত রূপ। সেখানে stack ধরে রাখত "খোলা কিন্তু এখনো বন্ধ হয়নি" bracket; এখানে stack ধরে রাখে "এখনো নিজের next-greater answer পায়নি" এমন element। দুটোতেই: একটা নতুন ঘটনা এসে সবচেয়ে recent unresolved জিনিসগুলোকে *resolve* করে দেয়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **monotonic stack invariant**: আমরা এমন element-দের একটা stack রাখি যাদের answer এখনো অজানা, আর তাদের value গুলো bottom-থেকে-top **decreasing**। যখন একটা নতুন value আসে যেটা stack-এর top-এর চেয়ে বড়, সে top-কে "হারায়" — মানে এটাই top-এর next greater। সে এভাবে যতজনকে হারায় সবাইকে answer দিয়ে pop করে, তারপর নিজে stack-এ যোগ দেয়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
- একটা **monotonic stack** (`list`) — যেসব value এখনো next-greater খুঁজছে।
- একটা **hash map** (`dict`) — প্রতিটা value-র জন্য তার next greater সংরক্ষণ করতে, যাতে `nums1`-এর answer O(1)-তে তোলা যায়।
(value গুলো distinct, তাই value-কে সরাসরি key হিসেবে ব্যবহার করা নিরাপদ।)
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতিটা element নিজের জন্য ডানে search করলে O(n^2) হতো। কিন্তু stack দিয়ে আমরা একবার scan-এ কাজ সারি: একটা নতুন element তার চেয়ে ছোট, অপেক্ষমাণ সব element-কে এক ধাক্কায় answer দিয়ে দেয়। প্রতিটা element একবার push, বড়জোর একবার pop — তাই O(n)। hash map থাকায় `nums2`-এর result থেকে `nums1`-এর উত্তর তোলা O(1)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সহজ চিন্তা: `nums1`-এর প্রতিটা x-এর জন্য `nums2`-তে x খুঁজি, তারপর সেখান থেকে ডানে হেঁটে প্রথম strictly বড় value খুঁজি।
```text
প্রতিটা x:
nums2-তে x-এর index j খুঁজো
j+1 থেকে শেষ পর্যন্ত হাঁটো; প্রথম nums2[k] > x পেলে সেটাই answer
না পেলে -1
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা x-এর জন্য `nums2`-তে খোঁজা O(n), তারপর ডানে হাঁটা আরও O(n) → প্রতি x-এ O(n), মোট **O(n*m)** (প্রায় O(n^2))। একই scanning বারবার হয়। monotonic stack এই পুনরাবৃত্তি দূর করে একবার scan-এ সব answer বের করে — O(n)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **প্রশ্নটা উল্টে দাও।** প্রতিটা element নিজের next greater *সামনে খুঁজতে* না গিয়ে, প্রতিটা নতুন element-কে দিয়ে answer *পেছনে deliver* করাও — যাদের সে dominate (হারায়) করে তাদের সবাইকে। তখন প্রতিটা element একবার push, একবার pop — O(n)।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`nums2`-তে একবার হাঁটো, একটা stack রেখে যেটায় এখনো-answer-না-পাওয়া value গুলো decreasing order-এ থাকে। প্রতিটা নতুন `num`-এ: যতক্ষণ stack-এর top `num`-এর চেয়ে ছোট, ততক্ষণ top-কে pop করে map-এ `top -> num` লিখে দাও (এটাই top-এর next greater)। তারপর `num` push করো। শেষে `nums1`-এর প্রতিটা element map থেকে তোলো (না পেলে `-1`)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "আমার next greater কে?" — প্রতিটা element-এর এই egocentric প্রশ্নটা বদলে দাও "আমি কাদের next greater?" — নতুন আসা বড় element নিজেই ঘোষণা করে দেয় সে কাদের উত্তর। এক-একটা element একবারের বেশি pop হয় না, তাই nested-দেখতে loop সত্ত্বেও মোট কাজ linear।
### ছবিতে বোঝা {#7-visual-explanation}
`nums2 = [1, 3, 4, 2]`-এর next greater বের করি (stack value রাখে):
```text
num action stack next_greater map
1 কেউ অপেক্ষায় নেই -> push [1]
3 3 > 1 -> ans(1)=3, pop 1; তারপর push 3 [3] {1:3}
4 4 > 3 -> ans(3)=4, pop 3; তারপর push 4 [4] {1:3, 3:4}
2 2 < 4 -> কাউকে হারায় না -> push [4, 2] {1:3, 3:4}
end stack-এ 4,2 কখনো হারেনি -> answer -1 (map-এ নেই)
```
এবার `nums1 = [4, 1, 2]` map থেকে তোলো: `4 -> -1`, `1 -> 3`, `2 -> -1` → `[-1, 3, -1]`।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `nums1=[2,4]`, `nums2=[1,2,3,4]`:
`nums2` scan:
1. `num=1` → stack খালি → push → `stack=[1]`
2. `num=2` → `2 > 1` → `map[1]=2`, pop 1; তারপর push 2 → `stack=[2]`, `map={1:2}`
3. `num=3` → `3 > 2` → `map[2]=3`, pop 2; তারপর push 3 → `stack=[3]`, `map={1:2, 2:3}`
4. `num=4` → `4 > 3` → `map[3]=4`, pop 3; তারপর push 4 → `stack=[4]`, `map={1:2, 2:3, 3:4}`
5. end → `4` কখনো হারেনি → map-এ নেই
`nums1` থেকে তোলো: `2 -> map.get(2,-1)=3`, `4 -> map.get(4,-1)=-1` → return `[3, -1]`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def next_greater_element(nums1, nums2):
next_greater = {}
stack = []
for num in nums2:
while stack and stack[-1] < num: # num যাদের হারায়
next_greater[stack.pop()] = num # তাদের answer = num
stack.append(num) # num এখন অপেক্ষমাণ
return [next_greater.get(x, -1) for x in nums1]
# ---- tests ----
assert next_greater_element([4, 1, 2], [1, 3, 4, 2]) == [-1, 3, -1]
assert next_greater_element([2, 4], [1, 2, 3, 4]) == [3, -1]
assert next_greater_element([4], [1, 2, 3, 4]) == [-1] # সবচেয়ে বড়
assert next_greater_element([1], [1]) == [-1] # একটাই element
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `next_greater = {}` — value → তার next greater, lookup O(1)।
- `stack = []` — এখনো answer-না-পাওয়া value, decreasing order-এ।
- `while stack and stack[-1] < num:` — top যদি `num`-এর চেয়ে ছোট হয়, `num`-ই তার next greater।
- `next_greater[stack.pop()] = num` — সেই top-কে pop করে তার answer লিখে দাও; loop চলতে থাকে যতক্ষণ top < num।
- `stack.append(num)` — `num` এবার নিজে অপেক্ষমাণ হিসেবে stack-এ।
- `return [...]` — `nums1`-এর প্রতিটা element map থেকে তোলো; না থাকলে `-1`।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`next_greater_element([2,4], [1,2,3,4])` → section 14-এর মতো `map={1:2, 2:3, 3:4}`; `nums1` থেকে `2->3`, `4->-1` → `[3, -1]`। `next_greater_element([4,1,2],[1,3,4,2])` → `map={1:3, 3:4}`; `4->-1, 1->3, 2->-1` → `[-1, 3, -1]`। সব assert pass — print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function nextGreaterElement(nums1, nums2) {
const nextGreater = new Map(); // value -> তার next greater
const stack = []; // এখনো answer-না-পাওয়া value, decreasing
for (const num of nums2) {
while (stack.length && stack[stack.length - 1] < num) {
nextGreater.set(stack.pop(), num); // num যাদের হারায় তাদের answer
}
stack.push(num); // num এখন অপেক্ষমাণ
}
return nums1.map(x => nextGreater.has(x) ? nextGreater.get(x) : -1);
}
// ---- test cases ----
assert(JSON.stringify(nextGreaterElement([4, 1, 2], [1, 3, 4, 2])) === JSON.stringify([-1, 3, -1]), "ex1");
assert(JSON.stringify(nextGreaterElement([2, 4], [1, 2, 3, 4])) === JSON.stringify([3, -1]), "ex2");
assert(JSON.stringify(nextGreaterElement([4], [1, 2, 3, 4])) === JSON.stringify([-1]), "largest");
assert(JSON.stringify(nextGreaterElement([1], [1])) === JSON.stringify([-1]), "single");
console.log("সব JS test pass!");
```
> **JS টীকা:** lookup-এর জন্য `Map` নাও, plain object নয় — `Map` যেকোনো type-এর key রাখে আর `.has()`/`.get()` পরিষ্কার, আবার number key object-এ string-এ রূপান্তরিত হওয়ার বাগও এড়ায়। array তুলনা করতে `===` কাজ করে না (reference তুলনা), তাই `JSON.stringify` দিয়ে মিলিয়েছি। `stack[stack.length - 1]` হলো top দেখার idiom (Python-এর `stack[-1]`-এর সমতুল্য)।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
const nextGreater = new Map