Medium Level LeetCode Problems मीडियम लेवल लीटकोड प्रॉब्लम्स

Medium DSA problems focusing on Sliding Window and Two Pointers. स्लाइडिंग विंडो और टू पॉइंटर्स पर फोकस्ड मीडियम DSA प्रॉब्लम्स।

Minimum Window Substring (LC 76) – LeetCode मिनिमम विंडो सबस्ट्रिंग (LC 76) – लीटकोड

Problem: Given two strings s and t, return the minimum window in s which contains all characters in t. If no such window exists, return "". समस्या: दिए गए दो स्ट्रिंग्स s और t में, s में t के सभी कैरेक्टर्स को कंटेन करने वाली मिनिमम विंडो रिटर्न करें। अगर कोई विंडो नहीं, तो "" रिटर्न।

Pattern Tags पैटर्न टैग्स

  • Primary: Sliding Window, Hash Map
  • Secondary: Two-Pointer
  • Frequency: Very high in interviews (FAANG favorite string problem)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: Optimal O(n + m) time, O(m) space
  • Edge: t longer than s → return ""
  • Self: Example s = "ADOBECODEBANC", t = "ABC" → "BANC"

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Case sensitive? Multiplicity in t? n,m up to 10^4?" Quick heuristic: "Min covering substring? Hints variable window (expand until valid, shrink), freq match." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "केस सेंसिटिव? t में मल्टिप्लिसिटी? n,m 10^4?" क्विक ह्यूरिस्टिक: "मिन कवरिंग सबस्ट्रिंग? हिन्ट्स वेरिएबल विंडो (वैलिड तक एक्सपैंड, श्रिंक), फ्रिक मैच।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“minimum window substring” Smallest substring covering all chars Sliding window + frequency map Expand right, shrink left
“contains all characters” Exact frequency match? Char count tracking Maintain count of required vs formed
“return empty if not exist” Handle no solution gracefully Conditional return Track 'minLen' and indices

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Generate all substrings of s, check if each contains t using frequency maps. Time: O(n³) Space: O(m)
  • Alternative Sort not applicable here, only sliding window works well.
  • Optimal (Sliding Window + Hash Map) Two pointers L and R. Expand R to satisfy requirement, shrink L to minimize window. Track min substring.

Non-Optimized Solution (Brute Force) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (ब्रूट फोर्स)

Javascript 
// Brute Force: Generate all substrings and check frequency
function minWindowBrute(s, t) {
  let minLen = Infinity, ans = "";

  function contains(sub, t) {
    let map = {};
    for (let c of t) map[c] = (map[c] || 0) + 1;
    for (let c of sub) {
      if (map[c]) map[c]--;
    }
    return Object.values(map).every(v => v <= 0);
  }

  for (let i = 0; i < s.length; i++) {
    for (let j = i + 1; j <= s.length; j++) {
      let sub = s.slice(i, j);
      if (contains(sub, t) && sub.length < minLen) {
        ans = sub;
        minLen = sub.length;
      }
    }
  }
  return ans;
}
// Time: O(n³) - nested loops + O(n) check, Space: O(m)
Why This Solution? यह सॉल्यूशन क्यों?
  • Intuitive, brute force check all substrings.
  • Impractical for large strings (O(n³)).

Optimized Solution (Sliding Window + Hash Map) ऑप्टिमाइज्ड सॉल्यूशन (स्लाइडिंग विंडो + हैश मैप)

Javascript 
// Optimized (Sliding Window + Hash Map): Two pointers with frequency tracking
function minWindow(s, t) {
  if (t.length > s.length) return "";

  let freq = {};
  for (let c of t) freq[c] = (freq[c] || 0) + 1;

  let required = Object.keys(freq).length;
  let formed = 0, windowCounts = {};
  let L = 0, R = 0, minLen = Infinity, res = [-1, -1];

  while (R < s.length) {
    let c = s[R];
    windowCounts[c] = (windowCounts[c] || 0) + 1;

    if (freq[c] && windowCounts[c] === freq[c]) formed++;

    while (L <= R && formed === required) {
      if (R - L + 1 < minLen) {
        minLen = R - L + 1;
        res = [L, R];
      }

      let leftChar = s[L];
      windowCounts[leftChar]--;
      if (freq[leftChar] && windowCounts[leftChar] < freq[leftChar]) formed--;
      L++;
    }
    R++;
  }
  return res[0] === -1 ? "" : s.slice(res[0], res[1] + 1);
}
// Time: O(n + m) - single pass, Space: O(m) - maps
Why This Solution? यह सॉल्यूशन क्यों?
  • Efficient O(n + m).
  • Standard interview sliding window template.

Interview Framing इंटरव्यू फ्रेमिंग

“Naïvely, I could generate all substrings and check if they contain t, but that’s O(n³). The optimal way is to use a sliding window: maintain a frequency map of t, expand right until the window covers all required characters, then shrink left to minimize. This guarantees O(n) time. For example, with s = "ADOBECODEBANC", t = "ABC", the answer is "BANC".” “नाइवली, सबस्ट्रिंग्स जेनरेट और t कंटेन चेक, लेकिन O(n³)। ऑप्टिमल स्लाइडिंग विंडो: t का फ्रिक्वेंसी मैप, राइट एक्सपैंड तक कवर, लेफ्ट श्रिंक मिनिमाइज। O(n) गारंटी। उदाहरण s = "ADOBECODEBANC", t = "ABC" → "BANC"।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

“I’d first mention the brute force, then say we can optimize with sliding window. Use two pointers, expand R to include characters, track how many required chars are matched. Once all are matched, shrink from L to minimize window. This balance of expand/shrink gives linear time.” “पहले ब्रूट फोर्स मेंशन, फिर स्लाइडिंग विंडो ऑप्टिमाइज। टू पॉइंटर्स, R एक्सपैंड कैरेक्टर्स ऐड, रिक्वायर्ड मैच ट्रैक। ऑल मैच तो L से श्रिंक मिन विंडो। एक्सपैंड/श्रिंक बैलेंस लीनियर टाइम।”

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“For Minimum Window Substring, the naive approach is to test every substring and check if it contains all chars of t, which is O(n³). The optimal solution uses a variable sliding window with a frequency map of t. I expand the right pointer adding chars to the window until all required characters are covered, then shrink the left pointer to minimize the window while it remains valid. I keep track of the best [L,R] and return that substring (or "" if none). This runs in O(n + m) time using a small hashmap.” “मिनिमम विंडो सबस्ट्रिंग के लिए, नाइव सबस्ट्रिंग टेस्ट t के सभी chars, O(n³)। ऑप्टिमल वेरिएबल स्लाइडिंग विंडो t का फ्रिक्वेंसी मैप। राइट पॉइंटर एक्सपैंड विंडो ऐड chars तक कवर, लेफ्ट श्रिंक वैलिड रख मिनिमाइज। बेस्ट [L,R] ट्रैक रिटर्न सबस्ट्रिंग (नोने "" )। O(n + m) स्मॉल हैशमैप।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate problem & constraints (contiguous substring, multiplicity).
  • Mention brute force (all substrings) and its complexity.
  • Present optimal pattern: variable sliding window + frequency map.
  • State complexities: O(n + m) time, O(|charset|) space.
  • Give a quick dry-run example and note edge cases (t longer than s → return "").

Find All Anagrams in a String (LC 438) – LeetCode फाइंड ऑल एनाग्राम्स इन अ स्ट्रिंग (LC 438) – लीटकोड

Problem: Given two strings s and p, return all start indices of p’s anagrams in s. समस्या: दिए गए दो स्ट्रिंग्स s और p में, s में p के एनाग्राम्स के सभी स्टार्ट इंडेक्स रिटर्न करें।

Pattern Tags पैटर्न टैग्स

  • Primary: Sliding Window, Hash Map
  • Secondary: Frequency Counter
  • Frequency: Common variation of substring problems

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: Optimal O(n) time, O(26) space
  • Edge: Empty p, or s shorter than p → return []
  • Self: Example s = "cbaebabacd", p = "abc" → [0,6]

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Lowercase only? Duplicates in p? n up to 10^4?" Quick heuristic: "Anagrams in string? Hints fixed window size p.length, freq compare." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "लोअरकेस ओनली? p में डुप्स? n 10^4?" क्विक ह्यूरिस्टिक: "स्ट्रिंग में एनाग्राम्स? हिन्ट्स फिक्स्ड विंडो p.length, फ्रिक कंपेयर।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“find all anagrams” Same length substrings Fixed-size sliding window Compare counts with target counts
“return start indices” Not substring, but indices needed Track window start Collect results when match achieved
“string p, string s” Length comparison Char frequency map O(1) compare using counts

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Generate every substring of length p.length, sort both, compare. Time: O(n·m log m) Space: O(m)
  • Alternative Sort-based approach (slower, O(n·m log m)).
  • Optimal (Fixed-size Sliding Window) Maintain freq counts for window of size p.length. Move window forward, update counts, check if matches.

Non-Optimized Solution (Sorting) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (सॉर्टिंग)

Javascript 
// Non-Optimized (Sorting): Sort each substring and compare
function findAnagramsBrute(s, p) {
  const res = [];
  const sortedP = p.split('').sort().join('');
  for (let i = 0; i <= s.length - p.length; i++) {
    const sub = s.slice(i, i + p.length).split('').sort().join('');
    if (sub === sortedP) res.push(i);
  }
  return res;
}
// Time: O(n·m log m) - sort each window, Space: O(m)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple, intuitive.
  • Sorting overhead → inefficient for large strings.

Optimized Solution (Sliding Window + Frequency Map) ऑप्टिमाइज्ड सॉल्यूशन (स्लाइडिंग विंडो + फ्रिक्वेंसी मैप)

Javascript 
// Optimized (Fixed-size Sliding Window + Frequency): Incremental counts
function findAnagrams(s, p) {
  const res = [];
  if (p.length > s.length) return res;

  let pCount = Array(26).fill(0);
  let sCount = Array(26).fill(0);

  for (let c of p) pCount[c.charCodeAt(0) - 97]++;

  for (let i = 0; i < s.length; i++) {
    sCount[s.charCodeAt(i) - 97]++;
    if (i >= p.length) {
      sCount[s.charCodeAt(i - p.length) - 97]--;
    }
    if (pCount.toString() === sCount.toString()) {
      res.push(i - p.length + 1);
    }
  }
  return res;
}
// Time: O(n) - single pass, Space: O(26) - fixed arrays
Why This Solution? यह सॉल्यूशन क्यों?
  • O(n) runtime.
  • Works with fixed alphabet efficiently.

Interview Framing इंटरव्यू फ्रेमिंग

“Brute force would check all substrings of length p and sort, but that’s O(n·m log m). Instead, I use a fixed-size sliding window of length p.length. I maintain counts of chars in the window, and compare with counts from p. Every time they match, I record the start index.” “ब्रूट f all substrings of length p and sort, but that’s O(n·m log m). Instead, I use a fixed-size sliding window of length p.length. I maintain counts of chars in the window, and compare with counts from p. Every time they match, I record the start index.”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

“I’d describe sorting-based brute force, then optimize with sliding window. For each char added on the right, update counts; if window too long, remove from left. Compare with target counts in O(1). This makes it linear.” “I’d describe sorting-based brute force, then optimize with sliding window. For each char added on the right, update counts; if window too long, remove from left. Compare with target counts in O(1). This makes it linear.”

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“For Find All Anagrams, brute force sorts or counts every substring of length p and compares to p, which is O(n·m log m). The optimal method uses a fixed-size sliding window of length p.length with frequency arrays for p and the current window. Slide the window, update counts incrementally, and whenever the counts match record the start index. This yields O(n) time and O(alphabet) space — very efficient for lowercase alphabets.” “For Find All Anagrams, brute force sorts or counts every substring of length p and compares to p, which is O(n·m log m). The optimal method uses a fixed-size sliding window of length p.length with frequency arrays for p and the current window. Slide the window, update counts incrementally, and whenever the counts match record the start index. This yields O(n) time and O(alphabet) space — very efficient for lowercase alphabets.”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate problem and confirm alphabet/case constraints.
  • Outline brute force (sort/compare each substring).
  • Describe optimal: fixed-size sliding window + incremental freq updates.
  • Complexity: O(n) time, O(k) space (k = alphabet).
  • Show small example and mention early exit if p longer than s.

Minimum Size Subarray Sum (LC 209) – LeetCode मिनिमम साइज सबअरे सम (LC 209) – लीटकोड

Problem: Given an array of positive integers nums and an integer target, return the minimal length of a subarray with sum ≥ target. If none exists, return 0. समस्या: दिए गए पॉजिटिव इंटीजर ऐरे nums और टारगेट में, सम ≥ टारगेट वाली मिनिमल लेंथ सबअरे रिटर्न करें। नोने एग्जिस्ट तो 0।

Pattern Tags पैटर्न टैग्स

  • Primary: Sliding Window, Two Pointers
  • Secondary: Prefix Sum (binary search variant)
  • Frequency: Classic medium (popular for array interviews)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: Optimal O(n), alternative O(n log n) via prefix sums
  • Edge: No subarray satisfies → return 0
  • Self: Example target=7, nums=[2,3,1,2,4,3] → output 2 (subarray [4,3])

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "All positive? target range? n up to 10^5?" Quick heuristic: "Min length subarray sum >= target? Hints sliding window for positives." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "ऑल पॉजिटिव? टारगेट रेंज? n 10^5?" क्विक ह्यूरिस्टिक: ">= टारगेट सम मिन लेंथ सबअरे? हिन्ट्स पॉजिटिव्स के लिए स्लाइडिंग विंडो।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“minimum length subarray” Shrinking window, smallest size Sliding window two-pointer Expand until sum ≥ target, then shrink
“sum ≥ target” Positive numbers only Prefix sum possible Shrink greedily since all nums > 0
“return 0 if none exists” Handle failure case Condition check Return 0 when no valid window

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Try all subarrays, compute sums. Time: O(n²) Space: O(1)
  • Alternative Prefix sums + binary search: compute prefix array, for each index binary search target sum. O(n log n).
  • Optimal (Sliding Window Two-pointer) Expand right until sum ≥ target, then shrink left to minimize length.

Non-Optimized Solution (Brute Force) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (ब्रूट फोर्स)

Javascript 
// Non-Optimized (Brute Force): Nested loops for subarrays
function minSubArrayLenBrute(target, nums) {
  let n = nums.length;
  let minLen = Infinity;
  for (let i = 0; i < n; i++) {
    let sum = 0;
    for (let j = i; j < n; j++) {
      sum += nums[j];
      if (sum >= target) {
        minLen = Math.min(minLen, j - i + 1);
        break;
      }
    }
  }
  return minLen === Infinity ? 0 : minLen;
}
// Time: O(n²) - nested, Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • Straightforward, but O(n²).

Optimized Solution (Sliding Window) ऑप्टिमाइज्ड सॉल्यूशन (स्लाइडिंग विंडो)

Javascript 
// Optimized (Sliding Window): Expand/shrink for positives
function minSubArrayLen(target, nums) {
  let L = 0, sum = 0, minLen = Infinity;
  for (let R = 0; R < nums.length; R++) {
    sum += nums[R];
    while (sum >= target) {
      minLen = Math.min(minLen, R - L + 1);
      sum -= nums[L];
      L++;
    }
  }
  return minLen === Infinity ? 0 : minLen;
}
// Time: O(n) - single pass, Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • O(n) runtime, minimal space.
  • Works because all nums > 0.

Interview Framing इंटरव्यू फ्रेमिंग

“Naïvely, I’d check all subarrays, O(n²). But since all numbers are positive, we can use a sliding window. Expand right until sum ≥ target, then shrink left while maintaining condition. This guarantees minimal length in linear time.” “नाइवली, सबअरे चेक O(n²)। लेकिन पॉजिटिव नंबर्स, स्लाइडिंग विंडो। राइट एक्सपैंड sum ≥ target, लेफ्ट श्रिंक कंडीशन। लीनियर मिनिमल लेंथ।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

“I’d highlight brute force first, then prefix sum + binary search, then the optimal sliding window. I’d stress why sliding works: since nums are positive, shrinking window always reduces sum, so correctness holds.” “ब्रूट हाइलाइट, फिर प्रिफिक्स + बाइनरी, फिर ऑप्टिमल स्लाइडिंग। क्यों वर्क्स: पॉजिटिव nums, श्रिंक सम रिड्यूस, करेक्ट।”

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“For Minimum Size Subarray Sum, naive double loops check every subarray sum in O(n²). Because numbers are non-negative, we can use a two-pointer sliding window: expand the right pointer adding numbers until sum ≥ target, then shrink left to try to minimize the window, updating minimum length as we go. That gives O(n) time and O(1) space. If negatives were allowed I’d mention prefix sums + binary search as an alternate O(n log n) approach.” “मिन साइज सबअरे सम, नाइव डबल लूप्स O(n²)। नॉन-नेगेटिव, टू-पॉइंटर स्लाइडिंग: राइट एक्सपैंड sum ≥ target, लेफ्ट श्रिंक मिनिमाइज, अपडेट लेंथ। O(n) O(1)। नेगेटिव्स तो प्रिफिक्स + बाइनरी O(n log n)।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate the problem and confirm positivity of numbers.
  • Mention brute force O(n²).
  • Describe sliding-window expand/shrink logic.
  • Complexity: O(n) time, O(1) space.
  • Example + edge case (no valid window → return 0).

Permutation in String (LC 567) – LeetCode परमुटेशन इन स्ट्रिंग (LC 567) – लीटकोड

Problem: Given two strings s1 and s2, return true if s2 contains a permutation of s1 as a substring. In other words, return true if some substring of s2 is an anagram of s1. समस्या: दिए गए दो स्ट्रिंग्स s1 और s2 में, अगर s2 में s1 का परमुटेशन सबस्ट्रिंग है तो true रिटर्न। यानी s2 का कोई सबस्ट्रिंग s1 का एनाग्राम हो।

Pattern Tags पैटर्न टैग्स

  • Primary: Sliding Window (fixed-size)
  • Secondary: Frequency Map / Counting
  • Frequency: Medium (common substring / anagram variant)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: Optimal O(n) time, O(k) space where k = alphabet size (or O(26) for lowercase letters).
  • Edge: s1.length > s2.length → return false. Empty s1 → define behavior (often true). Case sensitivity matters.
  • Self: s1 = "ab", s2 = "eidbaooo" → true (substring "ba" at index 3).

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Lowercase? Duplicates? n up to 5*10^4?" Quick heuristic: "Permutation substring? Fixed window len(s1), freq match." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "लोअरकेस? डुप्स? n 5*10^4?" क्विक ह्यूरिस्टिक: "परमुटेशन सबस्ट्रिंग? फिक्स्ड विंडो len(s1), फ्रिक मैच।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“contains a permutation” Fixed-size substring (size = s1.length) Fixed-size sliding window Slide window of length m and compare counts
“some substring is an anagram” Order doesn't matter, only frequency Frequency counter / match count Use counts or difference array for O(1) compare
“return true/false” Early exit possible when match found Stop when match achieved Don't need all indices, boolean result ok

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force For each index i in s2 with length m = s1.length, check substring s2[i..i+m-1] by sorting or counting and compare to s1. Time: O(n * m log m) if sorting each substring, or O(n * m) with counting. Space: O(m)
  • Alternative Sort s1, and check each substring of s2 of same length by sorting and comparing (slower). Or use rolling hash (less common for interviews).
  • Optimal (Fixed-size Sliding Window + Frequency counts) Maintain frequency arrays (or maps) for s1 and current window in s2. Slide the window, update counts incrementally, and check equality with O(1) comparison (for array of fixed size) or maintain a matches counter.

Non-Optimized Solution (Brute Force — counting per window) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (ब्रूट फोर्स — काउंटिंग पर विंडो)

Javascript 
// Non-Optimized (Brute Force — counting per window): O(n*m)
function checkInclusionBrute(s1, s2) {
  const m = s1.length, n = s2.length;
  if (m > n) return false;

  function counts(str) {
    const cnt = {};
    for (let c of str) cnt[c] = (cnt[c] || 0) + 1;
    return cnt;
  }

  const target = counts(s1);
  for (let i = 0; i <= n - m; i++) {
    const sub = s2.slice(i, i + m);
    const subCnt = counts(sub);
    let equal = true;
    if (Object.keys(subCnt).length !== Object.keys(target).length) equal = false;
    for (let k in target) {
      if (subCnt[k] !== target[k]) { equal = false; break; }
    }
    if (equal) return true;
  }
  return false;
}
// Time: O(n * m) - count each window, Space: O(m)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple and correct; too slow for large strings.

