001 — Valid Parentheses¶

Source¶

Original source: Classic stack exercise
Platform: LeetCode — https://leetcode.com/problems/valid-parentheses/
Topic: stack
Difficulty: Easy
Pattern: matching / nesting (stack)
Basic idea inherited from: raw push/pop discipline — খোলা bracket push করো, বন্ধ bracket এলে top-এর সাথে match করাও

1. Problem in simple words¶

তোমাকে একটা string দেওয়া আছে, যাতে শুধু (, ), [, ], {, } — এই ছয় রকম bracket থাকে। বলতে হবে string-টা ঠিকভাবে nested কিনা।

ঠিকভাবে nested মানে তিনটা শর্ত একসাথে মানতে হবে:

প্রতিটা খোলা bracket-এর একটা সঠিক ধরনের বন্ধ bracket আছে।
প্রতিটা বন্ধ bracket সঠিক order-এ বন্ধ হচ্ছে — সবচেয়ে পরে খোলা bracket-টা সবার আগে বন্ধ হবে।
শেষে কোনো খোলা bracket অমীমাংসিত থেকে যায় না।

valid   : ()    ()[]{}    {[]}    ([{}])
invalid : (]    ([)]      (       ]

2. Which basic idea does this inherit from?¶

এটা stack-এর সবচেয়ে raw রূপ — push আর pop-এর discipline, কোনো twist ছাড়াই। তুমি যেই মুহূর্তে বুঝবে "সবচেয়ে recently খোলা জিনিসটাই সবার আগে বন্ধ হতে হবে", তখনই LIFO (Last In, First Out) structure-টা নিজে থেকে চোখে পড়বে। chapter-এর ../concept.md-এ যে "থালার স্তূপ" analogy আছে, এটা ঠিক সেটারই সরাসরি প্রয়োগ।

3. What is the hidden math or logic?¶

লুকানো logic একটা invariant: যেকোনো মুহূর্তে stack-টা ধরে রাখে "যে bracket গুলো খোলা হয়েছে কিন্তু এখনো বন্ধ হয়নি", সবচেয়ে নতুনটা উপরে।

এই invariant ধরলে correctness তিনটা failure mode-এ ভাগ হয়ে যায়:

বন্ধ bracket এল কিন্তু stack খালি — কিছু খোলাই হয়নি যা বন্ধ করব (underflow)।
বন্ধ bracket এল কিন্তু top-এর খোলা bracket-টা ভুল ধরনের (mismatch)।
পুরো string শেষ কিন্তু stack-এ এখনো খোলা bracket পড়ে আছে (leftover)।

এই তিনটার একটাও ঘটলে string invalid; নাহলে valid।

4. Which data structure is needed?¶

একটা stack (Python-এ একটা সাধারণ list)। সাথে একটা ছোট hash map যা প্রতিটা বন্ধ bracket-কে তার সঠিক খোলা সঙ্গীর সাথে map করে — যাতে match করা O(1)-তে হয়।

5. Why this data structure fits¶

nesting মানেই "সবচেয়ে recent খোলাটা আগে বন্ধ হয়" — আর এটাই হুবহু LIFO। stack-এর append (push) আর pop দুটোই O(1)। বন্ধ bracket এলে আমাদের শুধু সবচেয়ে recent খোলাটা দেখতে হয়, যেটা ঠিক stack-এর top। array-তে মাঝখানে খুঁজতে গেলে O(n) লাগত; stack ঠিক যে প্রান্তটা দরকার সেটাই সস্তা রাখে।

6. Real-life analogy¶

একটা ম্যাট্রিওশকা (Russian nesting doll) ভাবো। তুমি বাইরের পুতুল খুলে ভেতরে আরেকটা পাও, সেটা খুলে আবার আরেকটা — খুলতে খুলতে ভেতরে যাও। বন্ধ করার সময় উল্টো: সবচেয়ে ভেতরের, মানে সবচেয়ে শেষে খোলা পুতুলটা আগে বন্ধ করতে হয়। মাঝখানেরটা আগে বন্ধ করতে চাইলে হবে না — ভেতরেরটা তখনো খোলা। bracket-ও ঠিক তাই।

7. Visual explanation¶

([{}]) valid কিনা দেখি, stack বদলাতে দেখি:

