015 — Next Greater Element II

Source

• 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

1. Problem in simple words

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

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

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

6. Real-life analogy

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

7. Visual explanation

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

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]

8. Example input and output

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]

9. Brute force thinking

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

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 বন্ধ।

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]

15. Python solution

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 করে, নতুন কাউকে যোগ করে না।

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

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] লাগে।

21. Which basic problem this inherits from

ভিত্তি: Problem 9-এর monotonic stack (next greater), Problem 7-এর "most recent unfinished"। chapter-এর ../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।