Optimized Solution (Sliding Window with Fixed-size counts) ऑप्टिमाइज्ड सॉल्यूशन (स्लाइडिंग विंडो विद फिक्स्ड-साइज काउंट्स)

Javascript 
// Optimized (Sliding Window with Fixed-size counts): O(n)
function checkInclusion(s1, s2) {
  const m = s1.length, n = s2.length;
  if (m > n) return false;

  const aCode = 'a'.charCodeAt(0);
  const s1Count = new Array(26).fill(0);
  const s2Count = new Array(26).fill(0);

  for (let i = 0; i < m; i++) {
    s1Count[s1.charCodeAt(i) - aCode]++;
    s2Count[s2.charCodeAt(i) - aCode]++;
  }

  function arraysEqual(a, b) {
    for (let i = 0; i < 26; i++) if (a[i] !== b[i]) return false;
    return true;
  }

  if (arraysEqual(s1Count, s2Count)) return true;

  for (let i = m; i < n; i++) {
    s2Count[s2.charCodeAt(i) - aCode]++;                // add new char
    s2Count[s2.charCodeAt(i - m) - aCode]--;            // remove old char
    if (arraysEqual(s1Count, s2Count)) return true;
  }
  return false;
}
// Time: O(n) - single pass, Space: O(26) - fixed arrays
Why This Solution? यह सॉल्यूशन क्यों?
  • Linear time, fixed-space for lowercase.
  • Efficient incremental updates avoid recomputing counts.

Interview Framing इंटरव्यू फ्रेमिंग

“Brute force checks every substring of size s1.length. The optimal approach keeps a window of length m and updates counts as we slide. Compare arrays in O(26) per step or maintain a match count for O(1) equality checks.” “ब्रूट चेक्स एवरी सबस्ट्रिंग s1.length। ऑप्टिमल विंडो m रख अपडेट काउंट्स स्लाइड। O(26) कंपेयर पर स्टेप या मैच काउंट O(1)।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Clarify constraints: alphabet size, case-sensitivity. Brute: check all substrings and compare counts — O(n·m). Optimized: build count arrays for s1 and the first window in s2. Slide window one char at a time: add new char, remove old char, compare counts. If we must avoid the O(26) compare each move, mention we can maintain a matches integer that increments/decrements when a char count becomes equal/unequal. State complexities and edge cases, and give a short dry-run example (s1="ab", s2="eidbaooo"). Clarify constraints: alphabet size, case-sensitivity. Brute: check all substrings and compare counts — O(n·m). Optimized: build count arrays for s1 and the first window in s2. Slide window one char at a time: add new char, remove old char, compare counts. If we must avoid the O(26) compare each move, mention we can maintain a matches integer that increments/decrements when a char count becomes equal/unequal. State complexities and edge cases, and give a short dry-run example (s1="ab", s2="eidbaooo").

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“For Permutation in String, brute force checks every length-m substring of s2 against s1 in O(n·m). The efficient approach keeps a fixed window of size s1.length with frequency counts of s1 and the window in s2. Slide the window, updating counts incrementally; if counts match at any time return true. This runs in O(n) time and O(k) space (k = alphabet). If alphabet is large mention using a map instead of fixed arrays.” “For Permutation in String, brute force checks every length-m substring of s2 against s1 in O(n·m). The efficient approach keeps a fixed window of size s1.length with frequency counts of s1 and the window in s2. Slide the window, updating counts incrementally; if counts match at any time return true. This runs in O(n) time and O(k) space (k = alphabet). If alphabet is large mention using a map instead of fixed arrays.”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Clarify window size equals s1.length and alphabet constraints.
  • State brute approach (check every window).
  • Present fixed-window counts method and incremental updates.
  • Complexity: O(n) time, O(k) space.
  • Give an example and mention the matches optimization for O(1) equality checks.

Sliding Window Maximum (LC 239) – LeetCode स्लाइडिंग विंडो मैक्सिमम (LC 239) – लीटकोड

Problem: Given an integer array nums and a sliding window size k, return an array of the maximum value in each sliding window. समस्या: दिए गए इंटीजर ऐरे nums और स्लाइडिंग विंडो साइज k में, हर स्लाइडिंग विंडो का मैक्सिमम वैल्यू ऐरे रिटर्न करें।

Pattern Tags पैटर्न टैग्स

  • Primary: Sliding Window, Monotonic Deque
  • Secondary: Deque / Index tracking
  • Frequency: Medium-high (classic window aggregate problem)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: Optimal O(n) time, O(k) space.
  • Edge: k = 1 (result = array), k = n (single max), duplicates present.
  • Self: nums = [1,3,-1,-3,5,3,6,7], k = 3 → [3,3,5,5,6,7].

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "k from 1 to n? Duplicates? n up to 10^5?" Quick heuristic: "Max in each fixed window? Hints monotonic deque for O(n)." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "k 1 to n? डुप्स? n 10^5?" क्विक ह्यूरिस्टिक: "फिक्स्ड विंडो में मैक्स? हिन्ट्स मोनोटोनिक डीक्यू O(n)।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“max for each sliding window” Fixed window size, need efficient agg Monotonic deque (indices) Keep candidates in decreasing order; front = max
“window size k” Need all windows or early exit? O(n) deque approach Ensure outdated indices are removed
“return array” Collect max at each step Deque holding indices Use indices to check window bounds

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force For each window compute max by scanning k elements. Time: O(n·k) Space: O(1)
  • Alternative Segment tree or heap per window (heap needs lazy removals) — higher overhead.
  • Optimal (Monotonic Deque) Maintain deque of indices whose corresponding values are in decreasing order. Front is max. Pop back smaller values when adding new index; pop front if out of window.

Non-Optimized Solution (Brute Force) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (ब्रूट फोर्स)

Javascript 
// Non-Optimized (Brute Force): Scan each window
function maxSlidingWindowBrute(nums, k) {
  const n = nums.length;
  const res = [];
  for (let i = 0; i <= n - k; i++) {
    let mx = -Infinity;
    for (let j = i; j < i + k; j++) mx = Math.max(mx, nums[j]);
    res.push(mx);
  }
  return res;
}
// Time: O(n·k) - scan per window, Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple; works for small inputs.
  • Too slow when k ~ n and n large.

Optimized Solution (Monotonic Deque) ऑप्टिमाइज्ड सॉल्यूशन (मोनोटोनिक डीक्यू)

Javascript 
// Optimized (Monotonic Deque): Indices in decreasing order
function maxSlidingWindow(nums, k) {
  const n = nums.length;
  const res = [];
  const dq = []; // will store indices, values decreasing

  for (let i = 0; i < n; i++) {
    // remove indices out of window (i - k)
    while (dq.length && dq[0] < i - k + 1) dq.shift();

    // remove smaller values at back; they cannot be max
    while (dq.length && nums[dq[dq.length - 1]] < nums[i]) dq.pop();

    dq.push(i);

    // start recording after we have the first full window
    if (i >= k - 1) res.push(nums[dq[0]]);
  }
  return res;
}
// Time: O(n) - each index once, Space: O(k) - deque
Why This Solution? यह सॉल्यूशन क्यों?
  • Each element enters and leaves deque at most once → O(n).
  • Using indices allows checking window bounds cheaply.

Interview Framing इंटरव्यू फ्रेमिंग

“Brute force scans each window O(nk). The monotonic deque is the common O(n) solution: keep indices of useful candidates in decreasing order; index at front is current max; remove out-of-window indices and smaller values when adding a new index.” “ब्रूट स्कैन O(nk)। मोनोटोनिक डीक्यू O(n): डिक्रीजिंग ऑर्डर इंडेक्सेस; फ्रंट मैक्स; आउट-ऑफ-विंडो और स्मॉलर रिमूव ऐड पर।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Clarify k and whether array has duplicates. Brute: compute max per window, O(nk). Optimized: use deque that stores indices of decreasing values. For each new index, pop from back until last value ≥ current; push index; remove front if it's out of window; front is maximum. Provide a small dry run showing how deque evolves for nums = [1,3,-1,-3,5,...]. Clarify k and whether array has duplicates. Brute: compute max per window, O(nk). Optimized: use deque that stores indices of decreasing values. For each new index, pop from back until last value ≥ current; push index; remove front if it's out of window; front is maximum. Provide a small dry run showing how deque evolves for nums = [1,3,-1,-3,5,...].

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“For Sliding Window Maximum, the naive approach computes the max for each window in O(n·k). The optimal is to use a monotonic deque storing indices whose values are decreasing; the front is the current max. For each new index, pop smaller values from the back, drop the front if out of window, then append and record the front once the window is full. This is O(n) time and O(k) space and handles duplicates by storing indices.” “For Sliding Window Maximum, the naive approach computes the max for each window in O(n·k). The optimal is to use a monotonic deque storing indices whose values are decreasing; the front is the current max. For each new index, pop smaller values from the back, drop the front if out of window, then append and record the front once the window is full. This is O(n) time and O(k) space and handles duplicates by storing indices.”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate: fixed window size k, we need max per window.
  • Brute approach: scan each window O(nk).
  • Optimal: monotonic deque of indices, explain push/pop rules.
  • Complexity: O(n) time, O(k) space.
  • Dry-run on a short array and mention edge cases (k=1, k=n).

Container With Most Water (LC 11) – LeetCode कंटेनर विद मोस्ट वॉटर (LC 11) – लीटकोड

Problem: Given n non-negative integers height[i] representing vertical lines at x = i, find two lines that together with the x-axis forms a container that holds the most water. Return the maximum area. समस्या: दिए गए n नॉन-नेगेटिव इंटीजर height[i] x=i पर वर्टिकल लाइन्स, दो लाइन्स x-एक्सिस के साथ मैक्स वॉटर कंटेनर। मैक्स एरिया रिटर्न।

Pattern Tags पैटर्न टैग्स

  • Primary: Two-Pointers, Greedy
  • Secondary: Math (area calculation)
  • Frequency: High (classic two-pointer interview)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: Optimal O(n) time, O(1) space.
  • Edge: All heights equal, zeros, monotonic heights.
  • Self: height = [1,8,6,2,5,4,8,3,7] → max area = 49 (lines at 1 and 8 with width 7 → 7*7).

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Non-negative? n up to 10^5? Area int?" Quick heuristic: "Max area two lines? Hints two-pointer from ends, move smaller." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "नॉन-नेग? n 10^5? एरिया int?" क्विक ह्यूरिस्टिक: "टू लाइन्स मैक्स एरिया? हिन्ट्स एंड्स से टू-पॉइंटर, स्मॉलर मूव।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“max area between two lines” Choose two indices maximize area Two-pointer greedy Move the pointer at smaller height inward to hope for larger height
“area = min(height[i],height[j]) * width” Volume depends on min height Greedy decision rule Moving taller pointer cannot increase area beyond current min * width

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Check all pairs (i, j), compute area = (j - i) * min(height[i], height[j]). Time: O(n²) Space: O(1)
  • Alternative None better than two-pointer for this problem; some proofs show correctness of greedy move.
  • Optimal (Two-Pointer Greedy) Start two pointers L=0, R=n-1. Compute area, move the pointer at smaller height inward (because moving taller pointer cannot produce better area for the same width).

Non-Optimized Solution (Brute Force) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (ब्रूट फोर्स)

Javascript 
// Non-Optimized (Brute Force): All pairs
function maxAreaBrute(height) {
  const n = height.length;
  let maxA = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const area = (j - i) * Math.min(height[i], height[j]);
      maxA = Math.max(maxA, area);
    }
  }
  return maxA;
}
// Time: O(n²) - all pairs, Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple; too slow for large n.

Optimized Solution (Two Pointers) ऑप्टिमाइज्ड सॉल्यूशन (टू पॉइंटर्स)

Javascript 
// Optimized (Two-Pointer Greedy): Move smaller inward
function maxArea(height) {
  let L = 0, R = height.length - 1;
  let maxA = 0;
  while (L < R) {
    const width = R - L;
    const area = width * Math.min(height[L], height[R]);
    maxA = Math.max(maxA, area);
    if (height[L] < height[R]) L++;
    else R--;
  }
  return maxA;
}
// Time: O(n) - single pass, Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • O(n) with simple greedy rule; proven by contradiction that moving smaller height may increase min height.

Interview Framing इंटरव्यू फ्रेमिंग

“Brute force enumerates pairs O(n²). The two-pointer approach starts at both ends and moves the smaller pointer inward; we only need to consider moves that might increase the limiting height. This yields O(n) time and constant space.” “ब्रूट पेयर्स O(n²)। टू-पॉइंटर एंड्स स्टार्ट स्मॉलर इनवर्ड मूव; लिमिटिंग हाइट इनक्रेज मूव्स। O(n) कांस्टेंट स्पेस।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Clarify input size and integer range. Brute force explanation (all pairs). Explain greedy two-pointer: area determined by min height and width. To try to increase area, we must try to increase the min height — so move the pointer at the smaller height inward. Show a small dry run and conclude O(n). Mention edge cases (all zeros, equal heights). Clarify input size and integer range. Brute force explanation (all pairs). Explain greedy two-pointer: area determined by min height and width. To try to increase area, we must try to increase the min height — so move the pointer at the smaller height inward. Show a small dry run and conclude O(n). Mention edge cases (all zeros, equal heights).

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“For Container With Most Water, brute force checks all pairs O(n²). The optimal greedy two-pointer approach places left at 0 and right at n−1, computes area = width * min(height[left], height[right]) and then moves the pointer at the smaller height inward (because moving the larger one cannot increase min height). Repeat until pointers meet and track max area. This yields O(n) time and O(1) space and is easy to dry-run on an example.” “For Container With Most Water, brute force checks all pairs O(n²). The optimal greedy two-pointer approach places left at 0 and right at n−1, computes area = width * min(height[left], height[right]) and then moves the pointer at the smaller height inward (because moving the larger one cannot increase min height). Repeat until pointers meet and track max area. This yields O(n) time and O(1) space and is easy to dry-run on an example.”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate problem (area = width * min height).
  • Mention brute force O(n²).
  • Describe two-pointer greedy: move smaller pointer inward and why.
  • Complexity: O(n) time, O(1) space.
  • Show quick dry-run and list edge cases (all equal heights, zeros).

3Sum Closest (LC 16) – LeetCode 3सम क्लोसेस्ट (LC 16) – लीटकोड

Problem: Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum. समस्या: दिए गए n लेंथ के इंटीजर ऐरे nums और टारगेट में, nums में तीन इंटीजर जिनका सम टारगेट के सबसे करीब। सम रिटर्न करें।

Pattern Tags पैटर्न टैग्स

  • Primary: Sorting, Two-Pointer
  • Secondary: K-sum variant (extension of 2-sum)
  • Frequency: Medium-high

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: Optimal O(n²) time, O(1) space.
  • Edge: Array length < 3 → undefined. Duplicates fine.
  • Self: nums = [-1,2,1,-4], target = 1 → closest sum = 2.

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Array length ≥ 3? Duplicates allowed? n up to 10^3?" Quick heuristic: "Closest sum of three? Hints sort + two-pointer for 2-sum." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "ऐरे लेंथ ≥ 3? डुप्स? n 10^3?" क्विक ह्यूरिस्टिक: "तीन का क्लोसेस्ट सम? हिन्ट्स सॉर्ट + टू-पॉइंटर 2-सम।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“3 integers closest to target” Not exactly equal, minimize diff Sort + 2-pointer Iterate one number, solve 2-sum closest
“return sum” Not indices, but actual sum Greedy search Track running closest and update
“closest” Need |sum-target| minimized Absolute diff compare

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Check all triplets (i,j,k), compute sum, update closest. Time: O(n³) Space: O(1)
  • Alternative Sort then fix one number and binary search for closest pair. Slightly worse complexity than 2-pointer.
  • Optimal (Sort + Two-Pointer) Sort array. For each i, run two pointers (L,R). Compute sum = nums[i]+nums[L]+nums[R]. Update closest if better. Move pointers inward depending on sum vs target.

Non-Optimized Solution (Brute Force) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (ब्रूट फोर्स)

Javascript 
// Brute Force: Check all triplets
function threeSumClosestBrute(nums, target) {
  let n = nums.length;
  let closest = Infinity;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      for (let k = j + 1; k < n; k++) {
        const sum = nums[i] + nums[j] + nums[k];
        if (Math.abs(sum - target) < Math.abs(closest - target)) {
          closest = sum;
        }
      }
    }
  }
  return closest;
}
// Time: O(n³), Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple to understand; checks all possible triplets.
  • Impractical for large n due to O(n³) complexity.

Optimized Solution (Two-Pointer) ऑप्टिमाइज्ड सॉल्यूशन (टू-पॉइंटर)

Javascript 
// Optimized (Sort + Two-Pointer): Sort and search
function threeSumClosest(nums, target) {
  nums.sort((a, b) => a - b);
  let n = nums.length;
  let closest = nums[0] + nums[1] + nums[2];

  for (let i = 0; i < n - 2; i++) {
    let L = i + 1, R = n - 1;
    while (L < R) {
      const sum = nums[i] + nums[L] + nums[R];
      if (Math.abs(sum - target) < Math.abs(closest - target)) {
        closest = sum;
      }
      if (sum < target) L++;
      else if (sum > target) R--;
      else return target; // exact match
    }
  }
  return closest;
}
// Time: O(n²), Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • Efficient O(n²) time, constant space.
  • Leverages sorted order for two-pointer efficiency.

Interview Framing इंटरव्यू फ्रेमिंग

“Brute force tries all triplets O(n³). Optimized: sort array, fix one number, then use two pointers to find best pair for closeness. This reduces complexity to O(n²).” “ब्रूट फोर्स सभी ट्रिपलेट्स O(n³)। ऑप्टिमाइज्ड: ऐरे सॉर्ट, एक नंबर फिक्स, फिर टू पॉइंटर्स से बेस्ट पेयर। O(n²)।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Clarify if array length ≥ 3, duplicates allowed. Brute force: check all triplets, update closest. Optimal: after sorting, fix one index i, then move two pointers inward comparing sum to target. Update if closer. Complexity: O(n²), space O(1). Edge cases: array with exactly 3 numbers, negative/positive mix. ऐरे लेंथ ≥ 3, डुप्स? ब्रूट: सभी ट्रिपलेट्स, अपडेट क्लोसेस्ट। ऑप्टिमल: सॉर्ट, i फिक्स, टू पॉइंटर्स इनवर्ड सम vs टारगेट। क्लोजर अपडेट। O(n²), O(1)। एज: ठीक 3 नंबर, नेग/पॉज मिक्स।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“For 3Sum Closest, the brute force approach is to try all triplets in O(n³) and track the one with smallest absolute difference. To optimize, I sort the array, then for each element use two pointers on the rest to get a candidate sum in O(n²). At each step I update the closest sum if it improves the difference. This runs in O(n²) with O(1) space and handles negatives and duplicates fine. For example, in [-1,2,1,-4] with target=1, the closest sum is 2.” “3सम क्लोसेस्ट, ब्रूट सभी ट्रिपलेट्स O(n³), मिन डिफ ट्रैक। ऑप्टिमाइज: सॉर्ट, हर एलिमेंट टू पॉइंटर्स O(n²)। हर स्टेप अपडेट क्लोसेस्ट। O(n²), O(1), नेग/डुप्स। उदाहरण: [-1,2,1,-4] टारगेट=1 → 2।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate problem + constraints.
  • Mention brute force approach and complexity.
  • Describe optimal pattern (sliding, two-pointer, etc.).
  • State time/space complexity.
  • Give quick example run and edge case.

Find Minimum in Rotated Sorted Array (LC 153) – LeetCode रोटेटेड सॉर्टेड ऐरे में मिनिमम (LC 153) – लीटकोड

Problem: Suppose an array of length n sorted in ascending order is rotated at some pivot. Find the minimum element. Assume no duplicates. समस्या: n लेंथ का सॉर्टेड ऐरे किसी पिवट पर रोटेटेड। मिनिमम एलिमेंट ढूंढें। कोई डुप्लिकेट्स नहीं।

