Clinic #07 - Valid Parentheses

Pattern: Stack (LIFO - “sabse haal ki cheez”) · LC 20

Ye board ek hi sawaal dikhata hai: jab brackets ek doosre ke andar nested hon, abhi is pal sabse haal mein kaunsa khula bracket apne jode (partner) ka intezaar kar raha hai. Push/pop andar se kaise kaam karte hain, wo Foundations #06 - Stacks & Queues (Hinglish) aur Linked Lists, Stacks & Queues (English) mein hai; yahan sirf ye ek problem.

Before you start. Bas itna pata hona chahiye ki push kisi cheez ko dher ke upar rakh deta hai aur pop sabse upar wali cheez ko wapas utha leta hai - Foundations #06 - Stacks & Queues ne ye dono operations andar se dikha diye the. Yahan sirf itna dekhna hai ki yehi do operations, aur kuch nahi, is interview problem ko solve kar dete hain.

The idea in 30 seconds

Compiler ko nested brackets match karne ke liye ye pata hona chahiye ki abhi sabse haal mein kaunsa khula bracket zinda hai - Dijkstra ne 1961 mein isi ke liye ek dher (stack) use kiya.
Stack ka niyam LIFO hai: jo sabse aakhri mein andar gaya, wahi sabse pehle bahar aata hai - jaise canteen ki thaliyon ka dher.
Push khula bracket ko dher pe rakhta hai; pop band bracket aane par sabse upar wali cheez utha ke check karta hai.
Sirf ginna kaafi nahi - "([)]" mein ginti net zero hai par order galat, kyunki ginti “sabse haal mein kaunsa khula hai” yaad nahi rakhti.
String valid tabhi hai jab har band bracket sahi partner se match kare aur ant mein stack khaali bache - koi khula na bacha ho.
Interview mein yehi ek line kaafi hai: “mujhe sabse haal ka khula bracket chahiye” bolte hi stack turant nikal aata hai.

Read the story · Skip to the numbers