char   action                       stack (top ডানে)
'('    open  -> push                [ (
'['    open  -> push                [ (, [
'{'    open  -> push                [ (, [, {
'}'    close -> top '{' মেলে -> pop [ (, [
']'    close -> top '[' মেলে -> pop [ (
')'    close -> top '(' মেলে -> pop [
end    stack খালি -> VALID

এবার ([)] — interleave করে, nest করে না:

'('    push                         [ (
'['    push                         [ (, [
')'    close -> top '[', দরকার '(' -> MISMATCH -> invalid

8. Example input and output¶

Input : "()"        -> Output: True
Input : "()[]{}"    -> Output: True
Input : "(]"        -> Output: False   (ভুল partner)
Input : "([)]"      -> Output: False   (interleave, nest না)

Edge case 1 (খালি string): Input: ""   -> Output: True   (কিছু ভাঙার নেই)
Edge case 2 (শুধু খোলা)   : Input: "("  -> Output: False  (leftover)
Edge case 3 (শুধু বন্ধ)   : Input: "]"  -> Output: False  (underflow)

9. Brute force thinking¶

প্রথম সরল চিন্তা: বারবার string scan করে পাশাপাশি থাকা মিলে-যাওয়া জোড়া ((), [], {}) মুছে ফেলি, যতক্ষণ আর কিছু মোছা না যায়।

"([)]" -> কোনো পাশাপাশি জোড়া নেই -> থামো -> string খালি না -> invalid
"(())" -> ভেতরের "()" মোছো -> "()" -> মোছো -> "" -> valid

10. Why brute force is slow¶

প্রতিবার একটা জোড়া মুছলে string-টা নতুন করে বানাতে আর আবার scan করতে হয়। সবচেয়ে খারাপ ক্ষেত্রে (যেমন ((((...))))) এটা O(n) বার scan, প্রতিবার O(n) কাজ → O(n^2)। string বারবার নতুন করে গড়াটাও অপচয়। আমরা চাই একবার scan-এ, O(n)-তে কাজ শেষ করতে।

11. Key observation¶

মূল observation: একটা বন্ধ bracket-কে শুধু সবচেয়ে recently খোলা bracket-এর সাথেই মেলাতে হয় — তার আগের কোনো খোলা bracket-এর কথা ভাবার দরকারই নেই। "সবচেয়ে recent খোলা"-টা ঠিক stack-এর top। তাই string একবার বাঁ থেকে ডানে হাঁটলেই হয়।

12. Optimized intuition¶

string-এ একবার হাঁটো। খোলা bracket পেলে stack-এ push করো। বন্ধ bracket পেলে stack-এর top দেখো: যদি top ওই বন্ধ bracket-এর সঠিক partner হয়, pop করো (এই জোড়াটা মিটে গেল); নাহলে (অথবা stack খালি থাকলে) সাথে সাথে invalid। শেষে stack খালি হলে valid, নাহলে leftover খোলা bracket আছে — invalid।

13. Thinking tweak¶

মোচড়: "পুরো string-টা মিলিয়ে দেখব" ভাবার বদলে ভাবো "প্রতি মুহূর্তে আমি কীসের ভেতরে আছি?" — stack-টাই তার exact উত্তর, innermost context উপরে। এই দৃষ্টিভঙ্গিতে nested-matching problem হঠাৎ trivial হয়ে যায়।

14. Step-by-step dry run¶

Input "{[]}":

শুরু: stack = []
{ — খোলা, push → stack = ['{']
[ — খোলা, push → stack = ['{', '[']
] — বন্ধ, top [ দরকার [ ✓ pop → stack = ['{']
} — বন্ধ, top { দরকার { ✓ pop → stack = []
string শেষ, stack খালি → return True

15. Python solution¶

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}   # বন্ধ -> তার সঠিক খোলা
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)                 # খোলা bracket জমাও
        elif not stack or stack.pop() != pairs[ch]:
            return False                      # underflow বা ভুল partner
    return not stack                          # leftover থাকলে False

# ---- tests ----
assert is_valid("()") is True
assert is_valid("()[]{}") is True
assert is_valid("{[]}") is True
assert is_valid("([{}])") is True
assert is_valid("(]") is False          # ভুল partner
assert is_valid("([)]") is False        # interleave
assert is_valid("") is True             # খালি string
assert is_valid("(") is False           # leftover খোলা
assert is_valid("]") is False           # underflow
print("সব test pass!")

16. Line-by-line code explanation¶

pairs = {...} — প্রতিটা বন্ধ bracket-কে তার সঠিক খোলা সঙ্গীর সাথে map; O(1) lookup-এর জন্য।
stack = [] — খোলা-কিন্তু-অমীমাংসিত bracket গুলো এখানে জমবে।
if ch in '([{': — খোলা bracket হলে append করে stack-এ তুলে রাখো।
elif not stack or stack.pop() != pairs[ch]: — বন্ধ bracket-এর ক্ষেত্রে: stack খালি হলে (underflow) বা pop করা top ভুল partner হলে — False। (not stack আগে check হয় বলে খালি stack-এ pop হয় না।)
return not stack — পুরো string ঠিক থাকলেও যদি stack-এ leftover খোলা থাকে, False; খালি হলে True।

17. Output walkthrough¶

is_valid("{[]}") → section 14-এর dry run মতো stack শেষে খালি → True। is_valid("([)]") → ) আসার সময় top থাকে [, partner দরকার (, mismatch → False। সব assert pass করে শেষে print: সব test pass!।

18. Time complexity¶

O(n) — প্রতিটা character ঠিক একবার দেখা হয়, প্রতিটা push/pop O(1)।

19. Space complexity¶

O(n) — সবচেয়ে খারাপ ক্ষেত্রে (সব খোলা bracket, যেমন "(((((") stack-এ n-টা element জমতে পারে।

20. Common mistakes¶

বন্ধ bracket-এ stack খালি কিনা check না করে সরাসরি pop করা — খালি stack-এ pop করলে error।
শেষে stack খালি কিনা check না করা — তখন "(((" ভুল করে valid দেখাবে।
শুধু গোনা ("খোলা সংখ্যা == বন্ধ সংখ্যা") দিয়ে decide করা — তাতে ([)]-কে ভুল করে valid বলবে; order আর type দুটোই matter করে।

21. Which basic problem this inherits from¶

ভিত্তি: stack-এর raw push/pop discipline। chapter-এর ../concept.md-এর Snippet 3 (আট লাইনে bracket matching) আর ../patterns.md-এর Pattern 1 (Matching / Nesting / Undo) এখানে সরাসরি কাজে লাগছে।

22. Similar harder problems¶

Decode String (nested encoding) — https://leetcode.com/problems/decode-string/ (এই tracker-এর #10)
Longest Valid Parentheses — https://leetcode.com/problems/longest-valid-parentheses/
Basic Calculator (parentheses সহ expression) — https://leetcode.com/problems/basic-calculator/ (#22)

23. Pattern learned¶

Matching with a stack: খোলা context push করো, closing event এলে top-এর সাথে মিলিয়ে pop করো — "valid / nested / balanced" দেখলেই এই pattern মনে করবে।

24. Final summary¶

ভবিষ্যতের আমাকে: "matching = সবচেয়ে recent খোলাটার সাথে মেলাও, তাই stack।" তিনটা failure mode মাথায় রাখবে — underflow, mismatch, leftover। "valid / balanced / nested" শব্দ দেখলেই stack-এর কথা ভাববে।

25. JavaScript solution (with test cases)¶

array-কে stack হিসেবে; closing bracket এলে top-এর সাথে match।

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// is the bracket string properly nested? (stack)
function isValid(s) {
  const pairs = { ")": "(", "]": "[", "}": "{" };   // বন্ধ -> তার সঠিক খোলা
  const stack = [];
  for (const ch of s) {
    if (ch === "(" || ch === "[" || ch === "{") {
      stack.push(ch);                                // খোলা bracket জমাও
    } else if (stack.length === 0 || stack.pop() !== pairs[ch]) {
      return false;                                  // underflow বা ভুল partner
    }
  }
  return stack.length === 0;                          // leftover থাকলে false
}
// ---- test cases (example + edge) ----
assert(isValid("()") === true, "simple");
assert(isValid("()[]{}") === true, "all-types");
assert(isValid("{[]}") === true, "nested");
assert(isValid("([{}])") === true, "deep");
assert(isValid("(]") === false, "wrong-partner");
assert(isValid("([)]") === false, "interleave");
assert(isValid("") === true, "empty");                           // edge
assert(isValid("(") === false, "leftover");                      // edge
assert(isValid("]") === false, "underflow");                     // edge
console.log("সব JS test pass!");

JS টীকা: plain array-ই stack — push/pop দুটোই O(1)। stack.length === 0 আগে check করো (short-circuit ||), নইলে খালি stack-এ pop() undefined দিয়ে ভুল match হতে পারত। শেষে stack.length === 0 না দেখলে "(((" ভুল করে valid দেখাবে।

26. TypeScript solution (with test cases)¶

function isValid(s: string): boolean {
  const pairs: Record<string, string> = { ")": "(", "]": "[", "}": "{" };
  const stack: string[] = [];
  for (const ch of s) {
    if (ch === "(" || ch === "[" || ch === "{") {
      stack.push(ch);
    } else if (stack.length === 0 || stack.pop() !== pairs[ch]) {
      return false;
    }
  }
  return stack.length === 0;
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(isValid("([{}])"), true, "deep");
expect(isValid("([)]"), false, "interleave");
expect(isValid(""), true, "empty");
expect(isValid("("), false, "leftover");
console.log("সব TS test pass!");

TS টীকা: pairs কে Record<string, string> declare করায় lookup নিরাপদ; stack: string[] বলে শুধু bracket character ঢোকে আর return boolean বলে তিন failure mode-এর বাইরে কিছু ফেরত দেওয়া যায় না।

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

Compiler/parser: কোড বা expression-এ bracket/scope সঠিকভাবে balanced কিনা যাচাই।
Editor tooling: IDE-তে bracket matching, auto-close, syntax error highlight।
Markup/JSON/XML validation: নেস্টেড tag বা brace সঠিক order-এ বন্ধ হচ্ছে কিনা।
Math expression eval: parenthesis balance check করে তারপর evaluate।
Template engines: {{ }} জাতীয় delimiter সঠিকভাবে nested কিনা যাচাই।
Undo/redo & call stack: সবচেয়ে recent action আগে বাতিল — একই LIFO discipline।

মূল pattern: খোলা context push, closing event এলে top-এর সাথে মিলিয়ে pop — "valid / balanced / nested" দেখলেই stack।

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