Pattern Tags पैटर्न टैग्स

  • Primary: Binary Search Variant
  • Secondary: Rotated Array, Divide & Conquer
  • Frequency: High (classic modified binary search)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: O(log n)
  • Edge: Array not rotated, length=1.
  • Self: [3,4,5,1,2] → min=1.

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "No duplicates? n up to 10^4?" Quick heuristic: "Min in rotated array? Hints binary search." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "कोई डुप्स नहीं? n 10^4?" क्विक ह्यूरिस्टिक: "रोटेटेड में मिन? हिन्ट्स बाइनरी सर्च।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“rotated sorted array” One pivot point only Modified binary search Compare mid with right to decide side
“find minimum” Pivot element Binary search half Minimum in unsorted half
“no duplicates” Simplifies comparison Strict inequalities

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Scan all elements and return min. O(n).
  • Alternative Use recursion to check halves.
  • Optimal (Binary Search) Compare mid with right: If nums[mid] > nums[right], min is in right half. Else min is in left half.

Non-Optimized Solution (Linear Scan) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (लिनियर स्कैन)

Javascript 
// Non-Optimized (Linear Scan): Scan all elements
function findMinBrute(nums) {
  let minVal = nums[0];
  for (let n of nums) minVal = Math.min(minVal, n);
  return minVal;
}
// Time: O(n), Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple but inefficient for large arrays.

Optimized Solution (Binary Search) ऑप्टिमाइज्ड सॉल्यूशन (बाइनरी सर्च)

Javascript 
// Optimized (Binary Search): Compare mid with right
function findMin(nums) {
  let L = 0, R = nums.length - 1;
  while (L < R) {
    const mid = Math.floor((L + R) / 2);
    if (nums[mid] > nums[R]) L = mid + 1;
    else R = mid;
  }
  return nums[L];
}
// Time: O(log n), Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • Efficient O(log n) time, constant space.
  • Leverages sorted property of rotated array.

Interview Framing इंटरव्यू फ्रेमिंग

“Brute is O(n). Binary search compares mid vs right; if mid > right, min in right half; otherwise min in left. Loop until pointers meet.” “ब्रूट O(n)। बाइनरी सर्च मिड vs राइट; मिड > राइट, मिन राइट हाफ; वरना लेफ्ट। लूप तक पॉइंटर्स मिलें।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Clarify no duplicates; rotation at one pivot. Brute: linear scan O(n). Optimal: binary search. If nums[mid] > nums[right], pivot is right; else pivot is left. Complexity O(log n). Edge cases: n=1, already sorted array. कोई डुप्स नहीं; एक पिवट पर रोटेशन। ब्रूट: लिनियर स्कैन O(n)। ऑप्टिमल: बाइनरी सर्च। nums[mid] > nums[right], पिवट राइट; वरना लेफ्ट। O(log n)। एज: n=1, पहले से सॉर्टेड।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“To find the minimum in a rotated sorted array, the brute force way is linear scan. Optimally, use binary search: compare mid with right — if nums[mid] > nums[right], then the minimum lies in the right half; otherwise it lies in the left half. Continue until L == R, which gives the pivot. This runs in O(log n). For example, in [3,4,5,1,2] mid=5>2, so min is on right, giving 1.” “रोटेटेड सॉर्टेड ऐरे में मिन, ब्रूट लिनियर स्कैन। ऑप्टिमल: बाइनरी सर्च: मिड vs राइट — nums[mid] > nums[right], मिन राइट हाफ; वरना लेफ्ट। L == R तक, पिवट। O(log n)। उदाहरण: [3,4,5,1,2] मिड=5>2, मिन राइट, 1।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate & clarify constraints.
  • Brute method + O(n).
  • Optimal pattern (binary search).
  • Time/space.
  • Example + edge cases.

Find First and Last Position of Element in Sorted Array (LC 34) – LeetCode सॉर्टेड ऐरे में फर्स्ट और लास्ट पोजीशन (LC 34) – लीटकोड

Problem: Given an array of integers sorted in non-decreasing order, find the first and last position of a given target. If not found, return [-1,-1]. समस्या: नॉन-डिक्रीजिंग सॉर्टेड इंटीजर ऐरे में, टारगेट की फर्स्ट और लास्ट पोजीशन। नहीं मिला तो [-1,-1]।

Pattern Tags पैटर्न टैग्स

  • Primary: Binary Search Variant
  • Secondary: Range finding
  • Frequency: High

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: O(log n)
  • Edge: Element not present, duplicates, array length 0.
  • Self: nums=[5,7,7,8,8,10], target=8 → [3,4].

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Duplicates allowed? n up to 10^5?" Quick heuristic: "First/last in sorted? Two binary searches." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "डुप्स? n 10^5?" क्विक ह्यूरिस्टिक: "सॉर्टेड में फर्स्ट/लास्ट? टू बाइनरी सर्च।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“first and last position” Need both boundaries Modified binary search Two passes: leftmost & rightmost
“sorted array” Enables binary search Left/right biased search Use mid differently in each pass
“not found → [-1,-1]” Return sentinel result Check after loop

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Linear scan for first and last. O(n).
  • Alternative Single binary search then expand outward.
  • Optimal (Two Binary Searches) Do left-biased binary search for first position; right-biased for last.

Non-Optimized Solution (Linear Scan) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (लिनियर स्कैन)

Javascript 
// Non-Optimized (Linear Scan): Find first and last
function searchRangeBrute(nums, target) {
  let first = -1, last = -1;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) {
      if (first === -1) first = i;
      last = i;
    }
  }
  return [first, last];
}
// Time: O(n), Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple, but inefficient for large sorted arrays.

Optimized Solution (Binary Search for bounds) ऑप्टिमाइज्ड सॉल्यूशन (बाइनरी सर्च फॉर बाउंड्स)

Javascript 
// Optimized (Binary Search for bounds): Left and right biased
function searchRange(nums, target) {
  function findBound(isFirst) {
    let L = 0, R = nums.length - 1, ans = -1;
    while (L <= R) {
      const mid = Math.floor((L + R) / 2);
      if (nums[mid] === target) {
        ans = mid;
        if (isFirst) R = mid - 1; // continue left
        else L = mid + 1;        // continue right
      } else if (nums[mid] < target) {
        L = mid + 1;
      } else {
        R = mid - 1;
      }
    }
    return ans;
  }

  return [findBound(true), findBound(false)];
}
// Time: O(log n), Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • Efficient O(log n) time, constant space.
  • Handles duplicates with biased searches.

Interview Framing इंटरव्यू फ्रेमिंग

“Brute scans entire array O(n). Optimal is two binary searches: one biased left to find first, another biased right to find last. Complexity O(log n).” “ब्रूट पूरा ऐरे स्कैन O(n)। ऑप्टिमल: टू बाइनरी सर्च, एक लेफ्ट बायस्ड फर्स्ट, दूसरा राइट बायस्ड लास्ट। O(log n)।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Clarify: array sorted, may have duplicates. Brute: scan linearly. Optimal: binary search with bias. On match, continue searching left for first, right for last. Complexity: O(log n). Edge cases: element absent → [-1,-1], single element array. स्पष्ट करें: ऐरे सॉर्टेड, डुप्स। ब्रूट: लिनियर स्कैन। ऑप्टिमल: बायस्ड बाइनरी सर्च। मैच पर, फर्स्ट के लिए लेफ्ट, लास्ट के लिए राइट। O(log n)। एज: एलिमेंट नहीं → [-1,-1], सिंगल एलिमेंट।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“For searching the first and last position of a target, brute force is linear scan. Optimally, I use two binary searches: one biased left to find the first index, and one biased right to find the last. On each match we update the answer and continue in the chosen direction. This guarantees O(log n) time. For example, nums=[5,7,7,8,8,10], target=8 → first=3, last=4.” “टारगेट की फर्स्ट और लास्ट पोजीशन, ब्रूट लिनियर स्कैन। ऑप्टिमल: टू बाइनरी सर्च, लेफ्ट बायस्ड फर्स्ट, राइट बायस्ड लास्ट। मैच पर अपडेट, चुनी दिशा में। O(log n)। उदाहरण: nums=[5,7,7,8,8,10], टारगेट=8 → फर्स्ट=3, लास्ट=4।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate problem.
  • Brute scan + O(n).
  • Optimal binary search variant.
  • Complexity O(log n).
  • Example + absent case.

Search a 2D Matrix (LC 74) – LeetCode 2D मैट्रिक्स सर्च (LC 74) – लीटकोड

Problem: Write an efficient algorithm that searches for a target value in an m x n matrix. This matrix has the properties that each row is sorted left to right, and the first integer of each row is greater than the last integer of the previous row. समस्या: m x n मैट्रिक्स में टारगेट वैल्यू सर्च करें। मैट्रिक्स: हर रो लेफ्ट टु राइट सॉर्टेड, हर रो का फर्स्ट इंटीजर पिछले रो के लास्ट से बड़ा।

Pattern Tags पैटर्न टैग्स

  • Primary: Binary Search (2D → 1D mapping)
  • Secondary: Matrix flattening, Divide & Conquer
  • Frequency: Medium (classic binary-search-on-matrix)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: Optimal O(log(m·n)) time, O(1) extra space. Alternative two-step binary search O(log m + log n).
  • Edge: Empty matrix, single row, single column.
  • Self: matrix = [[1,3,5],[7,9,11],[13,15,17]], target = 9 → true.

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Matrix non-empty? m,n ranges?" Quick heuristic: "Sorted matrix? Treat as 1D for binary search." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "मैट्रिक्स नॉन-एम्प्टी? m,n रेंज?" क्विक ह्यूरिस्टिक: "सॉर्टेड मैट्रिक्स? 1D की तरह बाइनरी सर्च।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“each row sorted, first of row > last of prev” Global row-major sorted order Binary search on virtual 1D array Map mid → matrix[row][col] using div/mod
“search target” Return boolean Binary search Treat matrix as sorted list of length m*n
“m x n” Size for indexing Index conversion: row = mid/cols Or do two-step: find row then binary search col

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Scan all elements and compare to target. Time: O(m·n) Space: O(1)
  • Alternative Two-stage binary search: first binary search rows to find candidate row (based on first/last element), then binary search within that row → O(log m + log n).
  • Optimal Treat matrix as a 1D sorted array of length m*n and do binary search using index → map index to matrix[Math.floor(mid / n)][mid % n]. Complexity O(log(m·n)).

Non-Optimized Solution (Brute Force) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (ब्रूट फोर्स)

Javascript 
// Non-Optimized (Brute Force): Scan all elements
function searchMatrixBrute(matrix, target) {
  for (let r = 0; r < matrix.length; r++) {
    for (let c = 0; c < matrix[0].length; c++) {
      if (matrix[r][c] === target) return true;
    }
  }
  return false;
}
// Time: O(m*n), Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • Trivial to implement; works for small matrices.
  • Too slow for large matrices compared to binary search.

Optimized Solution (Binary Search on Virtual 1D) ऑप्टिमाइज्ड सॉल्यूशन (वर्चुअल 1D पर बाइनरी सर्च)

Javascript 
// Optimized (Binary Search on Virtual 1D): Map indices
function searchMatrix(matrix, target) {
  if (!matrix || matrix.length === 0 || matrix[0].length === 0) return false;
  const m = matrix.length, n = matrix[0].length;
  let lo = 0, hi = m * n - 1;

  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    const val = matrix[Math.floor(mid / n)][mid % n];
    if (val === target) return true;
    if (val < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return false;
}
// Time: O(log(m*n)), Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • Uses the given ordering across rows to do a single binary search.
  • Clean index mapping avoids extra allocations and is optimal.

Interview Framing इंटरव्यू फ्रेमिंग

“Brute force scans O(m·n). Since rows are ordered and first of each row > last of previous, you can treat matrix as a flattened sorted array and binary-search over indices (or two-stage binary search). This gives O(log(m·n)).” “ब्रूट स्कैन O(m·n)। रो सॉर्टेड और हर रो का फर्स्ट > पिछले लास्ट, मैट्रिक्स को फ्लैट सॉर्टेड ऐरे की तरह बाइनरी सर्च (या टू-स्टेज)। O(log(m·n))।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Clarify matrix properties (row-sorted, row boundaries greater than previous). Brute force vs. binary-search options. Show index mapping row = Math.floor(idx / n) and col = idx % n. State complexity O(log(m·n)). Give example: map mid to element and continue search. मैट्रिक्स प्रॉपर्टीज (रो-सॉर्टेड, रो बाउंड्रीज पिछले से बड़ी)। ब्रूट vs बाइनरी सर्च। इंडेक्स मैपिंग row = Math.floor(idx / n), col = idx % n। O(log(m·n))। उदाहरण: मिड को एलिमेंट मैप।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“Naïve approach scans all m×n entries in O(m·n). Because each row is sorted and the first element of each row is greater than the last of the previous row, the whole matrix is ordered row-major. So I treat it as a 1D sorted array of length m·n and run binary search mapping the mid index to matrix[Math.floor(mid/n)][mid%n]. This yields O(log(m·n)) time and O(1) extra space. For example, with [[1,3,5],[7,9,11]] and target=9, mapping finds 9 at the correct mapped index.” “नाइव m×n एंट्रीज स्कैन O(m·n)। रो सॉर्टेड, फर्स्ट > पिछले लास्ट, मैट्रिक्स रो-मेजर सॉर्टेड। m·n लेंथ का 1D ऐरे, बाइनरी सर्च मिड को matrix[Math.floor(mid/n)][mid%n]। O(log(m·n)), O(1)। उदाहरण: [[1,3,5],[7,9,11]], टारगेट=9, मैपिंग 9।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate constraints (row ordering property).
  • Mention brute force O(m·n).
  • Present optimal: binary search on virtual 1D (or two-stage).
  • State time/space complexity.
  • Short dry-run and edge-case (empty matrix).

Find Peak Element (LC 162) – LeetCode पीक एलिमेंट ढूंढें (LC 162) – लीटकोड

Problem: A peak element is an element strictly greater than its neighbors. Given an array nums, return the index of any peak element. Assume nums[i] != nums[i+1] (no equal adjacent). The array may have multiple peaks — any index is acceptable. समस्या: पीक एलिमेंट पड़ोसियों से सख्ती से बड़ा। nums ऐरे में, किसी भी पीक एलिमेंट का इंडेक्स। nums[i] != nums[i+1] (कोई बराबर पड़ोसी नहीं)। मल्टीपल पीक्स, कोई भी इंडेक्स ठीक।

Pattern Tags पैटर्न टैग्स

  • Primary: Binary Search (peak finding)
  • Secondary: Divide & Conquer, Greedy
  • Frequency: Medium (binary search trick question)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: O(log n) time, O(1) space for binary-search solution.
  • Edge: Single element → index 0. Boundary peaks valid.
  • Self: nums = [1,2,3,1] → peak index = 2.

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "No equal neighbors? n range?" Quick heuristic: "Peak finding? Binary search on slope." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "कोई बराबर पड़ोसी नहीं? n रेंज?" क्विक ह्यूरिस्टिक: "पीक फाइंडिंग? स्लोप पर बाइनरी सर्च।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“peak element” Strictly greater than neighbors Binary search using slope Compare mid to mid+1 to decide slope direction
“return any peak” Not unique; any valid index Binary search suffices If mid < mid+1, go right; else go left
“nums[i] != nums[i+1]” No equal neighbors Strict comparison safe Guarantees a peak exists

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Scan array and return index i where nums[i] > nums[i-1] and nums[i] > nums[i+1]. Time: O(n) Space: O(1)
  • Alternative Linear scan for first element greater than next (works but O(n)).
  • Optimal Binary search on gradient: if nums[mid] < nums[mid+1] then there is a peak to the right; else a peak to the left (including mid).

Non-Optimized Solution (Linear Scan) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (लिनियर स्कैन)

Javascript 
// Non-Optimized (Linear Scan): Check neighbors
function findPeakElementBrute(nums) {
  const n = nums.length;
  if (n === 1) return 0;
  if (nums[0] > nums[1]) return 0;
  if (nums[n-1] > nums[n-2]) return n-1;
  for (let i = 1; i < n - 1; i++) {
    if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) return i;
  }
  return 0; // fallback
}
// Time: O(n), Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple, finds some peak in linear time. Acceptable for many cases but not optimal.

Optimized Solution (Binary Search on Slope) ऑप्टिमाइज्ड सॉल्यूशन (स्लोप पर बाइनरी सर्च)

Javascript 
// Optimized (Binary Search on Slope): Check slope
function findPeakElement(nums) {
  let L = 0, R = nums.length - 1;
  while (L < R) {
    const mid = Math.floor((L + R) / 2);
    if (nums[mid] < nums[mid + 1]) {
      // ascending slope, peak on right
      L = mid + 1;
    } else {
      // descending slope, peak at mid or left
      R = mid;
    }
  }
  return L; // L === R at peak
}
// Time: O(log n), Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • Uses slope property to discard half each time. Guaranteed to converge to a peak because array ends trend to -∞ conceptually.

Interview Framing इंटरव्यू फ्रेमिंग

“Brute finds peak in O(n). Binary-search approach compares mid with mid+1: if increasing, go right; otherwise go left. This shrinks search space logarily and returns an index of a peak.” “ब्रूट पीक O(n)। बाइनरी-सर्च मिड vs मिड+1: बढ़ रहा, राइट; वरना लेफ्ट। सर्च स्पेस लॉग, पीक इंडेक्स।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Confirm nums[i] != nums[i+1] and array length. Brute scan or early checks at boundaries. Optimal: binary-search on slope using nums[mid] < nums[mid+1] rule. Complexity O(log n). Give small dry-run like [1,2,3,1]. nums[i] != nums[i+1], ऐरे लेंथ। ब्रूट स्कैन या बाउंड्री चेक। ऑप्टिमल: स्लोप पर बाइनरी सर्च nums[mid] < nums[mid+1]। O(log n)। ड्राई-रन [1,2,3,1]।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“Brute-force is to scan and find an index where an element is greater than both neighbors in O(n). But by observing slope, if nums[mid] < nums[mid+1], a peak must exist on the right; otherwise on the left. So use binary search: if mid < mid+1, move left to mid+1; else move right to mid. Continue until pointers meet — that index is a peak. This runs in O(log n).” “ब्रूट स्कैन, इंडेक्स जहां एलिमेंट पड़ोसियों से बड़ा O(n)। स्लोप: nums[mid] < nums[mid+1], पीक राइट; वरना लेफ्ट। बाइनरी सर्च: मिड < मिड+1, लेफ्ट मिड+1; वरना राइट मिड। पॉइंटर्स मिलें — पीक। O(log n)।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate and confirm constraints (nums[i] != nums[i+1]).
  • Brute method O(n) quick mention.
  • Present binary-search-on-slope idea and why it works.
  • Complexity O(log n).
  • Example and edge-case single-element.

Top K Frequent Elements (LC 347) – LeetCode टॉप K फ्रिक्वेंट एलिमेंट्स (LC 347) – लीटकोड

Problem: Given a non-empty array of integers, return the k most frequent elements. समस्या: नॉन-एम्प्टी इंटीजर ऐरे में, k सबसे फ्रिक्वेंट एलिमेंट्स रिटर्न करें।

Pattern Tags पैटर्न टैग्स

  • Primary: Heap / Bucket Sort, Frequency Map
  • Secondary: Sorting by frequency
  • Frequency: High (classic frequency/top-k problem)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: Sorting approach: O(n log n), Heap (min-heap size k): O(n log k), Bucket sort: O(n) average (if frequencies bounded by n).
  • Edge: k = number of unique elements, many duplicates.
  • Self: nums = [1,1,1,2,2,3], k = 2 → [1,2].

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "k range? Unique elements?" Quick heuristic: "Top k frequent? Heap or bucket sort." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "k रेंज? यूनिक एलिमेंट्स?" क्विक ह्यूरिस्टिक: "टॉप k फ्रिक्वेंट? हीप या बकेट सॉर्ट।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“k most frequent” Need top-k by frequency Heap or Bucket sort Count frequencies, then extract top-k
“non-empty array” Count map straightforward Map → bucket/heap/sort Choose method based on k vs n
“return elements” Not counts Return keys, not values Use key lists from buckets or heap

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Count frequencies, sort unique elements by frequency descending. Time: O(n log n) Space: O(n)
  • Alternative Use min-heap of size k for streaming top-k → O(n log k).
  • Optimal Bucket sort by frequency: build freq map, then array of buckets where index = frequency, collect from high to low until k elements gathered → average O(n).

