NeetCode 150 in Hindi (Hinglish): Free SDE Prep

Hindi mein samjho (Hinglish)

Neeche is topic ka Hinglish explanation hai, wahi jo hamare course lesson mein audio narration ke saath chalta hai. Code English mein hai, samjhana Hindi mein.

Top K Frequent Elements

Top K Frequent Elements wo question hai jahan zyaadatar candidates heap solution pe ruk jaate hain aur better answer miss kar dete hain. Interviewer chahta hai ki tum teen approaches order mein walk karo: full sort, min-heap of size k, phir bucket sort. Bucket-sort wala answer strong-hire signal deta hai. Aaj hum teeno banayenge taaki tum interview mein right pick out loud justify kar sako.

Pattern pehchano. Jab bhi tumhe top k items chahiye kisi bounded integer score ke basis pe, frequency, length, digit count, us score se indexed bucket sort O of n deta hai. Trick yeh hai ki score ka tight upper bound hota hai. Length n ke array mein, koi bhi element n se zyaada baar nahi aa sakta, isliye n plus one buckets kaafi hain.

Ab unlock. Do ideas back to back. Pehla, min-heap of size k humein O of n log k deta hai by frequency map walk karte hue sirf top k counts rakhke. Lekin ek sharper insight hai: frequencies n se bounded integers hain. Hum har element ko uske frequency-indexed bucket mein daal sakte hain. Phir buckets ko high frequency se low tak walk karke k items collect karo. Na comparisons, na heap: pure O of n.

Python solution: Top K Frequent Elements

def top_k_frequent(nums, k):
    freq = {}
    for x in nums:
        freq[x] = freq.get(x, 0) + 1
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, count in freq.items():
        buckets[count].append(num)
    result = []
    for i in range(len(buckets) - 1, 0, -1):
        for num in buckets[i]:
            result.append(num)
            if len(result) == k:
                return result
    return result

Complexity: Sort by frequency: time O(n log n), space O(n); Min-heap of size k: time O(n log k), space O(k); Bucket sort by frequency (optimal): time O(n), space O(n).

Valid Parentheses

Welcome to Valid Parentheses. Duniya ka har parser, har compiler, har JSON validator usi idea pe bana hai jo tum aaj seekhne waale ho. Problem chhota dikhta hai, bas check karo brackets balanced hain, par yeh poori stack family ka gateway hai. Yeh saaf aa gaya toh Reverse Polish Notation, Min Stack, aur Daily Temperatures sab obvious lagne lagenge.

Pehle pattern pehchano. Jab bhi tum dekho nested structure jo opening ke reverse order mein band honi chahiye, brackets, HTML tags, function calls, undo history, yeh stack problem hai. Stacks last-in-first-out hote hain. Sabse recently jo open kiya, wahi next band hona chahiye. Bas yahi property bracket matching ke liye chahiye.

Asli unlock. Left se right walk karo. Har opener stack pe push kar do. Jab closer dikhe, uska sirf valid neighbour hai matching opener, aur wo bilkul stack ke top pe hona chahiye. Teen failure modes, sab O of one mein detect ho jaate hain. Empty stack pe pop. Top pe mismatch. Aur finally string khatam hone pe leftover openers. Warna valid hai.

Python solution: Valid Parentheses

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for i, ch in enumerate(s):
        if ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)
    return not stack

Complexity: Brute force (repeated string replace): time O(n²), space O(n); Stack + map (single pass): time O(n), space O(n).

Min Stack

Min Stack ek design problem hai jo data structure question ke roop mein chhupi hui hai. Interviewer dekhna chahta hai kya tum ek primitive structure, stack, le ke uss pe ek nayi operation bolt kar sakte ho original ke constant-time guarantees tode bina. Yeh skill, data structure ko precomputed state ke saath augment karna, har jagah aata hai databases se le ke operating systems tak.

Pattern recognition. Jab bhi problem maange ek O of one query ek aisi structure pe jo naturally support nahi karti, jawab almost always yahi hai ki query result ko structure ke saath maintain karo jaise woh change hota hai. Push aur pop already har state change ko touch karte hain, toh tum apni bookkeeping unke andar piggyback kar dete ho. Iss pattern ka naam hai, augmented data structure, aur Min Stack iska sabse saaf example hai.

Unlock simple hai. Ek doosra stack maintain karo jo running minimum track kare. Jab bhi tum naya value push karte ho jo current min se chhota ya equal hai, usse min stack pe bhi push karo. Jab tum aisa value pop karte ho jo current min ke equal hai, min stack bhi pop karo. Min stack ka top hamesha main stack mein jo bhi hai uska minimum hota hai. Constant time har jagah.

Python solution: Min Stack

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self):
        val = self.stack.pop()
        if val == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min_stack[-1]

Complexity: Brute force (single stack, scan on getMin): time push/pop/top: O(1), getMin: O(n), space O(n); Parallel min stack (≤ trigger): time all four: O(1), space O(n) worst, O(1) best for min stack; Pair storage: single stack of (val, min): time all four: O(1), space 2·O(n): always.