007 — Next Greater Element I

Source

• Original source: Classic monotonic-stack exercise
• Platform: LeetCode — https://leetcode.com/problems/next-greater-element-i/
• Topic: stack, hash map
• Difficulty: Easy
• Pattern: monotonic stack
• Basic idea inherited from: matching — "most recent unresolved" element-কে নতুন আসা element answer দিয়ে যায়

1. Problem in simple words

তোমাকে দুটো array দেওয়া আছে: nums1 আর nums2, যেখানে nums1-এর সব element nums2-তেও আছে (nums1 হলো nums2-এর একটা subset)। nums2-তে প্রতিটা element-এর জন্য তার ডানদিকের প্রথম strictly greater value খুঁজতে হবে। তারপর nums1-এর প্রতিটা element-এর সেই answer ফেরত দিতে হবে। ডানদিকে বড় কিছু না থাকলে answer -1।

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

6. Real-life analogy

লাইনে দাঁড়ানো একদল মানুষ ভাবো, প্রত্যেকে নিজের চেয়ে লম্বা প্রথম মানুষ খুঁজছে যে তাদের পরে আসবে। যতক্ষণ কেউ লম্বা না আসছে, খাটো মানুষগুলো "অপেক্ষায়" দাঁড়িয়ে থাকে (stack)। একজন লম্বা মানুষ এলে, তার সামনে দাঁড়ানো যত খাটো মানুষ আছে — সবাই একসাথে উত্তর পেয়ে যায় ("ও-ই আমার next greater!") আর লাইন ছেড়ে দেয়। নতুন লম্বা মানুষ তখন অপেক্ষমাণদের পেছনে দাঁড়ায়।

7. Visual explanation

nums2 = [1, 3, 4, 2]-এর next greater বের করি (stack value রাখে):

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

8. Example input and output

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]

9. Brute force thinking

সহজ চিন্তা: nums1-এর প্রতিটা x-এর জন্য nums2-তে x খুঁজি, তারপর সেখান থেকে ডানে হেঁটে প্রথম strictly বড় value খুঁজি।

প্রতিটা 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।

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]

15. Python solution

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।

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

18. Time complexity

O(n + m) — nums2-এর প্রতিটা element একবার push ও বড়জোর একবার pop (O(n)), nums1-এর প্রতিটা lookup O(1) (O(m))।

19. Space complexity

O(n) — stack ও hash map-এ মিলে nums2-এর element সংখ্যার সমানুপাতিক।

20. Common mistakes

• comparison-এ <-এর বদলে <= ব্যবহার — তাতে সমান value-ও pop হয়ে যায়, কিন্তু এখানে "strictly greater" চাই (distinct value বলে এই problem-এ পার্থক্য কম, তবু সাবধান)।
• map থেকে তোলার সময় missing key handle না করা — next_greater[x] সরাসরি লিখলে KeyError; .get(x, -1) ব্যবহার করো।
• nums1-এর জন্য আলাদা করে আবার O(n^2) search করা — পুরো লাভটাই হলো map precompute, সেটা ব্যবহার করো।

21. Which basic problem this inherits from

ভিত্তি: problem 1-এর "most recent unresolved" matching discipline; chapter-এর ../patterns.md-এর Pattern 4 (Monotonic Stack) আর ../concept.md-এর core invariant 4 (monotonic stack invariant)। এটা পুরো monotonic-stack পরিবারের প্রবেশদ্বার।

22. Similar harder problems

• Daily Temperatures (value-র বদলে distance) — https://leetcode.com/problems/daily-temperatures/ (এই tracker-এর #9)
• Next Greater Element II (circular array) — https://leetcode.com/problems/next-greater-element-ii/ (#15)
• Largest Rectangle in Histogram (previous/next smaller) — https://leetcode.com/problems/largest-rectangle-in-histogram/ (#20)

23. Pattern learned

Monotonic stack: decreasing stack-এ অপেক্ষমাণদের রাখো; নতুন বড় element এসে যাদের হারায় তাদের সবাইকে answer deliver করে — O(n)-তে "next greater / smaller"।

24. Final summary

ভবিষ্যতের আমাকে: "next/previous greater/smaller" দেখলেই monotonic stack। চাবি-চিন্তা: element-রা নিজের answer খুঁজতে যায় না, নতুন আসা element-ই পেছনে answer পৌঁছে দেয়। distinct value হলে hash map দিয়ে subset-এর answer তোলা সহজ।

25. JavaScript solution (with test cases)

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]-এর সমতুল্য)।

26. TypeScript solution (with test cases)

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  const nextGreater = new Map<number, number>();
  const stack: number[] = [];
  for (const num of nums2) {
    while (stack.length && stack[stack.length - 1] < num) {
      nextGreater.set(stack.pop()!, num);
    }
    stack.push(num);
  }
  return nums1.map(x => nextGreater.get(x) ?? -1);   // না থাকলে -1
}

function expect<T>(a: T, e: T, m = ""): void { if (a !== e) throw new Error(`FAIL ${m}`); }

expect(JSON.stringify(nextGreaterElement([4, 1, 2], [1, 3, 4, 2])), JSON.stringify([-1, 3, -1]), "ex1");
expect(JSON.stringify(nextGreaterElement([2, 4], [1, 2, 3, 4])), JSON.stringify([3, -1]), "ex2");
expect(JSON.stringify(nextGreaterElement([4], [1, 2, 3, 4])), JSON.stringify([-1]), "largest");
console.log("সব TS test pass!");

TS টীকা: Map<number, number> generic দিয়ে key ও value দুটোই number-এ বাঁধা — ভুল type ঢুকলে compile error। nextGreater.get(x) ?? -1 হলো nullish coalescing: get যদি undefined দেয় (key নেই) তবেই -1 বসে, কিন্তু value 0 হলে সেটা ভুল করে -1 হয় না (|| দিলে হতো)। এটাই missing-key handle করার নিরাপদ TS idiom।

27. কোথায় কাজে লাগে (real-world use)

• Stock price analysis: "প্রতিটা দিনের পর প্রথম যে দিন দাম বাড়ল" — financial dashboard আর trading signal-এ এই next-greater একদম সরাসরি লাগে।
• Temperature/sensor forecasting: "এর পরে প্রথম কবে value বাড়বে/কমবে" জাতীয় time-series প্রশ্ন monotonic stack-এ O(n)-তে মেটে।
• Compiler/parser: scope বা expression-এ "পরের বড় precedence operator" খোঁজা monotonic-stack চিন্তায় হয়।
• UI layout (skyline/spacing): histogram, skyline rendering-এ পরের উঁচু element কতদূর — এই pattern-এর ভিত্তি।
• Job scheduling: priority queue-তে "এই কাজের পর প্রথম উচ্চতর priority" খুঁজতে এই unresolved-stack ধারণা কাজে লাগে।

এক কথায়, "ডানদিকের প্রথম বড়/ছোট" জাতীয় যেকোনো relative-lookup-এ monotonic stack quadratic scan-কে linear-এ নামিয়ে আনে।

---

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