Non-Optimized Solution (Sort by Frequency) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (फ्रिक्वेंसी सॉर्ट)

Javascript 
// Non-Optimized (Sort by Frequency): Sort map entries
function topKFrequentBrute(nums, k) {
  const freq = new Map();
  for (const x of nums) freq.set(x, (freq.get(x) || 0) + 1);
  const items = Array.from(freq.entries()); // [num, count]
  items.sort((a, b) => b[1] - a[1]); // sort desc by count
  return items.slice(0, k).map(x => x[0]);
}
// Time: O(n log n), Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple to implement; fine for moderate n.
  • Sorting large unique keys can be slower than heap/bucket.

Optimized Solution (Bucket Sort by Frequency) ऑप्टिमाइज्ड सॉल्यूशन (फ्रिक्वेंसी बकेट सॉर्ट)

Javascript 
// Optimized (Bucket Sort by Frequency): Use frequency buckets
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const x of nums) freq.set(x, (freq.get(x) || 0) + 1);

  const buckets = Array(nums.length + 1).fill(null).map(() => []);
  for (const [num, count] of freq.entries()) {
    buckets[count].push(num);
  }

  const res = [];
  for (let i = buckets.length - 1; i >= 0 && res.length < k; i--) {
    for (const num of buckets[i]) {
      res.push(num);
      if (res.length === k) break;
    }
  }
  return res;
}
// Time: O(n), Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Linear time in terms of n (frequency counting + bucket fill + traverse).
  • Very efficient when counts are within 0..n.

Interview Framing इंटरव्यू फ्रेमिंग

“Compute frequencies with a hash map, then either sort unique keys by frequency (O(n log n)), use a min-heap of size k for O(n log k), or use bucket sort for O(n). Bucket sort is elegant for integer keys because frequency ≤ n.” “हैश मैप से फ्रिक्वेंसी, फिर यूनिक कीज सॉर्ट (O(n log n)), मिन-हीप k साइज O(n log k), या बकेट सॉर्ट O(n)। बकेट सॉर्ट इंटीजर कीज के लिए, फ्रिक्वेंसी ≤ n।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Build frequency map. Explain options: sort (easy), heap (good when k ≪ n), buckets (linear). Choose bucket solution: create buckets indexed by frequency and traverse from high to low to collect top k. Complexity tradeoffs and edge cases. Example with nums [1,1,1,2,2,3]. फ्रिक्वेंसी मैप बनाएँ। ऑप्शन्स: सॉर्ट (आसान), हीप (k ≪ n), बकेट्स (लिनियर)। बकेट सॉल्यूशन: फ्रिक्वेंसी इंडेक्स्ड बकेट्स, हाई टू लो ट्रैवर्स टॉप k। कॉम्प्लेक्सिटी ट्रेडऑफ्स, एज केस। उदाहरण nums [1,1,1,2,2,3]।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“First count frequencies in a hash map. Common solutions: sort keys by frequency (O(n log n)), use a min-heap of size k (O(n log k)), or do bucket sort since frequencies are bounded by n. In bucket sort, create an array of size n+1 where index i holds numbers that appear i times, then traverse from high frequency down and collect k elements. This gives O(n) time and O(n) space.” “पहले हैश मैप में फ्रिक्वेंसी गिनें। सॉल्यूशन्स: कीज सॉर्ट (O(n log n)), k साइज मिन-हीप (O(n log k)), या बकेट सॉर्ट, फ्रिक्वेंसी ≤ n। बकेट सॉर्ट: n+1 साइज ऐरे, इंडेक्स i में i बार वाले नंबर, हाई फ्रिक्वेंसी से k एलिमेंट्स। O(n) टाइम, O(n) स्पेस।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate problem (top-k by frequency).
  • Brute: sort unique keys by frequency O(n log n).
  • Present alternatives: heap (O(n log k)) vs bucket (O(n)).
  • Pick approach, state complexity.
  • Quick dry-run and mention k-edge cases.

Merge k Sorted Lists (LC 23) – LeetCode k सॉर्टेड लिस्ट्स मर्ज करें (LC 23) – लीटकोड

Problem: Given an array of k linked-lists each sorted in ascending order, merge all the linked lists into one sorted linked list and return it. समस्या: k लिंक्ड-लिस्ट्स का ऐरे, प्रत्येक ascending सॉर्टेड, सभी को मर्ज करके एक सॉर्टेड लिंक्ड लिस्ट रिटर्न करें।

Pattern Tags पैटर्न टैग्स

  • Primary: Heap (priority queue) OR Divide & Conquer merge
  • Secondary: Linked list merge (two-list merge)
  • Frequency: High (common linked-list + heap pattern)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: Sequential merge one-by-one: O(k·N) (N total nodes), Divide & conquer or heap: O(N log k) (optimal).
  • Edge: Some lists may be null / empty list. k can be large.
  • Self: [[1,4,5],[1,3,4],[2,6]] → [1,1,2,3,4,4,5,6].

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Empty lists allowed? k range?" Quick heuristic: "Merge k sorted? Heap or divide & conquer." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "खाली लिस्ट्स? k रेंज?" क्विक ह्यूरिस्टिक: "k सॉर्टेड मर्ज? हीप या डिवाइड & कॉन्कर।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“merge k sorted lists” Multiple sorted inputs Min-heap of heads or divide & conquer Merge lists pairwise to reduce merges
“linked lists” Node-level pointer manipulation MergeTwoLists helper Reuse nodes to avoid extra space
“k can be large” Complexity sensitive to k Aim for O(N log k) Either heap of k heads (log k per pop)

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Sequentially merge lists: take result = merge(result, lists[i]) for i in 0..k-1 → O(k·N). Time: O(k·N) Space: O(1) extra (reusing nodes)
  • Alternative Use a min-heap containing current heads of each list — pop min and push its next → O(N log k). Also divide & conquer pairwise merging reduces merges to log k levels each costing O(N) per level → O(N log k).
  • Optimal Divide & conquer pairwise merging: merge lists in pairs recursively to achieve O(N log k).

Helper Function (Merge Two Lists) हेल्पर फंक्शन (टू लिस्ट्स मर्ज)

Javascript 
// Helper: Merge two sorted lists
function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (l1 && l2) {
    if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; }
    else { tail.next = l2; l2 = l2.next; }
    tail = tail.next;
  }
  tail.next = l1 || l2;
  return dummy.next;
}
// Time: O(n + m), Space: O(1)

Non-Optimized Solution (Sequential Merge) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (सीक्वेंशियल मर्ज)

Javascript 
// Non-Optimized (Sequential Merge): Merge one-by-one
function mergeKListsSequential(lists) {
  if (!lists || lists.length === 0) return null;
  let merged = null;
  for (let list of lists) {
    merged = mergeTwoLists(merged, list);
  }
  return merged;
}
// Time: O(k * N), Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple to implement using mergeTwoLists.
  • Can be slow when k is large because we repeatedly traverse merged list.

Optimized Solution (Divide & Conquer Pairwise Merge) ऑप्टिमाइज्ड सॉल्यूशन (डिवाइड & कॉन्कर पेयरवाइज मर्ज)

Javascript 
// Optimized (Divide & Conquer Pairwise Merge): Recursive merge
function mergeKLists(lists) {
  if (!lists || lists.length === 0) return null;

  function mergeRange(lists, left, right) {
    if (left === right) return lists[left];
    const mid = Math.floor((left + right) / 2);
    const l = mergeRange(lists, left, mid);
    const r = mergeRange(lists, mid + 1, right);
    return mergeTwoLists(l, r);
  }

  return mergeRange(lists, 0, lists.length - 1);
}
// Time: O(N log k), Space: O(log k)
Why This Solution? यह सॉल्यूशन क्यों?
  • Merges lists in pairs, cutting number of merges and balancing work → O(N log k).
  • Easier to implement than heap in some languages and efficient.

Interview Framing इंटरव्यू फ्रेमिंग

“Sequential merging is simplest but can be O(k·N). Two common optimal approaches: use a min-heap of k heads (pop smallest, push next) or pairwise divide & conquer merging (merge pairs recursively). Both achieve O(N log k).” “सीक्वेंशियल मर्जिंग सबसे आसान लेकिन O(k·N)। दो ऑप्टिमल: k हेड्स का मिन-हीप (सबसे छोटा पॉप, नेक्स्ट पुश) या पेयरवाइज डिवाइड & कॉन्कर (पेयर्स रिकर्सिव मर्ज)। दोनों O(N log k)।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Explain mergeTwoLists (two-pointer merge). Brute sequential merge and complexity O(k·N). Present heap approach or divide & conquer. I prefer divide & conquer for clarity: recursively merge halves until one list. Complexity O(N log k). Edge cases: null lists, single list, memory reuse by re-linking nodes. mergeTwoLists (टू-पॉइंटर मर्ज)। ब्रूट सीक्वेंशियल मर्ज O(k·N)। हीप या डिवाइड & कॉन्कर। डिवाइड & कॉन्कर क्लैरिटी: हाफ्स रिकर्सिव मर्ज। O(N log k)। एज केस: नल लिस्ट्स, सिंगल लिस्ट, नोड्स री-लिंक।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“A straightforward solution merges lists one-by-one in O(k·N). For better performance, you can either keep a min-heap of the current head of each list and repeatedly extract the smallest (O(N log k)), or do divide & conquer pairwise merging: recursively merge left and right halves until one list remains; this also runs in O(N log k). I typically implement divide & conquer because it’s easy to code with the mergeTwoLists helper and gives the optimal time.” “सीधा सॉल्यूशन लिस्ट्स वन-बाय-वन मर्ज O(k·N)। बेहतर: मिन-हीप k हेड्स, सबसे छोटा निकालें (O(N log k)), या डिवाइड & कॉन्कर पेयरवाइज मर्जिंग: लेफ्ट-राइट हाफ्स रिकर्सिव मर्ज। O(N log k)। डिवाइड & कॉन्कर आसान, mergeTwoLists हेल्पर, ऑप्टिमल टाइम।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate problem and confirm list/empty cases.
  • Brute: sequential merging O(k·N).
  • Optimal patterns: min-heap (priority queue) or divide & conquer.
  • Complexity: O(N log k).
  • Example & edge-case notes (null lists, reuse nodes).

IPO (LC 502) – LeetCode IPO (LC 502) – लीटकोड

Problem: You are given k (max projects you can pick), initial capital W, and two arrays profits and capital of equal length n. Each project i requires capital[i] to start and yields profits[i] profit (added to your capital when finished). Select at most k projects to maximize final capital. Return final capital. समस्या: k (अधिकतम प्रोजेक्ट्स), प्रारंभिक पूंजी W, और दो समान लंबाई n के ऐरे profits और capital दिए गए हैं। प्रत्येक प्रोजेक्ट i को शुरू करने के लिए capital[i] चाहिए और profits[i] लाभ देता है। अधिकतम k प्रोजेक्ट्स चुनें ताकि अंतिम पूंजी अधिकतम हो। अंतिम पूंजी रिटर्न करें।

Pattern Tags पैटर्न टैग्स

  • Primary: Greedy + Heaps (Priority Queues)
  • Secondary: Sorting, Simulation
  • Frequency: Medium (heap + greedy trick)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: Optimal O(n log n + k log n) time (dominant due to heap ops), O(n) space.
  • Edge: k = 0 → return W; all projects require more capital than W → return W.
  • Self: Example: k=2, W=0, profits=[1,2,3], capital=[0,1,1] → pick project0 (W=1), then project2 (profit 3) → final W=4.

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "k range? Capital limits?" Quick heuristic: "Maximize by picking best affordable projects? Greedy + heap." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "k रेंज? पूंजी सीमा?" क्विक ह्यूरिस्टिक: "सर्वश्रेष्ठ किफायती प्रोजेक्ट्स? ग्रीडी + हीप।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“at most k projects” Greedy repeated selection over k rounds Repeated selection with heap At each round, pick best profit among affordable
“initial capital W” Affordability filter by capital required Min-heap by capital → max-heap by profit Move affordable projects to profit-heap, pop best
“maximize final capital” Greedy incremental improvement Use two heaps + sort Sorting + pushing to profit heap as W grows

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Try all combinations of up to k projects (subset search) and compute final capitals — exponential O(C(n,k)) — impractical.
  • Alternative Sort projects by capital and for each round scan affordable ones to find max profit (O(n·k) worst-case) — better than brute but slow for large n.
  • Optimal Sort projects by capital ascending. Maintain two heaps: a min-heap (or pointer into sorted list) over capital to discover newly affordable projects, a max-heap over profits of currently affordable projects. Repeat up to k times: move all projects whose capital ≤ current W into profit-max-heap, then pop top profit (if any) and add to W.

Non-Optimized Solution (Naïve scanning each round) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (प्रत्येक राउंड में नाइव स्कैनिंग)

Javascript 
// Naive: for up to k rounds, scan projects to find max-profit affordable project
function findFinalCapitalNaive(k, W, profits, capital) {
  const n = profits.length;
  const used = new Array(n).fill(false);
  for (let i = 0; i < k; i++) {
    let best = -1, bestIdx = -1;
    for (let j = 0; j < n; j++) {
      if (!used[j] && capital[j] <= W) {
        if (profits[j] > best) { best = profits[j]; bestIdx = j; }
      }
    }
    if (bestIdx === -1) break;
    used[bestIdx] = true;
    W += profits[bestIdx];
  }
  return W;
}
// Time: O(k * n), Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple and straightforward.
  • Too slow when n and k are large.

Optimized Solution (Sort + Two Heaps) ऑप्टिमाइज्ड सॉल्यूशन (सॉर्ट + टू हीप्स)

Javascript 
// Simple binary heap implementation (min or max by comparator)
class Heap {
  constructor(comparator = (a,b) => a - b) {
    this.data = [];
    this.compare = comparator;
  }
  size(){ return this.data.length; }
  peek(){ return this.data[0]; }
  push(val){
    this.data.push(val);
    this._siftUp();
  }
  pop(){
    if (!this.data.length) return undefined;
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length) {
      this.data[0] = last;
      this._siftDown();
    }
    return top;
  }
  _siftUp(){
    let idx = this.data.length - 1;
    while (idx > 0) {
      const parent = Math.floor((idx - 1) / 2);
      if (this.compare(this.data[idx], this.data[parent]) < 0) {
        [this.data[idx], this.data[parent]] = [this.data[parent], this.data[idx]];
        idx = parent;
      } else break;
    }
  }
  _siftDown(){
    let idx = 0;
    const n = this.data.length;
    while (true) {
      let left = idx * 2 + 1, right = idx * 2 + 2, smallest = idx;
      if (left < n && this.compare(this.data[left], this.data[smallest]) < 0) smallest = left;
      if (right < n && this.compare(this.data[right], this.data[smallest]) < 0) smallest = right;
      if (smallest !== idx) {
        [this.data[idx], this.data[smallest]] = [this.data[smallest], this.data[idx]];
        idx = smallest;
      } else break;
    }
  }
}

// Main solution
function findMaximizedCapital(k, W, profits, capital) {
  const n = profits.length;
  const projects = [];
  for (let i = 0; i < n; i++) projects.push([capital[i], profits[i]]);
  projects.sort((a,b) => a[0] - b[0]); // sort by capital required asc

  // min-heap for capital is simulated by scanning sorted array with index
  // max-heap for profits (use comparator that returns negative for larger profit)
  const profitHeap = new Heap((a,b) => b - a); // max-heap via comparator
  let idx = 0;
  for (let i = 0; i < k; i++) {
    while (idx < n && projects[idx][0] <= W) {
      profitHeap.push(projects[idx][1]);
      idx++;
    }
    if (profitHeap.size() === 0) break;
    W += profitHeap.pop();
  }
  return W;
}
// Time: O(n log n + k log n) due to sorting + heap ops. Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Efficient: each project pushed/popped at most once.
  • Sorting + heap operations are standard pattern for “choose best affordable item repeatedly.”

Interview Framing इंटरव्यू फ्रेमिंग

“This is a repeated 'pick-best-affordable' greedy problem. Brute force tries all choices (exponential). Sort projects by capital and use a max-heap for profits: in each round add all newly affordable projects to the profit heap and pop the best profit. Repeat k times. This yields O(n log n + k log n).” “यह बार-बार 'सर्वश्रेष्ठ-किफायती' ग्रीडी समस्या है। ब्रूट फोर्स सभी चॉइस (एक्सपोनेंशियल)। प्रोजेक्ट्स को पूंजी से सॉर्ट करें और प्रॉफिट्स के लिए मैक्स-हीप: प्रत्येक राउंड में नए किफायती प्रोजेक्ट्स को प्रॉफिट हीप में डालें और सर्वश्रेष्ठ प्रॉफिट निकालें। k बार दोहराएँ। O(n log n + k log n)।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Clarify input sizes (n, k) and that projects are independent. Show brute force (exponential) or naive O(k·n) scanning. Present efficient plan: sort by capital, maintain profit max-heap for affordable ones, repeat k times. State complexities and memory. Example run and edge cases (no affordable projects early). इनपुट साइज (n, k) और प्रोजेक्ट्स स्वतंत्र। ब्रूट फोर्स (एक्सपोनेंशियल) या नाइव O(k·n) स्कैनिंग। कुशल प्लान: पूंजी से सॉर्ट, किफायती के लिए प्रॉफिट मैक्स-हीप, k बार दोहराएँ। कॉम्प्लेक्सिटी और मेमोरी। उदाहरण रन और एज केस (शुरुआत में कोई किफायती प्रोजेक्ट नहीं)।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“Sort projects by required capital. Maintain a max-heap of profits of currently affordable projects (those with required capital ≤ current W). For up to k rounds: move newly affordable projects into the heap, pop the highest profit and add to W. If heap empty, stop. This is O(n log n + k log n) and quickly selects the best sequence of projects to maximize final capital.” “प्रोजेक्ट्स को जरूरी पूंजी से सॉर्ट करें। वर्तमान किफायती प्रोजेक्ट्स के प्रॉफिट्स का मैक्स-हीप (पूंजी ≤ W)। k राउंड तक: नए किफायती प्रोजेक्ट्स को हीप में डालें, सबसे ज्यादा प्रॉफिट निकालें और W में जोड़ें। अगर हीप खाली, रुकें। O(n log n + k log n), सर्वश्रेष्ठ प्रोजेक्ट्स अनुक्रम।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate constraints and ask about ranges (n, k).
  • Mention brute/naive scanning O(k·n).
  • Present pattern: sort by capital + profit max-heap.
  • Complexity: O(n log n + k log n).
  • Run a quick example and mention early-stop when no affordable projects.

Longest Increasing Path in a Matrix (LC 329) – LeetCode मैट्रिक्स में सबसे लंबा बढ़ता पथ (LC 329) – लीटकोड

Problem: Given an m x n integer matrix, return the length of the longest increasing path (strictly increasing) in the matrix. You may move up/down/left/right. समस्या: m x n इंटीजर मैट्रिक्स में, सबसे लंबा सख्ती से बढ़ता पथ रिटर्न करें। ऊपर/नीचे/बाएँ/दाएँ जा सकते हैं।

Pattern Tags पैटर्न टैग्स

  • Primary: DFS + Memoization (DP on DAG)
  • Secondary: Topological ordering (graph view), DP
  • Frequency: Medium-high (DFS + memo pattern)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: O(m·n) time with memoization (each cell computed once), O(m·n) space for memo & recursion stack.
  • Edge: All equal values → 1, single cell → 1.
  • Self: Use DFS from each cell with memo to avoid exponential repeats.

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Strictly increasing? m,n ranges?" Quick heuristic: "Longest path in grid? DFS + memo." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "सख्ती से बढ़ता? m,n रेंज?" क्विक ह्यूरिस्टिक: "ग्रिड में सबसे लंबा पथ? DFS + मेमो।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“longest increasing path” Strictly increasing adjacency moves DFS + memoization Treat each cell as node in DAG, compute longest out-path
“move in 4 directions” Grid neighbors only DFS with memo or topological DP Use memo to store best length starting at cell
“matrix sizes” m·n complexity Avoid recomputation (memo) Each cell processed once with memo

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force DFS from each cell without memo → exponential due to overlapping subproblems.
  • Alternative Topological sort by treating edges from lower→higher and do DP on DAG (requires building graph and indegree), but heavier to implement.
  • Optimal DFS with memo: for each cell, recursively compute the length of the longest increasing path starting at that cell by exploring neighbors > current. Store in memo and reuse.

Non-Optimized Solution (DFS naive, no memo) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (DFS नाइव, बिना मेमो)

Javascript 
// Naive DFS without memoization
function longestIncreasingPathNaive(matrix) {
  const m = matrix.length;
  const n = matrix[0].length;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  function dfs(i,j,prev) {
    if (i < 0 || i >= m || j < 0 || j >= n || matrix[i][j] <= prev) return 0;
    let maxLen = 0;
    for (const [di,dj] of dirs) {
      maxLen = Math.max(maxLen, dfs(i+di, j+dj, matrix[i][j]));
    }
    return 1 + maxLen;
  }
  let ans = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      ans = Math.max(ans, dfs(i, j, -Infinity));
    }
  }
  return ans;
}
// Time: exponential, due to repeated work
Why This Solution? यह सॉल्यूशन क्यों?
  • Conceptually simple but repeats subproblems excessively.

Optimized Solution (DFS + Memoization) ऑप्टिमाइज्ड सॉल्यूशन (DFS + मेमोइजेशन)

Javascript 
// DFS + Memoization
function longestIncreasingPath(matrix) {
  const m = matrix.length;
  const n = matrix[0].length;
  const memo = Array.from({length: m}, () => Array(n).fill(0));
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  
  function dfs(i, j) {
    if (memo[i][j] !== 0) return memo[i][j];
    let best = 1;
    for (const [di, dj] of dirs) {
      const ni = i + di, nj = j + dj;
      if (ni >= 0 && ni < m && nj >= 0 && nj < n && matrix[ni][nj] > matrix[i][j]) {
        best = Math.max(best, 1 + dfs(ni, nj));
      }
    }
    memo[i][j] = best;
    return best;
  }

  let ans = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      ans = Math.max(ans, dfs(i, j));
    }
  }
  return ans;
}
// Time: O(m*n) with memo, Space: O(m*n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Each cell computed once; recursion explores at most 4 neighbors.
  • Memo converts exponential DFS into linear DP.

Interview Framing इंटरव्यू फ्रेमिंग

“Brute force DFS repeats many overlapping subproblems. Use DFS with memoization: compute longest path starting at each cell and memoize. This results in O(m·n) time overall.” “ब्रूट फोर्स DFS कई ओवरलैपिंग सबप्रॉब्लम्स। DFS + मेमोइजेशन: प्रत्येक सेल से सबसे लंबा पथ और मेमो। O(m·n) समय।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Restate moves allowed and strict increasing requirement. Brute DFS is exponential due to repeated states. Use memo: dfs(i,j) returns longest path starting at (i,j), store result to avoid recomputation. Complexity O(m·n), space O(m·n). Mention iterative/topological alternative if recursion depth is a concern. चलने की अनुमति और सख्त बढ़ता नियम। ब्रूट DFS एक्सपोनेंशियल, बार-बार स्टेट्स। मेमो: dfs(i,j) से (i,j) से सबसे लंबा पथ, रीकम्प्यूटेशन से बचें। O(m·n) समय, O(m·n) स्पेस। रिकर्शन डेप्थ के लिए इटेरेटिव/टॉपोलॉजिकल ऑप्शन।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“Treat every cell as a node in a directed DAG where edges go from a cell to its strictly larger neighbors. A naive DFS from each cell repeats work exponentially. With memoization, dfs(i,j) computes and caches the longest increasing path starting there by exploring up to 4 neighbors; each cell is computed once giving O(m·n) time. This is the standard DFS+memo approach for grid DP problems.” “प्रत्येक सेल को DAG नोड, जहां एज छोटे से बड़े पड़ोसी को। नाइव DFS एक्सपोनेंशियल। मेमोइजेशन: dfs(i,j) सबसे लंबा बढ़ता पथ कैश, 4 पड़ोसियों तक। प्रत्येक सेल एक बार, O(m·n) समय। ग्रिड DP के लिए स्टैंडर्ड DFS+मेमो।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate grid rules (4-direction, strict increase).
  • Mention brute DFS and repeated work.
  • Present DFS + memoization as optimal (or topological DP).
  • Complexity: O(m·n) time, O(m·n) space.
  • Quick dry-run and note recursion depth / iterative alternative.

Course Schedule II (LC 210) – LeetCode कोर्स शेड्यूल II (LC 210) – लीटकोड

Problem: Given numCourses and prerequisites list of pairs [a,b] (to take course a you must have taken b), return a possible order to finish all courses or [] if impossible. समस्या: numCourses और प्रीरेक्जिट्स की लिस्ट [a,b] (कोर्स a के लिए b पहले), सभी कोर्सेज का संभावित क्रम या [] अगर असंभव।

Pattern Tags पैटर्न टैग्स

  • Primary: Graph, Topological Sort (Kahn’s algorithm)
  • Secondary: DFS-based topological sort (post-order)
  • Frequency: High (classic topo / cycle detection)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: O(V + E) time, O(V + E) space.
  • Edge: Cycle → return []; multiple valid orders possible.
  • Self: numCourses=2, prerequisites=[[1,0]] → [0,1].

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Cycle possible? numCourses range?" Quick heuristic: "Course ordering? Topological sort." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "साइकिल संभव? numCourses रेंज?" क्विक ह्यूरिस्टिक: "कोर्स ऑर्डरिंग? टॉपोलॉजिकल सॉर्ट।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“order to finish all courses” Topological ordering of DAG Kahn’s BFS or DFS postorder Use indegree (Kahn) or DFS stack (postorder)
“if impossible” Detect cycles If topo order size < V → cycle Return empty array
“pairs [a,b]” directed edges b → a Build adjacency + indegree Process nodes with zero indegree

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Try all permutations and check prerequisites — O(n!) — impossible for large n.
  • Alternative DFS post-order topological sort with cycle detection (coloring).
  • Optimal Kahn’s algorithm: build indegree array and adjacency list; push all indegree=0 nodes into queue, pop and reduce neighbors’ indegree; record order. If recorded count < numCourses → cycle.

Non-Optimized Solution (DFS naive without cycle detection clarity) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (DFS नाइव बिना साइकिल डिटेक्शन)

Javascript 
// Naive DFS without cycle detection clarity
function findOrderNaive(numCourses, prerequisites) {
  const adj = Array.from({length: numCourses}, () => []);
  for (const [a,b] of prerequisites) adj[b].push(a);

  const visited = new Array(numCourses).fill(false);
  const order = [];

  function dfs(u) {
    visited[u] = true;
    for (const v of adj[u]) {
      if (!visited[v]) dfs(v);
    }
    order.push(u);
  }

  for (let i = 0; i < numCourses; i++) {
    if (!visited[i]) dfs(i);
  }
  return order.reverse(); // may be invalid if cycle exists
}
// Time: O(V + E), Space: O(V + E)
Why This Solution? यह सॉल्यूशन क्यों?
  • Demonstrates post-order idea but lacks cycle detection; not safe.

Optimized Solution (Kahn’s BFS Topo Sort) ऑप्टिमाइज्ड सॉल्यूशन (काह्न्स BFS टॉपो सॉर्ट)

Javascript 
// Kahn’s BFS Topological Sort
function findOrder(numCourses, prerequisites) {
  const adj = Array.from({length: numCourses}, () => []);
  const indegree = new Array(numCourses).fill(0);
  for (const [a,b] of prerequisites) {
    adj[b].push(a);
    indegree[a]++;
  }

  const queue = [];
  for (let i = 0; i < numCourses; i++) if (indegree[i] === 0) queue.push(i);

  const order = [];
  while (queue.length) {
    const u = queue.shift();
    order.push(u);
    for (const v of adj[u]) {
      indegree[v]--;
      if (indegree[v] === 0) queue.push(v);
    }
  }

  return order.length === numCourses ? order : [];
}
// Time: O(V + E), Space: O(V + E)
Why This Solution? यह सॉल्यूशन क्यों?
  • Kahn’s algorithm cleanly detects cycles (if order size smaller than numCourses) and produces a valid order if exists.

Interview Framing इंटरव्यू फ्रेमिंग

“Brute force tries permutations. Standard solution is topological sort. Kahn’s BFS uses indegree counts and queue of zero-indegree nodes. Alternatively DFS post-order with cycle detection works as well.” “ब्रूट फोर्स परम्यूटेशन्स। स्टैंडर्ड सॉल्यूशन टॉपोलॉजिकल सॉर्ट। काह्न्स BFS इंडिग्री काउंट्स और जीरो-इंडिग्री क्यू। वैकल्पिक DFS पोस्ट-ऑर्डर साइकिल डिटेक्शन।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Clarify that problem asks for a topological order. Describe building adjacency list and indegree. Explain Kahn’s algorithm (queue of zero indegree, pop, reduce neighbors). Complexity O(V+E). Mention cycle detection (order length check). समस्या टॉपोलॉजिकल ऑर्डर। एडजसेंसी लिस्ट और इंडिग्री। काह्न्स एल्गोरिदम (जीरो इंडिग्री क्यू, पॉप, पड़ोसियों की कमी)। O(V+E)। साइकिल डिटेक्शन (ऑर्डर लेंथ चेक)।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“Build directed graph from prerequisites and compute indegree for each node. Use Kahn’s topological sort: initialize queue with nodes of indegree 0, then repeatedly pop node, append to result, and decrement indegree of neighbors, enqueueing any that drop to 0. If final order contains all courses return it; otherwise return [] (cycle). Runs in O(V+E).” “प्रीरेक्जिट्स से डायरेक्टेड ग्राफ और प्रत्येक नोड के लिए इंडिग्री। काह्न्स टॉपोलॉजिकल सॉर्ट: जीरो इंडिग्री नोड्स से क्यू, नोड पॉप, रिजल्ट में, पड़ोसियों की इंडिग्री कम करें, 0 पर क्यू। अगर ऑर्डर में सभी कोर्स, रिटर्न; वरना [] (साइकिल)। O(V+E)।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate as topological ordering / cycle detection.
  • Brute is permutations O(n!).
  • Present Kahn’s algorithm or DFS post-order with coloring.
  • Complexity: O(V+E).
  • Example and cycle detection note.

Is Graph Bipartite? (LC 785) – LeetCode क्या ग्राफ बाइपार्टाइट है? (LC 785) – लीटकोड

Problem: Given an undirected graph as adjacency list graph, return true if and only if it is bipartite (nodes can be colored with 2 colors such that no edge has same-colored endpoints). समस्या: अनडायरेक्टेड ग्राफ (एडजसेंसी लिस्ट), ट्रू रिटर्न करें अगर ग्राफ बाइपार्टाइट (2 रंगों से नोड्स रंग सकते हैं, कोई एज समान रंग नहीं)।

Pattern Tags पैटर्न टैग्स

  • Primary: Graph, BFS/DFS coloring
  • Secondary: Two-coloring, Union-Find (alternative)
  • Frequency: Medium (graph coloring basics)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: O(V + E) time, O(V) space for color array or queue.
  • Edge: Graph may be disconnected — must process each component.
  • Self: graph = [[1,3],[0,2],[1,3],[0,2]] → true (two-colorable).

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Disconnected components? Graph size?" Quick heuristic: "Bipartite? Try two-coloring via BFS/DFS." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "डिस्कनेक्टेड कंपोनेंट्स? ग्राफ साइज?" क्विक ह्यूरिस्टिक: "बाइपार्टाइट? BFS/DFS से टू-कलरिंग।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“bipartite” Two-coloring of graph nodes BFS/DFS coloring Color neighbor with opposite color, detect conflicts
“graph as adjacency list” Check disconnected components Loop components Init uncolored nodes and traverse each comp
“no edge between same color” Immediate conflict detection Return false on conflict Use queue/bfs to propagate colors

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Try to assign colors with backtracking across nodes — exponential in worst-case.
  • Alternative Union-Find approach: for each edge (u,v), union u with complement of v; detect conflict if u and v are in same set — trickier.
  • Optimal BFS (or DFS) coloring: For each unvisited node, color it 0 and BFS; for neighbor, if uncolored assign opposite color; if colored same → not bipartite.

Non-Optimized Solution (Backtracking coloring — illustrative) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (बैकट्रैकिंग कलरिंग — उदाहरण)

Javascript 
// Backtracking coloring (illustrative)
function isBipartiteBacktrack(graph) {
  const n = graph.length;
  const color = new Array(n).fill(null);

  function dfs(node, c) {
    color[node] = c;
    for (const nei of graph[node]) {
      if (color[nei] === null) {
        if (!dfs(nei, 1 - c)) return false;
      } else if (color[nei] === c) return false;
    }
    return true;
  }

  for (let i = 0; i < n; i++) {
    if (color[i] === null) {
      if (!dfs(i, 0)) return false;
    }
  }
  return true;
}
// Time: O(V + E), Space: O(V)
Why This Solution? यह सॉल्यूशन क्यों?
  • Correct but recursive/backtracking style; effectively same as DFS coloring with cycle detection.

Optimized Solution (BFS Coloring) ऑप्टिमाइज्ड सॉल्यूशन (BFS कलरिंग)

Javascript 
// BFS Coloring
function isBipartite(graph) {
  const n = graph.length;
  const color = new Array(n).fill(-1); // -1 uncolored, 0/1 colored

  for (let i = 0; i < n; i++) {
    if (color[i] !== -1) continue;
    // start BFS
    const queue = [i];
    color[i] = 0;
    while (queue.length) {
      const u = queue.shift();
      for (const v of graph[u]) {
        if (color[v] === -1) {
          color[v] = 1 - color[u];
          queue.push(v);
        } else if (color[v] === color[u]) {
          return false;
        }
      }
    }
  }
  return true;
}
// Time: O(V + E), Space: O(V)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple BFS/DFS coloring with conflict detection.
  • Handles disconnected graphs by iterating all nodes.

Interview Framing इंटरव्यू फ्रेमिंग

“Color the graph using two colors via BFS or DFS. For each component start uncolored node and color it 0, then color neighbors opposite. If you ever find adjacent nodes with same color, graph is not bipartite.” “ग्राफ को दो रंगों से BFS या DFS से रंगें। प्रत्येक कंपोनेंट के लिए अनकलर्ड नोड से शुरू, 0 रंग, फिर पड़ोसियों को उल्टा। अगर एकसमान रंग के पड़ोसी, ग्राफ बाइपार्टाइट नहीं।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Clarify graph input shape and disconnected components. Brute/backtracking mention. Present BFS coloring; show how colors propagate and conflict detection stops early. Complexity O(V + E). Example small graph and disconnected case. ग्राफ इनपुट आकार और डिस्कनेक्टेड कंपोनेंट्स। ब्रूट/बैकट्रैकिंग उल्लेख। BFS कलरिंग; रंग कैसे फैलते हैं और कॉन्फ्लिक्ट डिटेक्शन। O(V + E)। छोटा ग्राफ और डिस्कनेक्टेड केस उदाहरण।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“Check two-colorability by BFS/DFS coloring. Iterate through nodes; for any unvisited node assign color 0 and BFS: assign every neighbor the opposite color. If at any point a neighbor has same color, return false. Iterate all components. This runs in O(V + E) time and detects conflicts early.” “BFS/DFS कलरिंग से टू-कलरेबिलिटी। नोड्स पर लूप; अनविजिटेड नोड को 0 रंग और BFS: प्रत्येक पड़ोसी को उल्टा रंग। अगर पड़ोसी का रंग समान, फॉल्स। सभी कंपोनेंट्स। O(V + E) समय, जल्दी कॉन्फ्लिक्ट डिटेक्शन।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate: is graph two-colorable? Note adjacency representation.
  • Brute backtracking idea (exponential).
  • Optimal: BFS/DFS coloring or Union-Find alternative.
  • Complexity: O(V + E).
  • Example & disconnected graphs note.

Course Schedule (LC 207) – LeetCode कोर्स शेड्यूल (LC 207) – लीटकोड

Problem: Given numCourses and prerequisites list pairs [a,b] (to take a you must take b), return true if you can finish all courses (i.e., graph is acyclic), otherwise false. समस्या: numCourses और प्रीरेक्जिट्स लिस्ट पेयर्स [a,b] (a के लिए b पहले), ट्रू रिटर्न करें अगर सभी कोर्सेज पूरे हो सकते हैं (ग्राफ एसाइक्लिक), वरना फॉल्स।

Pattern Tags पैटर्न टैग्स

  • Primary: Graph, Cycle Detection, Topological Sort
  • Secondary: DFS coloring, Kahn’s algorithm
  • Frequency: Very common (graph basics)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: O(V + E) time, O(V + E) space.
  • Edge: Disconnected graph; zero prerequisites (true).
  • Self: numCourses=2, prerequisites=[[1,0]] → true.

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Cycle possible? numCourses range?" Quick heuristic: "Check course feasibility? Cycle detection." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "साइकिल संभव? numCourses रेंज?" क्विक ह्यूरिस्टिक: "कोर्स फीजिबिलिटी? साइकिल डिटेक्शन।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“can finish all courses” Need to detect cycle Topological / cycle detect If cycle exists → false, else true
“prerequisites pairs” Directed edges b → a Build adjacency and indegree Use Kahn (BFS) or DFS coloring
“return boolean” Only feasibility required Early exit on cycle detect No need to return ordering (LC210 did)

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Try all permutations of courses and check prerequisites → O(n!) — infeasible.
  • Alternative DFS with recursion stack detection (path-based) — works and simple.
  • Optimal Either Kahn’s BFS (indegree queue) or DFS with 3-color marking (white/gray/black). Both are O(V+E). Here I present DFS color method as optimized.

Non-Optimized Solution (DFS with recursion-stack detection) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (DFS रिकर्शन-स्टैक डिटेक्शन)

Javascript 
// Non-optimized but clear: recursion stack check for cycle
function canFinishBrute(numCourses, prerequisites) {
  const adj = Array.from({length: numCourses}, () => []);
  for (const [a,b] of prerequisites) adj[b].push(a);

  const visiting = new Set(); // nodes in current recursion stack
  const visited = new Set();

  function dfs(u) {
    if (visiting.has(u)) return false; // cycle
    if (visited.has(u)) return true;

    visiting.add(u);
    for (const v of adj[u]) {
      if (!dfs(v)) return false;
    }
    visiting.delete(u);
    visited.add(u);
    return true;
  }

  for (let i = 0; i < numCourses; i++) {
    if (!visited.has(i)) {
      if (!dfs(i)) return false;
    }
  }
  return true;
}
// Time: O(V + E), but recursion-stack bookkeeping is explicit; fine for interviews.
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple explicit recursion-stack cycle detection. Works well but uses Sets and recursion; DFS-color is slightly cleaner.

Optimized Solution (DFS with 3-color marking) ऑप्टिमाइज्ड सॉल्यूशन (DFS 3-कलर मार्किंग)

Javascript 
// Optimized: DFS coloring (0 = unvisited, 1 = visiting, 2 = visited)
function canFinish(numCourses, prerequisites) {
  const adj = Array.from({length: numCourses}, () => []);
  for (const [a,b] of prerequisites) adj[b].push(a);

  const color = new Array(numCourses).fill(0);
  function dfs(u) {
    if (color[u] === 1) return false; // back edge => cycle
    if (color[u] === 2) return true;  // already processed
    color[u] = 1; // visiting
    for (const v of adj[u]) {
      if (!dfs(v)) return false;
    }
    color[u] = 2; // done
    return true;
  }

  for (let i = 0; i < numCourses; i++) {
    if (color[i] === 0) {
      if (!dfs(i)) return false;
    }
  }
  return true;
}
// Time: O(V + E), Space: O(V + E) recursion stack
Why This Solution? यह सॉल्यूशन क्यों?
  • 3-color is standard and concise for cycle detection; straightforward to explain.

Interview Framing इंटरव्यू फ्रेमिंग

“This is cycle detection in a directed graph. Brute permutations are infeasible. Use DFS coloring or Kahn’s indegree approach. If a back-edge is found, you have a cycle → cannot finish.” “यह डायरेक्टेड ग्राफ में साइकिल डिटेक्शन है। ब्रूट परम्यूटेशन्स अनुपयुक्त। DFS कलरिंग या काह्न्स इंडिग्री अप्रोच। बैक-एज मिले तो साइकिल → पूरा नहीं हो सकता।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Clarify graph is directed and we need to detect cycles. Mention brute-force permutations (and discard). Present DFS 3-coloring: visiting nodes marked '1', visited '2'; encountering a '1' is a cycle. Complexity O(V+E). Edge cases: no prerequisites → true; disconnected components handled by looping all nodes. ग्राफ डायरेक्टेड और साइकिल डिटेक्शन जरूरी। ब्रूट-फोर्स परम्यूटेशन्स (त्यागें)। DFS 3-कलरिंग: विजिटिंग नोड्स '1', विजिटेड '2'; '1' मिलना साइकिल। O(V+E)। एज केस: कोई प्रीरेक्जिट्स → ट्रू; डिस्कनेक्टेड कंपोनेंट्स लूप से।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“Model courses as nodes and prerequisites as directed edges. To check feasibility, detect a directed cycle. I use DFS 3-coloring: unvisited (0), visiting (1), visited (2). For each node, DFS; if we reach a node marked visiting, we found a cycle and return false. If no cycle, return true. This runs in O(V+E).” “कोर्सेज को नोड्स और प्रीरेक्जिट्स को डायरेक्टेड एज। फीजिबिलिटी के लिए डायरेक्टेड साइकिल डिटेक्शन। DFS 3-कलरिंग: अनविजिटेड (0), विजिटिंग (1), विजिटेड (2)। प्रत्येक नोड के लिए DFS; विजिटिंग नोड मिले तो साइकिल, फॉल्स। कोई साइकिल नहीं तो ट्रू। O(V+E)।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate problem → find cycle in directed graph.
  • Brute mention (permutations) and why infeasible.
  • Present DFS color or Kahn’s topo as optimal.
  • State complexity O(V+E).
  • Quick example + disconnected components note.

Network Delay Time (LC 743) – LeetCode नेटवर्क डिले टाइम (LC 743) – लीटकोड

Problem: Given times as [u,v,w] directed edges with travel time w, n nodes, and starting node k, return the time it takes for all nodes to receive the signal; return -1 if some node is unreachable. समस्या: times [u,v,w] डायरेक्टेड एज ट्रैवल टाइम w, n नोड्स, और स्टार्टिंग नोड k, सभी नोड्स तक सिग्नल पहुंचने का समय रिटर्न करें; -1 अगर कोई नोड अनरिचेबल।

Pattern Tags पैटर्न टैग्स

  • Primary: Single-source shortest path, Dijkstra’s algorithm
  • Secondary: Priority queue (min-heap), Graph adjacency list
  • Frequency: Medium (Dijkstra classic)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: O(E log V) with binary heap, O(V^2) for naive Dijkstra without heap.
  • Edge: Negative weights? Problem guarantees non-negative weights (Dijkstra OK). Unreachable nodes → return -1.
  • Self: times=[[2,1,1],[2,3,1],[3,4,1]], n=4, k=2 → answer 2.

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Non-negative weights? n range?" Quick heuristic: "Shortest paths from k? Dijkstra." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "नॉन-नेगेटिव वेट्स? n रेंज?" क्विक ह्यूरिस्टिक: "k से शॉर्टेस्ट पाथ्स? डिज्क्स्ट्रा।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“time for all nodes” Shortest path from k to every node Dijkstra (non-negative) Compute max distance among shortest paths
“return -1 if unreachable” Need full reachability check Distances + check After Dijkstra, check any distance === inf
“times as edges” Weighted directed graph Use adjacency list Use min-heap to extract next shortest node

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Use Bellman-Ford (O(VE)) or repeated relaxation naive approach — works but slower.
  • Alternative Use BFS if all weights are equal (unit weights) or use Dijkstra for positive weights. Bellman-Ford needed only for negative weights (not the case here).
  • Optimal Dijkstra’s algorithm with min-heap (priority queue) from source k, track distances. After algorithm finished, compute maximum of distances; if any unreachable (Infinity) return -1.

Non-Optimized Solution (Dijkstra without heap) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (डिज्क्स्ट्रा बिना हीप)

Javascript 
// Non-optimized Dijkstra without heap
function networkDelayTimeSimple(times, n, k) {
  const adj = Array.from({length: n + 1}, () => []);
  for (const [u,v,w] of times) adj[u].push([v,w]);

  const dist = Array(n + 1).fill(Infinity);
  const visited = Array(n + 1).fill(false);
  dist[k] = 0;

  for (let i = 1; i <= n; i++) {
    // pick unvisited node with smallest dist
    let u = -1, minD = Infinity;
    for (let v = 1; v <= n; v++) {
      if (!visited[v] && dist[v] < minD) { minD = dist[v]; u = v; }
    }
    if (u === -1) break;
    visited[u] = true;
    for (const [v,w] of adj[u]) {
      if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
    }
  }

  const ans = Math.max(...dist.slice(1));
  return ans === Infinity ? -1 : ans;
}
// Time: O(V^2 + E) ~ O(V^2)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simpler to code but O(V^2) can be slow for large graphs.

Optimized Solution (Dijkstra + Min-Heap) ऑप्टिमाइज्ड सॉल्यूशन (डिज्क्स्ट्रा + मिन-हीप)

Javascript 
// Simple min-heap implemented via comparator
class MinHeap {
  constructor() { this.data = []; }
  size(){ return this.data.length; }
  push(val){ this.data.push(val); this._siftUp(); }
  pop(){ if (!this.data.length) return undefined; const top = this.data[0]; const last = this.data.pop(); if (this.data.length) { this.data[0] = last; this._siftDown(); } return top; }
  _siftUp(){ let i = this.data.length - 1; while (i > 0) { const p = Math.floor((i-1)/2); if (this.data[i][0] < this.data[p][0]) { [this.data[i], this.data[p]] = [this.data[p], this.data[i]]; i = p; } else break; } }
  _siftDown(){ let i = 0; const n = this.data.length; while (true) { let l = 2*i+1, r = 2*i+2, smallest = i; if (l < n && this.data[l][0] < this.data[smallest][0]) smallest = l; if (r < n && this.data[r][0] < this.data[smallest][0]) smallest = r; if (smallest !== i) { [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]]; i = smallest } else break; } }
}

function networkDelayTime(times, n, k) {
  const adj = Array.from({length: n + 1}, () => []);
  for (const [u,v,w] of times) adj[u].push([v,w]);

  const dist = Array(n + 1).fill(Infinity);
  dist[k] = 0;
  const heap = new MinHeap();
  heap.push([0, k]); // [distance, node]

  while (heap.size()) {
    const [d,u] = heap.pop();
    if (d > dist[u]) continue; // stale entry
    for (const [v,w] of adj[u]) {
      if (d + w < dist[v]) {
        dist[v] = d + w;
        heap.push([dist[v], v]);
      }
    }
  }

  const ans = Math.max(...dist.slice(1));
  return ans === Infinity ? -1 : ans;
}
// Time: O(E log V), Space: O(V + E)
Why This Solution? यह सॉल्यूशन क्यों?
  • Dijkstra with heap processes each edge with heap operations giving O(E log V).
  • Handles typical constraints for this LC problem.

Interview Framing इंटरव्यू फ्रेमिंग

“This is single-source shortest path with non-negative weights → Dijkstra with a min-heap fits. After computing shortest distances from k, return the maximum distance (or -1 if any node unreachable).” “यह सिंगल-सोर्स शॉर्टेस्ट पाथ नॉन-नेगेटिव वेट्स → डिज्क्स्ट्रा मिन-हीप। k से शॉर्टेस्ट डिस्टेंस के बाद, अधिकतम डिस्टेंस (-1 अगर कोई नोड अनरिचेबल)।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Clarify weights are non-negative (Dijkstra OK). Build adjacency list, run Dijkstra from k, maintain dist[] initialized to Infinity. Use min-heap to efficiently get next closest node, relax edges. After algorithm, if any dist is Infinity → return -1, else return max(dist). Complexity O(E log V). वेट्स नॉन-नेगेटिव (डिज्क्स्ट्रा ठीक)। एडजसेंसी लिस्ट, k से डिज्क्स्ट्रा, dist[] को इनफिनिटी से इनिशियलाइज। मिन-हीप से अगला नजदीकी नोड, रिलैक्स एज। अगर कोई dist इनफिनिटी → -1, वरना max(dist)। O(E log V)।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“Model as directed weighted graph and run Dijkstra from node k. Build adjacency list, use a min-heap keyed by tentative distance, relax edges and update distances. At the end, return the maximum distance across nodes (or -1 if some unreachable). This runs in O(E log V).” “डायरेक्टेड वेटेड ग्राफ और k से डिज्क्स्ट्रा। एडजसेंसी लिस्ट, मिन-हीप टेंटेटिव डिस्टेंस, रिलैक्स एज और अपडेट डिस्टेंस। अंत में, नोड्स में अधिकतम डिस्टेंस (-1 अगर अनरिचेबल)। O(E log V)।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate graph type and weight sign (non-negative?).
  • Mention naive O(V^2) Dijkstra vs heap-based.
  • Present adjacency build + heap Dijkstra.
  • Complexity O(E log V).
  • Example and unreachable check.

Redundant Connection (LC 684) – LeetCode रिडंडेंट कनेक्शन (LC 684) – लीटकोड

Problem: Given a list of edges that form a graph of n nodes with one extra edge that creates a cycle, return the edge that, if removed, leaves a tree (i.e., the redundant edge). Edges are undirected. Return the last such edge in input order that creates a cycle. समस्या: n नोड्स का ग्राफ बनाने वाली एज लिस्ट, एक अतिरिक्त एज जो साइकिल बनाती है, वह एज रिटर्न करें जो हटाने पर ट्री बनाए (रिडंडेंट एज)। एज अनडायरेक्टेड। इनपुट ऑर्डर में आखिरी साइकिल बनाने वाली एज रिटर्न करें।

Pattern Tags पैटर्न टैग्स

  • Primary: Union-Find (Disjoint Set Union)
  • Secondary: Cycle detection in undirected graph
  • Frequency: Medium (DSU classic)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: O(E α(N)) ≈ O(E) with path compression & union by rank.
  • Edge: Return the edge that completes a cycle (last in input order if multiple).
  • Self: edges = [[1,2],[1,3],[2,3]] → return [2,3].

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Undirected graph? Nodes 1..n?" Quick heuristic: "Cycle in undirected graph? Union-Find." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "अनडायरेक्टेड ग्राफ? नोड्स 1..n?" क्विक ह्यूरिस्टिक: "अनडायरेक्टेड ग्राफ में साइकिल? यूनियन-फाइंड।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“one extra edge creates a cycle” Undirected graph cycle detection Union-Find Union endpoints, if already connected => redundant
“return that edge” Input order matters Iterate edges in order Return first edge (when iterating) that connects already-connected nodes
“nodes labeled 1..n” DSU indexes easily Path compression helpful Maintain parent and rank arrays

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force For each edge, build graph without that edge and check if it's a tree (i.e., no cycles & connected) — O(E*(V+E)) — slow.
  • Alternative Use DFS cycle detection after adding edges incrementally: check whether u and v already connected using DFS/BFS per edge (costly).
  • Optimal Union-Find: iterate edges, for each (u,v) check if find(u) === find(v); if yes, return edge; else union(u,v). Use path compression + union by rank.

Non-Optimized Solution (Incremental DFS connectivity check) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (इन्क्रीमेंटल DFS कनेक्टिविटी चेक)

Javascript 
// Slow: for each edge, check connectivity by DFS
function findRedundantConnectionBrute(edges) {
  const n = edges.length;
  for (let i = 0; i < n; i++) {
    // build graph with edges[0..i-1]
    const adj = {};
    for (let j = 0; j < i; j++) {
      const [u,v] = edges[j];
      adj[u] = adj[u] || [];
      adj[v] = adj[v] || [];
      adj[u].push(v); adj[v].push(u);
    }
    const [u,v] = edges[i];
    // check if u can reach v
    const seen = new Set(), stack = [u], found = false;
    while (stack.length) {
      const cur = stack.pop();
      if (cur === v) { found = true; break; }
      if (seen.has(cur)) continue;
      seen.add(cur);
      for (const nei of (adj[cur] || [])) if (!seen.has(nei)) stack.push(nei);
    }
    if (found) return edges[i]; // this edge closes a cycle
  }
  return [];
}
// Time: O(E*V)
Why This Solution? यह सॉल्यूशन क्यों?
  • Easy to reason about but expensive (repeat DFS many times).

Optimized Solution (Union-Find with path compression & union by rank) ऑप्टिमाइज्ड सॉल्यूशन (यूनियन-फाइंड पाथ कम्प्रेशन & यूनियन बाय रैंक)

Javascript 
class UnionFind {
  constructor(n) {
    this.parent = Array(n + 1).fill(0).map((_, i) => i);
    this.rank = Array(n + 1).fill(0);
  }
  find(x) {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }
  union(x, y) {
    const rx = this.find(x), ry = this.find(y);
    if (rx === ry) return false;
    if (this.rank[rx] > this.rank[ry]) this.parent[ry] = rx;
    else if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
    else { this.parent[ry] = rx; this.rank[rx]++; }
    return true;
  }
}

function findRedundantConnection(edges) {
  const n = edges.length;
  const uf = new UnionFind(n);
  for (const [u,v] of edges) {
    if (!uf.union(u, v)) return [u, v]; // union failed => cycle
  }
  return [];
}
// Time: ~O(E α(N)), Space: O(N)
Why This Solution? यह सॉल्यूशन क्यों?
  • Union-Find directly detects a cycle when trying to union two already-connected nodes. Fast and canonical.

Interview Framing इंटरव्यू फ्रेमिंग

“Add edges one by one and use DSU to track connectivity. If an edge connects two nodes already in the same set, it forms a cycle and is the redundant edge. Union-Find with path compression is the standard solution.” “एज एक-एक करके जोड़ें और DSU से कनेक्टिविटी ट्रैक करें। अगर एज दो पहले से कनेक्टेड नोड्स जोड़े, यह साइकिल बनाए और रिडंडेंट है। पाथ कम्प्रेशन के साथ यूनियन-फाइंड स्टैंडर्ड सॉल्यूशन।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

State that adding edges until a cycle appears suggests DSU. Show union-find operations: find with path compression and union by rank. Iterate edges in order: if find(u) === find(v) return edge. Complexity near-linear. Mention brute-force DFS approach and why it's slower. साइकिल आने तक एज जोड़ना DSU सुझाता है। यूनियन-फाइंड ऑपरेशन्स: पाथ कम्प्रेशन और रैंक। एज ऑर्डर में: अगर find(u) === find(v), एज रिटर्न। नियर-लिनियर। ब्रूट-फोर्स DFS और धीमा होने का कारण।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“Iterate edges and maintain a disjoint-set union structure. For each edge (u,v), if find(u) equals find(v), this edge closes a cycle — return it. Otherwise union the sets. With path compression/union-by-rank this runs in near-linear time O(E α(N)).” “एज पर लूप और डिसजॉइंट-सेट यूनियन स्ट्रक्चर। प्रत्येक एज (u,v) के लिए, अगर find(u) = find(v), यह साइकिल बंद करता है — रिटर्न। वरना सेट्स यूनियन। पाथ कम्प्रेशन/रैंक से नियर-लिनियर O(E α(N))।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate: edge list, undirected, find edge that creates cycle.
  • Brute mention: repeated DFS checks (inefficient).
  • Present DSU approach: union/find per edge.
  • Complexity: O(E α(N)).
  • Quick example and note input indexing (1..n).

Construct Binary Tree from Preorder and Inorder (LC 105) – LeetCode प्रीऑर्डर और इनऑर्डर से बाइनरी ट्री बनाएँ (LC 105) – लीटकोड

Problem: Given preorder and inorder traversals of a binary tree (no duplicates), construct the binary tree and return its root. समस्या: बाइनरी ट्री के प्रीऑर्डर और इनऑर्डर ट्रैवर्सल (कोई डुप्लिकेट्स नहीं), बाइनरी ट्री बनाएँ और उसका रूट रिटर्न करें।

Pattern Tags पैटर्न टैग्स

  • Primary: Tree, Recursion, Divide & Conquer
  • Secondary: Hash map for inorder indices
  • Frequency: Very common (tree construction)

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: Optimized O(n) time, O(n) space. Naive slicing approach can be O(n²).
  • Edge: Empty arrays → null. No duplicates assumption used for index mapping.
  • Self: preorder=[3,9,20,15,7], inorder=[9,3,15,20,7] → returns root of constructed tree.

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "No duplicates? Array sizes?" Quick heuristic: "Tree from traversals? Divide & conquer with map." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "कोई डुप्लिकेट्स नहीं? ऐरे साइज?" क्विक ह्यूरिस्टिक: "ट्रैवर्सल से ट्री? डिवाइड & कॉन्कर विथ मैप।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“preorder and inorder” Preorder root first, inorder splits Root from preorder[preIdx] Use inorder index map to split left/right
“construct tree” Need to preserve original structure Recursion with indices Avoid slicing for O(n) solution
“no duplicates” Index map safe Hash map of inorder indices Track preorder index globally

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Use slices: take root = preorder[0], find its index in inorder (O(n) search), recursively slice arrays → O(n²) worst-case (skewed tree).
  • Optimal Build a hash map from inorder value → index to get O(1) splits, and use a global preIndex to traverse preorder without slicing. Recursively construct left/right with index ranges.

Non-Optimized Solution (Using slicing) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (स्लाइसिंग)

Javascript 
// Using slicing; simpler but O(n²) worst-case
function buildTreeBrute(preorder, inorder) {
  if (!preorder.length) return null;
  const rootVal = preorder[0];
  const root = new TreeNode(rootVal);
  const mid = inorder.indexOf(rootVal); // O(n)
  root.left = buildTreeBrute(preorder.slice(1, mid+1), inorder.slice(0, mid));
  root.right = buildTreeBrute(preorder.slice(mid+1), inorder.slice(mid+1));
  return root;
}
// Time: O(n^2) worst-case due to indexOf + slices (skewed tree)
Why This Solution? यह सॉल्यूशन क्यों?
  • Straightforward and correct; but slicing/indexSearch cost adds up.

Optimized Solution (Index map + preorder index pointer) ऑप्टिमाइज्ड सॉल्यूशन (इंडेक्स मैप + प्रीऑर्डर इंडेक्स पॉइंटर)

Javascript 
// Index map + preorder index pointer — O(n)
function buildTree(preorder, inorder) {
  if (!preorder.length || !inorder.length) return null;
  const idxMap = new Map();
  for (let i = 0; i < inorder.length; i++) idxMap.set(inorder[i], i);

  let preIndex = 0;
  function helper(left, right) { // inorder indices
    if (left > right) return null;
    const rootVal = preorder[preIndex++];
    const root = new TreeNode(rootVal);
    const mid = idxMap.get(rootVal);
    root.left = helper(left, mid - 1);
    root.right = helper(mid + 1, right);
    return root;
  }

  return helper(0, inorder.length - 1);
}
// Time: O(n), Space: O(n) (map + recursion)
Why This Solution? यह सॉल्यूशन क्यों?
  • Avoids slices and repeated scans by using map and shared preorder pointer — linear time.

Interview Framing इंटरव्यू फ्रेमिंग

“Preorder gives root order; inorder tells left/right split. Use preorder[preIndex] to get root, lookup its index in inorder via a hash map, then recursively build left & right subtrees using index ranges. Avoid slicing for O(n) performance.” “प्रीऑर्डर रूट ऑर्डर; इनऑर्डर लेफ्ट/राइट स्प्लिट। preorder[preIndex] से रूट, इनऑर्डर में इंडेक्स हैश मैप से, फिर इंडेक्स रेंज से लेफ्ट/राइट सबट्री। O(n) के लिए स्लाइसिंग से बचें।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Clarify no duplicates (essential for unique mapping). Show brute slice-based solution, then explain its inefficiency. Present optimized method: build index map for inorder, use a global preorder pointer and recurse on index ranges. Complexity O(n), space O(n). Example small tree dry-run. कोई डुप्लिकेट्स नहीं (यूनिक मैपिंग के लिए जरूरी)। ब्रूट स्लाइस-बेस्ड सॉल्यूशन, फिर इसकी अक्षमता। ऑप्टिमाइज्ड: इनऑर्डर के लिए इंडेक्स मैप, ग्लोबल प्रीऑर्डर पॉइंटर और इंडेक्स रेंज रिकर्स। O(n) समय, O(n) स्पेस। छोटा ट्री ड्राई-रन।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“Preorder[preIndex] gives the root; find its index in inorder to know left subtree size. Use a hashmap for inorder indices to avoid O(n) searches and a global preorder index that moves forward as we create nodes. Recursively build left and right by inorder ranges. This avoids slicing and runs in O(n).” “Preorder[preIndex] रूट देता है; इनऑर्डर में इंडेक्स से लेफ्ट सबट्री साइज। इनऑर्डर इंडेक्स के लिए हैशमैप से O(n) सर्च से बचें और ग्लोबल प्रीऑर्डर इंडेक्स जो नोड्स बनने पर आगे बढ़े। इनऑर्डर रेंज से लेफ्ट और राइट रिकर्सिव बिल्ड। स्लाइसिंग से बचकर O(n)।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate that preorder gives root order and inorder splits left/right.
  • Brute: slice arrays and recurse (O(n²) worst-case).
  • Optimal: map inorder values to indices + preorder pointer + index-range recursion.
  • Complexity: O(n) time, O(n) space.
  • Dry-run for [3,9,20,15,7] / [9,3,15,20,7].

Lowest Common Ancestor of a Binary Tree (LC 236) – LeetCode बाइनरी ट्री का सबसे निचला सामान्य पूर्वज (LC 236) – लीटकोड

Problem: Given a binary tree and two nodes p and q, return their lowest common ancestor (the deepest node that is ancestor of both). समस्या: एक बाइनरी ट्री और दो नोड्स p और q दिए गए, उनका सबसे निचला सामान्य पूर्वज (सबसे गहरा नोड जो दोनों का पूर्वज हो) रिटर्न करें।

Pattern Tags पैटर्न टैग्स

  • Primary: Binary Tree, Recursion, DFS
  • Secondary: Divide & Conquer
  • Frequency: Very common

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: O(n) time, O(h) space recursion.
  • Edge: p or q may be root; tree not necessarily BST.
  • Self: Tree = [3,5,1,6,2,0,8,null,null,7,4], p=5, q=1 → return 3.

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Not BST? p/q guaranteed in tree?" Quick heuristic: "LCA in binary tree? Recursive DFS." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स और उदाहरण स्पष्ट करें। इंटरव्यूअर से पूछें: "BST नहीं? p/q ट्री में निश्चित?" क्विक ह्यूरिस्टिक: "बाइनरी ट्री में LCA? रिकर्सिव DFS।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“lowest common ancestor” Need ancestor in binary tree DFS recursion Recurse left/right and combine results
“binary tree, not BST” No ordering guarantees Must explore whole tree Use recursive returns to bubble up
“return node” Return node, not value Careful with null checks If one child returns non-null, bubble

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Path-based: Find path from root to p, root to q, then compare paths → O(n) extra space.
  • Alternative Store parent pointers for all nodes using DFS, then move up from p and q until intersection.
  • Optimal Recursive DFS: If root == null or root == p or root == q → return root. Else, recurse left/right. If both sides non-null → return root. Else return whichever is non-null.

Non-Optimized Solution (Path-based compare) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (पाथ-बेस्ड कम्पेयर)

Javascript 
// Non-optimized: Path-based compare
function lowestCommonAncestorBrute(root, p, q) {
  function pathTo(node, target, path) {
    if (!node) return false;
    path.push(node);
    if (node === target) return true;
    if (pathTo(node.left, target, path) || pathTo(node.right, target, path)) return true;
    path.pop();
    return false;
  }
  const pathP = [], pathQ = [];
  pathTo(root, p, pathP);
  pathTo(root, q, pathQ);
  let i = 0;
  while (i < pathP.length && i < pathQ.length && pathP[i] === pathQ[i]) i++;
  return pathP[i-1];
}
// Time: O(n), Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple to understand but uses extra O(n) space for storing paths.

Optimized Solution (Recursive DFS) ऑप्टिमाइज्ड सॉल्यूशन (रिकर्सिव DFS)

Javascript 
// Optimized: Recursive DFS
function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left || right;
}
// Time: O(n), Space: O(h)
Why This Solution? यह सॉल्यूशन क्यों?
  • Efficient with O(h) space using recursion stack; elegant and concise.

Interview Framing इंटरव्यू फ्रेमिंग

“If current node is p or q, return it. Else check left and right. If both return non-null → this is LCA. Otherwise return whichever side is non-null.” “यदि वर्तमान नोड p या q है, इसे रिटर्न करें। अन्यथा बाएँ और दाएँ चेक करें। यदि दोनों नॉन-नल रिटर्न करते हैं → यह LCA है। अन्यथा जो साइड नॉन-नल है उसे रिटर्न करें।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Clarify that this is a general binary tree, not BST. Mention path-based method (works but extra storage). Explain recursive DFS solution. Complexity O(n), O(h). Edge cases: one node ancestor of other → works fine. स्पष्ट करें कि यह सामान्य बाइनरी ट्री है, BST नहीं। पाथ-बेस्ड विधि (काम करता है लेकिन अतिरिक्त स्टोरेज)। रिकर्सिव DFS सॉल्यूशन समझाएँ। जटिलता O(n), O(h)। एज केस: एक नोड दूसरे का पूर्वज → ठीक काम करता है।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“Do a recursive DFS. If node is null or equals p/q, return it. Recurse on left and right. If both sides return non-null, this node is LCA. Otherwise bubble up whichever is non-null. This works in O(n).” “रिकर्सिव DFS करें। यदि नोड नल है या p/q के बराबर है, इसे रिटर्न करें। बाएँ और दाएँ रिकर्स करें। यदि दोनों साइड नॉन-नल रिटर्न करते हैं, यह नोड LCA है। अन्यथा जो नॉन-नल है उसे ऊपर भेजें। यह O(n) में काम करता है।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate: find LCA in binary tree.
  • Brute: path-to-node arrays and compare.
  • Optimal: DFS recursion combining left/right returns.
  • Complexity O(n), O(h).
  • Example: p=5, q=1 → left=5, right=1 → root=3 is LCA.

House Robber III (LC 337) – LeetCode हाउस रॉबर III (LC 337) – लीटकोड

Problem: Given a binary tree, return max amount of money robbed without robbing directly-connected nodes. समस्या: एक बाइनरी ट्री दी गई, अधिकतम धन राशि रिटर्न करें जो बिना सीधे जुड़े नोड्स को लूटे प्राप्त हो।

Pattern Tags पैटर्न टैग्स

  • Primary: Tree DP, DFS
  • Secondary: Post-order traversal
  • Frequency: Common

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: O(n) time, O(h) space.
  • Edge: Single node tree; empty tree → 0.
  • Self: Tree = [3,2,3,null,3,null,1] → result = 7.

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Non-negative values? Any depth?" Quick heuristic: "Optimization on tree? DP with rob/not rob." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स और उदाहरण स्पष्ट करें। इंटरव्यूअर से पूछें: "नॉन-नेगेटिव वैल्यूज? कोई डेप्थ?" क्विक ह्यूरिस्टिक: "ट्री पर ऑप्टिमाइजेशन? DP लूटें/न लूटें।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“cannot rob directly-linked” Parent-child constraint Tree DP Post-order with include/exclude states
“maximize” Optimization problem DP recursion Compute both cases at each node
“tree nodes as houses” Binary tree DFS Return [rob, notRob] per node

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force At each node, either rob it or not, recurse. Exponential.
  • Optimal Post-order DFS returns two values: rob = node.val + notRob(left) + notRob(right), notRob = max(rob,left) + max(rob,right).

Non-Optimized Solution (Naive recursion) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (नैव रिकर्शन)

Javascript 
// Non-optimized: Naive recursion
function robBrute(root) {
  if (!root) return 0;
  let val = root.val;
  if (root.left) val += robBrute(root.left.left) + robBrute(root.left.right);
  if (root.right) val += robBrute(root.right.left) + robBrute(root.right.right);
  return Math.max(val, robBrute(root.left) + robBrute(root.right));
}
// Time: O(2^n), Space: O(h)
Why This Solution? यह सॉल्यूशन क्यों?
  • Correct but exponential due to repeated computations.

Optimized Solution (DFS returning [rob, notRob]) ऑप्टिमाइज्ड सॉल्यूशन (DFS रिटर्निंग [rob, notRob])

Javascript 
// Optimized: DFS returning [rob, notRob]
function rob(root) {
  function dfs(node) {
    if (!node) return [0, 0]; // [rob, notRob]
    const [lRob, lNot] = dfs(node.left);
    const [rRob, rNot] = dfs(node.right);
    const robNode = node.val + lNot + rNot;
    const notRob = Math.max(lRob, lNot) + Math.max(rRob, rNot);
    return [robNode, notRob];
  }
  const [robRoot, notRobRoot] = dfs(root);
  return Math.max(robRoot, notRobRoot);
}
// Time: O(n), Space: O(h)
Why This Solution? यह सॉल्यूशन क्यों?
  • Efficient O(n) by computing both rob and notRob states in one pass.

Interview Framing इंटरव्यू फ्रेमिंग

“We need DP on tree. At each node, decide rob or not. If rob → cannot rob children. If not rob → can take max from children. Use post-order to compute both values and return the max.” “हमें ट्री पर DP चाहिए। प्रत्येक नोड पर लूटने या न लूटने का निर्णय। यदि लूटें → बच्चे नोड्स नहीं लूट सकते। यदि न लूटें → बच्चों से अधिकतम ले सकते हैं। पोस्ट-ऑर्डर से दोनों वैल्यूज और अधिकतम रिटर्न।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Brute: try robbing vs skipping each node (exponential). Optimized: return [rob, notRob] for each node. Recursively combine results bottom-up. Complexity O(n). Works naturally for all edge cases. ब्रूट: प्रत्येक नोड पर लूटने/छोड़ने की कोशिश (एक्सपोनेंशियल)। ऑप्टिमाइज्ड: प्रत्येक नोड के लिए [rob, notRob] रिटर्न। नीचे से ऊपर रिकर्सिवली रिजल्ट्स जोड़ें। जटिलता O(n)। सभी एज केस के लिए स्वाभाविक रूप से काम करता है।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“At each node, compute two values: rob = node.val + notRob(left)+notRob(right), and notRob = max of left + max of right. Return [rob, notRob] upwards. At root, answer is max of both. Runs in O(n).” “प्रत्येक नोड पर दो वैल्यूज: rob = node.val + notRob(left)+notRob(right), और notRob = लेफ्ट का अधिकतम + राइट का अधिकतम। [rob, notRob] ऊपर रिटर्न। रूट पर, उत्तर दोनों का अधिकतम। O(n) में चलता है।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate: binary tree, no adjacent robbery.
  • Brute: try rob/not rob at each node.
  • Optimal: DP with [rob, notRob] per node.
  • Complexity O(n).
  • Example small tree with answer 7.

Binary Tree Right Side View (LC 199) – LeetCode बाइनरी ट्री राइट साइड व्यू (LC 199) – लीटकोड

Problem: Given a binary tree, return values of nodes visible from right side. समस्या: एक बाइनरी ट्री दी गई, दाईं ओर से दिखाई देने वाले नोड्स की वैल्यूज रिटर्न करें।

Pattern Tags पैटर्न टैग्स

  • Primary: BFS level-order
  • Secondary: DFS with depth tracking
  • Frequency: Common

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: O(n) time, O(n) space.
  • Edge: Single node tree; skewed left.
  • Self: [1,2,3,null,5,null,4] → [1,3,4].

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Empty tree case? Max depth?" Quick heuristic: "Rightmost per level? BFS or DFS." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स और उदाहरण स्पष्ट करें। इंटरव्यूअर से पूछें: "खाली ट्री केस? अधिकतम डेप्थ?" क्विक ह्यूरिस्टिक: "प्रत्येक लेवल पर राइटमोस्ट? BFS या DFS।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“right side view” Rightmost per level Level-order BFS Take last node at each level
“visible from right” Depth-based visibility DFS depth-first right Preorder right-first + record first
“return values” Only list of values No tree construction Simple traversal output

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Do level-order BFS and collect all nodes per level, then take last one.
  • Alternative DFS preorder (root-right-left) and track max depth visited. First node seen at each depth is rightmost.
  • Optimal Either BFS or DFS. BFS is easiest to explain.

Non-Optimized Solution (DFS right-first) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (DFS राइट-फर्स्ट)

Javascript 
// Non-optimized: DFS right-first
function rightSideViewDFS(root) {
  const res = [];
  function dfs(node, depth) {
    if (!node) return;
    if (res.length === depth) res.push(node.val);
    dfs(node.right, depth+1);
    dfs(node.left, depth+1);
  }
  dfs(root, 0);
  return res;
}
// Time: O(n), Space: O(h)
Why This Solution? यह सॉल्यूशन क्यों?
  • Correct and intuitive but DFS may be less obvious than BFS for level-order.

Optimized Solution (BFS level-order) ऑप्टिमाइज्ड सॉल्यूशन (BFS लेवल-ऑर्डर)

Javascript 
// Optimized: BFS level-order
function rightSideView(root) {
  if (!root) return [];
  const res = [], queue = [root];
  while (queue.length) {
    let size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
      if (i === size - 1) res.push(node.val); // last node in level
    }
  }
  return res;
}
// Time: O(n), Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • BFS naturally processes levels, making it easier to pick the last node per level.

Interview Framing इंटरव्यू फ्रेमिंग

“Right side view means last node at each level. BFS by levels → push last node. Alternative is DFS right-first. Both O(n).” “राइट साइड व्यू का मतलब प्रत्येक लेवल पर आखिरी नोड। BFS लेवल्स से → आखिरी नोड पुश करें। वैकल्पिक DFS राइट-फर्स्ट। दोनों O(n)।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Clarify we need last node at each depth. Brute: BFS all nodes per level and take last. Optimized: BFS in one pass and directly pick last per level. Complexity O(n). Edge cases: skewed tree. स्पष्ट करें कि हमें प्रत्येक डेप्थ पर आखिरी नोड चाहिए। ब्रूट: BFS सभी नोड्स प्रति लेवल और आखिरी लें। ऑप्टिमाइज्ड: एक पास में BFS और सीधे आखिरी प्रति लेवल। जटिलता O(n)। एज केस: स्क्यूड ट्री।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“Traverse level by level with BFS. At each level, record the last node value. That gives the right-side view. Runs in O(n) time and space.” “BFS के साथ लेवल दर लेवल ट्रैवर्स करें। प्रत्येक लेवल पर, आखिरी नोड वैल्यू रिकॉर्ड करें। यह राइट-साइड व्यू देता है। O(n) समय और स्पेस में चलता है।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate: need rightmost node at each level.
  • Brute: BFS store full level.
  • Optimal: BFS, push last node only.
  • Complexity O(n).
  • Example tree → [1,3,4].

Count Complete Tree Nodes (LC 222) – LeetCode कम्प्लीट ट्री नोड्स की गिनती (LC 222) – लीटकोड

Problem: Given root of a complete binary tree, return total number of nodes. समस्या: एक कम्प्लीट बाइनरी ट्री का रूट दिया गया, कुल नोड्स की संख्या रिटर्न करें।

Pattern Tags पैटर्न टैग्स

  • Primary: Tree, Binary Search on height
  • Secondary: DFS counting
  • Frequency: Medium

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: Naive O(n), optimized O(log² n).
  • Edge: Empty tree → 0.
  • Self: Tree with height 3 but missing last nodes.

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Complete tree guaranteed? Max height?" Quick heuristic: "Count nodes efficiently? Exploit completeness." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स और उदाहरण स्पष्ट करें। इंटरव्यूअर से पूछें: "कम्प्लीट ट्री गारंटी? अधिकतम हाइट?" क्विक ह्यूरिस्टिक: "नोड्स की गिनती कुशलता से? कम्प्लीटनेस का उपयोग।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“complete binary tree” Structure property Height-based check Compare left/right heights
“count nodes” Total nodes Binary search / DFS Use formula if perfect subtree
“optimize” n ≤ 10⁴ (but log² n better) Exploit completeness Perfect subtree detection

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Traverse tree and count → O(n).
  • Optimal For complete tree: Compute leftmost height and rightmost height. If equal → perfect tree, return 2^h - 1. Else recursively count left + right + 1.

Non-Optimized Solution (Simple recursion count) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (सिंपल रिकर्शन काउंट)

Javascript 
// Non-optimized: Simple recursion count
function countNodesBrute(root) {
  if (!root) return 0;
  return 1 + countNodesBrute(root.left) + countNodesBrute(root.right);
}
// Time: O(n), Space: O(h)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple and correct but O(n) doesn’t exploit complete tree property.

Optimized Solution (Height-based) ऑप्टिमाइज्ड सॉल्यूशन (हाइट-बेस्ड)

Javascript 
// Optimized: Height-based
function countNodes(root) {
  if (!root) return 0;
  function heightLeft(node) {
    let h = 0;
    while (node) { h++; node = node.left; }
    return h;
  }
  function heightRight(node) {
    let h = 0;
    while (node) { h++; node = node.right; }
    return h;
  }
  const hl = heightLeft(root);
  const hr = heightRight(root);
  if (hl === hr) return (1 << hl) - 1; // perfect subtree
  return 1 + countNodes(root.left) + countNodes(root.right);
}
// Time: O(log² n), Space: O(log n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Exploits complete tree property for O(log² n) by checking perfect subtrees.

Interview Framing इंटरव्यू फ्रेमिंग

“Naive count is O(n). Since tree is complete, use left/right heights: if equal → perfect subtree count formula. Else recurse. Gives O(log² n).” “नैव काउंट O(n) है। चूंकि ट्री कम्प्लीट है, बाएँ/दाएँ हाइट्स: यदि बराबर → परफेक्ट सबट्री काउंट फॉर्मूला। अन्यथा रिकर्स। O(log² n) देता है।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Clarify difference: complete vs perfect. Brute: DFS count all nodes. Optimized: use heights to detect perfect subtrees. Complexity O(log² n). Example with height 3. स्पष्ट करें अंतर: कम्प्लीट बनाम परफेक्ट। ब्रूट: DFS सभी नोड्स गिनें। ऑप्टिमाइज्ड: हाइट्स से परफेक्ट सबट्री डिटेक्शन। जटिलता O(log² n)। हाइट 3 का उदाहरण।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“For complete tree, compute leftmost and rightmost heights. If equal, it’s perfect → nodes = 2^h - 1. Else, recurse on children. This yields O(log² n).” “कम्प्लीट ट्री के लिए, बाएँ और दाएँ हाइट्स गणना करें। यदि बराबर, परफेक्ट है → नोड्स = 2^h - 1। अन्यथा बच्चों पर रिकर्स। यह O(log² n) देता है।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate: count nodes in complete tree.
  • Brute: simple DFS count (O(n)).
  • Optimal: exploit complete-tree property with height checks.
  • Complexity O(log² n).
  • Example small tree.

Longest Increasing Subsequence (LC 300) – LeetCode सबसे लंबा बढ़ता हुआ सबसीक्वेंस (LC 300) – लीटकोड

Problem: Given an integer array nums, return the length of the longest strictly increasing subsequence. समस्या: एक पूर्णांक ऐरे nums दिया गया, सबसे लंबे सख्ती से बढ़ते हुए सबसीक्वेंस की लंबाई रिटर्न करें।

Pattern Tags पैटर्न टैग्स

  • Primary: Dynamic Programming, Binary Search
  • Secondary: Patience Sorting
  • Frequency: Very common

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: DP O(n²), Optimized O(n log n).
  • Edge: All equal elements → 1. Empty array → 0.
  • Self: [10,9,2,5,3,7,101,18] → 4 ([2,3,7,101]).

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Strictly increasing? Array size?" Quick heuristic: "Longest increasing subsequence? DP or binary search." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स और उदाहरण स्पष्ट करें। इंटरव्यूअर से पूछें: "सख्ती से बढ़ता? ऐरे साइज?" क्विक ह्यूरिस्टिक: "सबसे लंबा बढ़ता सबसीक्वेंस? DP या बाइनरी सर्च।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“longest increasing” Strictly monotone DP or binary search Build subsequence lengths incrementally
“subsequence” Not contiguous Must allow skips DP O(n²) or patience sorting O(n log n)
“length only” No reconstruction needed Just return max length Focus on DP values or tails array

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Generate all subsequences, check LIS → exponential.
  • Non-Optimized DP O(n²): dp[i] = LIS ending at i.
  • Optimal Binary search O(n log n): maintain smallest tail of increasing subsequence of length k using patience sorting.

Non-Optimized Solution (DP O(n²)) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (DP O(n²))

Javascript 
// Non-optimized: DP O(n²)
function lengthOfLIS_DP(nums) {
  if (!nums.length) return 0;
  const dp = Array(nums.length).fill(1);
  let maxLen = 1;
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
    maxLen = Math.max(maxLen, dp[i]);
  }
  return maxLen;
}
// Time: O(n²), Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple to implement and understand but quadratic time due to nested loops.

Optimized Solution (Binary Search O(n log n)) ऑप्टिमाइज्ड सॉल्यूशन (बाइनरी सर्च O(n log n))

Javascript 
// Optimized: Binary Search O(n log n)
function lengthOfLIS(nums) {
  const tails = [];
  for (let num of nums) {
    let l = 0, r = tails.length;
    while (l < r) {
      let m = Math.floor((l + r) / 2);
      if (tails[m] < num) l = m + 1;
      else r = m;
    }
    tails[l] = num;
  }
  return tails.length;
}
// Time: O(n log n), Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Efficient O(n log n) using binary search to maintain tails array for patience sorting.

Interview Framing इंटरव्यू फ्रेमिंग

“Classic LIS: O(n²) DP compares each pair. Optimized uses binary search on tails: maintain smallest tail of increasing subsequence of length k. Replace using lower bound. Runs O(n log n).” “क्लासिक LIS: O(n²) DP प्रत्येक जोड़े की तुलना। ऑप्टिमाइज्ड टेल्स पर बाइनरी सर्च: k लंबाई के बढ़ते सबसीक्वेंस का सबसे छोटा टेल। लोअर बाउंड से रिप्लेस। O(n log n)।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Brute: exponential subsequences. O(n²): DP[i] = LIS ending at i. O(n log n): patience sorting idea, maintain tails with binary search. Complexity: O(n²) → O(n log n). Edge cases: all decreasing → LIS = 1. ब्रूट: एक्सपोनेंशियल सबसीक्वेंस। O(n²): DP[i] = i पर समाप्त LIS। O(n log n): पेशेंस सॉर्टिंग, बाइनरी सर्च से टेल्स। जटिलता: O(n²) → O(n log n)। एज केस: सभी घटते → LIS = 1।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“Use DP. O(n²) version: dp[i] = max LIS ending at i. Optimized O(n log n): keep tails array, binary search replace position for each num. Answer is length of tails.” “DP उपयोग करें। O(n²): dp[i] = i पर अधिकतम LIS। ऑप्टिमाइज्ड O(n log n): टेल्स ऐरे, प्रत्येक num के लिए बाइनरी सर्च रिप्लेस। उत्तर टेल्स की लंबाई।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate: LIS length in array.
  • Brute: generate subsequences.
  • DP: compare all pairs O(n²).
  • Optimal: patience sorting O(n log n).
  • Example [10,9,2,5,3,7,101,18] → LIS = 4.

Longest Common Subsequence (LC 1143) – LeetCode सबसे लंबा सामान्य सबसीक्वेंस (LC 1143) – लीटकोड

Problem: Given two strings text1 and text2, return length of their longest common subsequence. समस्या: दो स्ट्रिंग्स text1 और text2 दी गई, उनके सबसे लंबे सामान्य सबसीक्वेंस की लंबाई रिटर्न करें।

Pattern Tags पैटर्न टैग्स

  • Primary: DP on strings
  • Secondary: 2D bottom-up DP
  • Frequency: Classic

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: O(m·n) time, O(m·n) space.
  • Edge: One empty string → 0.
  • Self: “abcde”, “ace” → 3.

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "ASCII strings? Max length?" Quick heuristic: "LCS of strings? 2D DP." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स और उदाहरण स्पष्ट करें। इंटरव्यूअर से पूछें: "ASCII स्ट्रिंग्स? अधिकतम लंबाई?" क्विक ह्यूरिस्टिक: "स्ट्रिंग्स का LCS? 2D DP।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“common subsequence” Not contiguous needed 2D DP Compare chars; build relation
“two strings” Cross-check characters DP on grid Table dimension m×n
“longest” Optimization Take max of subproblems Standard LCS recurrence

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Try all subsequences of first string, check in second. Exponential.
  • Non-Optimized Recursive with memoization: O(m·n) but with extra overhead.
  • Optimal Bottom-up 2D DP: If chars match, add 1 + diagonal; else max(top, left).

Non-Optimized Solution (Recursive with memo) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (मेमो के साथ रिकर्सिव)

Javascript 
// Non-optimized: Recursive with memo
function lcsRec(text1, text2) {
  const memo = {};
  function dfs(i, j) {
    if (i === text1.length || j === text2.length) return 0;
    const key = i + "," + j;
    if (key in memo) return memo[key];
    if (text1[i] === text2[j]) memo[key] = 1 + dfs(i+1, j+1);
    else memo[key] = Math.max(dfs(i+1, j), dfs(i, j+1));
    return memo[key];
  }
  return dfs(0,0);
}
// Time: O(m·n), Space: O(m·n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Correct but recursive overhead makes it less efficient than bottom-up DP.

Optimized Solution (Bottom-up DP) ऑप्टिमाइज्ड सॉल्यूशन (बॉटम-अप DP)

Javascript 
// Optimized: Bottom-up DP
function longestCommonSubsequence(text1, text2) {
  const m = text1.length, n = text2.length;
  const dp = Array.from({length: m+1}, () => Array(n+1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i-1] === text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
      else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
    }
  }
  return dp[m][n];
}
// Time: O(m·n), Space: O(m·n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Efficient O(m·n) with straightforward iterative approach, avoiding recursion stack.

Interview Framing इंटरव्यू फ्रेमिंग

“Naive is exponential. DP: if chars match, add 1 + diagonal. Else max(top, left). O(mn).” “नैव एक्सपोनेंशियल है। DP: यदि कैरेक्टर्स मिलते हैं, 1 + डायगोनल। अन्यथा अधिकतम(ऊपर, बाएँ)। O(mn)।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Brute: try all subsequences. Optimal: DP table recurrence. O(mn) time and space. Edge case: empty string → answer 0. Can optimize to O(min(m,n)) space using 1D rolling array. ब्रूट: सभी सबसीक्वेंस आजमाएँ। ऑप्टिमल: DP टेबल रिकरेंस। O(mn) समय और स्पेस। एज केस: खाली स्ट्रिंग → उत्तर 0। 1D रोलिंग ऐरे से O(min(m,n)) स्पेस।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“Build DP table m×n. If chars match → diagonal+1, else max of top or left. Runs O(mn). Example ‘abcde’, ‘ace’ → 3.” “m×n DP टेबल बनाएँ। यदि कैरेक्टर्स मिलते हैं → डायगोनल+1, अन्यथा ऊपर या बाएँ का अधिकतम। O(mn)। उदाहरण ‘abcde’, ‘ace’ → 3।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate: LCS length of two strings.
  • Brute: check all subsequences.
  • DP recurrence with match/skip.
  • Complexity O(mn).
  • Example → 3.

Word Break (LC 139) – LeetCode वर्ड ब्रेक (LC 139) – लीटकोड

Problem: Given a string s and dictionary of words, return true if s can be segmented into words from dictionary. समस्या: एक स्ट्रिंग s और शब्दों का डिक्शनरी दिया गया, यदि s को डिक्शनरी के शब्दों में विभाजित किया जा सकता है तो ट्रू रिटर्न करें।

Pattern Tags पैटर्न टैग्स

  • Primary: DP, String
  • Secondary: BFS on indices
  • Frequency: Very common

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: O(n²) time, O(n) space.
  • Edge: Empty string true. Dict empty → false unless s empty.
  • Self: “leetcode”, [“leet”, “code”] → true.

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Empty string case? Dict size?" Quick heuristic: "String segmentation? DP or BFS." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स और उदाहरण स्पष्ट करें। इंटरव्यूअर से पूछें: "खाली स्ट्रिंग केस? डिक्ट साइज?" क्विक ह्यूरिस्टिक: "स्ट्रिंग सेगमेंटेशन? DP या BFS।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“word dictionary” Membership check Hash set for fast lookup Substring membership O(1)
“segment string” Partition problem DP dp[i]=reachable up to i
“return true/false” Boolean DP Yes/No segmentation Early break when found true

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Recursive try all splits. Exponential.
  • Optimal DP: dp[i] = true if substring [0..i) can be segmented.

Non-Optimized Solution (Recursive) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (रिकर्सिव)

Javascript 
// Non-optimized: Recursive
function wordBreakRec(s, wordDict) {
  const set = new Set(wordDict);
  function dfs(start) {
    if (start === s.length) return true;
    for (let end = start+1; end <= s.length; end++) {
      if (set.has(s.slice(start, end)) && dfs(end)) return true;
    }
    return false;
  }
  return dfs(0);
}
// Time: O(2^n), Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Correct but exponential without memoization; inefficient for large inputs.

Optimized Solution (Bottom-up DP) ऑप्टिमाइज्ड सॉल्यूशन (बॉटम-अप DP)

Javascript 
// Optimized: Bottom-up DP
function wordBreak(s, wordDict) {
  const set = new Set(wordDict);
  const dp = Array(s.length+1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && set.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}
// Time: O(n²), Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Efficient O(n²) with DP and hash set for fast dictionary lookup.

Interview Framing इंटरव्यू फ्रेमिंग

“We want to see if string can be split into words. Brute force try all splits is exponential. Optimal DP: dp[i]=true if prefix up to i can be split. O(n²).” “हमें देखना है कि स्ट्रिंग को शब्दों में विभाजित किया जा सकता है। ब्रूट फोर्स सभी स्प्लिट्स एक्सपोनेंशियल। ऑप्टिमल DP: dp[i]=true यदि i तक का प्रीफिक्स स्प्लिट हो। O(n²)।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Brute: recursive try all cuts. Optimal: DP with hash set dictionary lookup. Complexity O(n²). Edge cases: empty string, empty dict. BFS alternative: treat indices as nodes. ब्रूट: रिकर्सिव सभी कट्स। ऑप्टिमल: DP हैश सेट डिक्शनरी लुकअप। जटिलता O(n²)। एज केस: खाली स्ट्रिंग, खाली डिक्ट। BFS वैकल्पिक: इंडेक्स को नोड्स के रूप में।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“Use DP. dp[i]=true if substring[0..i) can be segmented. Check all j “DP उपयोग करें। dp[i]=true यदि सबस्ट्रिंग[0..i) सेगमेंट हो। सभी j

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate: check segmentation into dict words.
  • Brute: recursive try splits.
  • Optimal: DP with substring membership.
  • Complexity O(n²).
  • Example ‘leetcode’ → true.

Unique Paths (LC 62) – LeetCode यूनिक पाथ्स (LC 62) – लीटकोड

Problem: Given m×n grid, return number of unique paths from top-left to bottom-right moving only down or right. समस्या: m×n ग्रिड दिया गया, टॉप-लेफ्ट से बॉटम-राइट तक केवल नीचे या दाएँ चलकर यूनिक पाथ्स की संख्या रिटर्न करें।

Pattern Tags पैटर्न टैग्स

  • Primary: DP grid
  • Secondary: Combinatorics
  • Frequency: Classic

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: O(mn) DP, O(1) combinatorial.
  • Edge: 1×1 grid → 1.
  • Self: m=3, n=7 → 28.

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Grid size? Only right/down?" Quick heuristic: "Count paths in grid? DP or combinatorics." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स और उदाहरण स्पष्ट करें। इंटरव्यूअर से पूछें: "ग्रिड साइज? केवल दाएँ/नीचे?" क्विक ह्यूरिस्टिक: "ग्रिड में पाथ्स गिनें? DP या कॉम्बिनेटोरिक्स।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“unique paths” Grid movement DP grid / combinatorics dp[i][j]=dp[i-1][j]+dp[i][j-1]
“only right or down” Restricted moves Pascal’s triangle Classic lattice paths
“count number” Not min/max optimization Counting DP Simple accumulation

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force DFS all paths. Exponential.
  • Optimal DP: dp[i][j] = ways from top-left to (i,j). Or combinatorial formula: choose(m+n-2, m-1).

Non-Optimized Solution (DFS recursion) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (DFS रिकर्शन)

Javascript 
// Non-optimized: DFS recursion
function uniquePathsDFS(m, n) {
  function dfs(i, j) {
    if (i === m-1 && j === n-1) return 1;
    if (i >= m || j >= n) return 0;
    return dfs(i+1, j) + dfs(i, j+1);
  }
  return dfs(0,0);
}
// Time: O(2^(m+n)), Space: O(m+n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Correct but exponential due to repeated path explorations.

Optimized Solution (DP grid) ऑप्टिमाइज्ड सॉल्यूशन (DP ग्रिड)

Javascript 
// Optimized: DP grid
function uniquePaths(m, n) {
  const dp = Array.from({length: m}, () => Array(n).fill(1));
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
  }
  return dp[m-1][n-1];
}
// Time: O(m·n), Space: O(m·n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Efficient O(m·n) with DP grid; also supports combinatorial O(1) space solution.

Interview Framing इंटरव्यू फ्रेमिंग

“Naive: DFS all paths. Optimal: DP with grid. dp[i][j] = ways from top-left to (i,j). Or combinatorial formula: choose(m+n-2, m-1).” “नैव: DFS सभी पाथ्स। ऑप्टिमल: DP ग्रिड। dp[i][j] = टॉप-लेफ्ट से (i,j) तक रास्ते। या कॉम्बिनेटोरियल फॉर्मूला: choose(m+n-2, m-1)।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Brute: DFS count paths. DP: fill grid with sums of top+left. Complexity O(mn). Combinatorics formula also valid. Edge: m or n = 1 → paths=1. ब्रूट: DFS पाथ्स गिनें। DP: ग्रिड को ऊपर+बाएँ के योग से भरें। जटिलता O(mn)। कॉम्बिनेटोरिक्स फॉर्मूला भी वैलिड। एज: m या n = 1 → पाथ्स=1।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“DP grid. dp[i][j] = dp[i-1][j] + dp[i][j-1]. Fill table, return bottom-right. Runs O(mn). Alternatively combinatorics formula choose(m+n-2, m-1).” “DP ग्रिड। dp[i][j] = dp[i-1][j] + dp[i][j-1]। टेबल भरें, बॉटम-राइट रिटर्न। O(mn)। वैकल्पिक रूप से कॉम्बिनेटोरिक्स फॉर्मूला choose(m+n-2, m-1)।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate: number of paths in grid.
  • Brute: DFS all paths.
  • Optimal: DP grid or combinatorics.
  • Complexity O(mn) or O(1).
  • Example 3×7 → 28.

Coin Change II (LC 518) – LeetCode कॉइन चेंज II (LC 518) – लीटकोड

Problem: Given coins and amount, return number of combinations to make amount. Unlimited coins. समस्या: कॉइन्स और अमाउंट दिए गए, अमाउंट बनाने के लिए कॉम्बिनेशन्स की संख्या रिटर्न करें। असीमित कॉइन्स।

Pattern Tags पैटर्न टैग्स

  • Primary: DP (Unbounded Knapsack)
  • Secondary: 1D DP optimization
  • Frequency: Classic

Quick Notes for Me मेरे लिए क्विक नोट्स

  • Big O: O(n·amount) time, O(amount) space.
  • Edge: amount=0 → 1 way (empty set).
  • Self: coins=[1,2,5], amount=5 → 4.

Pattern Recognition Checklist पैटर्न रिकग्निशन चेकलिस्ट

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Unlimited coins? Non-negative amount?" Quick heuristic: "Count combinations? Unbounded knapsack." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स और उदाहरण स्पष्ट करें। इंटरव्यूअर से पूछें: "असीमित कॉइन्स? नॉन-नेगेटिव अमाउंट?" क्विक ह्यूरिस्टिक: "कॉम्बिनेशन्स गिनें? अनबाउंडेड नैपसैक।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
“number of combinations” Count ways, not min DP count knapsack Order doesn’t matter
“unlimited coins” Unbounded knapsack 1D dp accumulation Outer loop on coins
“return int” Not list Just count Edge: dp[0]=1

Approach Breakdown एप्रोच ब्रेकडाउन

  • Brute Force Recursive try all coins repeatedly. Exponential.
  • Non-Optimized Recursive with memoization: O(n·amount) but with overhead.
  • Optimal DP: dp[x] += dp[x-coin] for each coin, with outer loop on coins to avoid duplicates.

Non-Optimized Solution (Recursive with memo) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (मेमो के साथ रिकर्सिव)

Javascript 
// Non-optimized: Recursive with memo
function changeRec(amount, coins) {
  const memo = {};
  function dfs(i, remain) {
    if (remain === 0) return 1;
    if (i === coins.length || remain < 0) return 0;
    const key = i + "," + remain;
    if (key in memo) return memo[key];
    return memo[key] = dfs(i, remain - coins[i]) + dfs(i+1, remain);
  }
  return dfs(0, amount);
}
// Time: O(n·amount), Space: O(n·amount)
Why This Solution? यह सॉल्यूशन क्यों?
  • Correct but recursive overhead; memoization still uses O(n·amount) space.

Optimized Solution (DP) ऑप्टिमाइज्ड सॉल्यूशन (DP)

Javascript 
// Optimized: DP
function change(amount, coins) {
  const dp = Array(amount+1).fill(0);
  dp[0] = 1;
  for (let coin of coins) {
    for (let x = coin; x <= amount; x++) {
      dp[x] += dp[x - coin];
    }
  }
  return dp[amount];
}
// Time: O(n·amount), Space: O(amount)
Why This Solution? यह सॉल्यूशन क्यों?
  • Efficient O(n·amount) time and O(amount) space with 1D DP array.

Interview Framing इंटरव्यू फ्रेमिंग

“This is unbounded knapsack counting. Outer loop over coins to avoid double-counting. dp[x]+=dp[x-coin]. O(n·amount).” “यह अनबाउंडेड नैपसैक गिनती है। डबल-काउंटिंग से बचने के लिए कॉइन्स पर बाहरी लूप। dp[x]+=dp[x-coin]। O(n·amount)।”

How to Explain to Interviewers इंटरव्यूअर्स को कैसे समझाएँ

Brute: try all combinations recursively. DP: number of ways to form amount using coins. Outer loop coins ensures no duplicates. Complexity O(n·amount). Edge: amount=0 → 1. ब्रूट: रिकर्सिवली सभी कॉम्बिनेशन्स। DP: कॉइन्स से अमाउंट बनाने के तरीके। बाहरी लूप कॉइन्स डुप्लिकेट्स रोकता है। जटिलता O(n·amount)। एज: amount=0 → 1।

One-Go Interview Answer वन-गो इंटरव्यू आंसर

“Classic unbounded knapsack. Initialize dp[0]=1. For each coin, update dp[x]+=dp[x-coin]. Return dp[amount]. Runs in O(n·amount).” “क्लासिक अनबाउंडेड नैपसैक। dp[0]=1 इनिशियलाइज। प्रत्येक कॉइन के लिए, dp[x]+=dp[x-coin]। dp[amount] रिटर्न। O(n·amount) में।”

5-Step Reusable Script 5-स्टेप रीयूजेबल स्क्रिप्ट

  • Restate: count combinations to form amount.
  • Brute: recursive try coins.
  • Optimal: DP with 1D array.
  • Complexity O(n·amount).
  • Example coins [1,2,5], amount=5 → 4 ways.