Arrays & Hashing (Days 1-2) ऐरे और हैशिंग (दिन 1-2)

Arrays are lists in JS ([]), great for indexed access. Hashing uses Maps for fast lookups. Focus: O(1) access, but inserts/deletes shift elements (O(n)). जावास्क्रिप्ट में ऐरे लिस्ट हैं ([]), इंडेक्स्ड एक्सेस के लिए बढ़िया। हैशिंग मैप्स का उपयोग तेज लुकअप के लिए करता है। फोकस: O(1) एक्सेस, लेकिन इंसर्ट/डिलीट एलिमेंट्स को शिफ्ट करते हैं (O(n))।

Two Sum (LC 1) - LeetCode टू सम (LC 1) - लीटकोड

Problem: Given nums array and target, return indices of two numbers that add to target. समस्या: दिए गए nums ऐरे और टारगेट में, दो नंबर्स के इंडेक्स रिटर्न करें जो टारगेट में जोड़ते हैं।

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

  • Primary: Array & Hashing, Two Sum
  • Secondary: Hash Map Frequency
  • Frequency: High (FAANG whiteboard favorite)

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

  • Big O: Optimized O(n) time, O(n) space.
  • Edge: Empty array, duplicates, negatives.
  • Self: Practice with [2,7,11,15] target 9 → [0,1]. Maps beat nested loops.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Is the array sorted? Value range (e.g., positives/negatives)? Memory limits? Exactly one solution or multiples?" Quick heuristic: "Is this about finding pairs that sum to target? Hints ordering (no), adjacency (no), prefix (no), structure (hash for fast lookup)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "क्या ऐरे सॉर्टेड? वैल्यू रेंज (पॉजिटिव/नेगेटिव)? मेमोरी लिमिट्स? एग्जैक्टली एक सॉल्यूशन या मल्टिपल?" क्विक ह्यूरिस्टिक: "क्या यह टारगेट तक सम करने वाले पेयर्स ढूंढने के बारे में? हिन्ट्स ऑर्डरिंग (नहीं), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (हैश फास्ट लुकअप के लिए)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"indices of two numbers that add to target" Return indices? Unordered array? Assume unique solution? Hash Map for O(1) lookup of complement Breakdown: Brute pairs → Optimize with seen values storage. Ask: Duplicates allowed?
"array", "target sum" Sorted? Negatives? n up to 10^4? Array & Hashing, avoid sort if indices needed Think: Trade space for time? Hash complements.

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

  • Brute Force (Nested Loops): Use two nested loops to check every possible pair of numbers. For each i, check j > i if nums[i] + nums[j] == target. This is straightforward but O(n²) time due to checking all pairs.
  • Sorting + Two Pointers: Sort the array with indices preserved (e.g., via a map or paired array), then use left/right pointers starting from ends, moving inward based on sum. O(n log n) time, but requires extra work to track original indices.
  • Hash Map (Optimal): Use a Map to store each number and its index as we iterate once. For each num, compute complement = target - num, and check if it exists in the Map. If yes, return the indices; else, add current num:index. This achieves O(n) time with O(1) lookups.

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

Javascript
// Brute Force (Nested Loops): Check every possible pair
function twoSum(nums, target) {
  // Outer loop: Iterate through each element as first number
  for (let i = 0; i < nums.length; i++) {
    // Inner loop: Check remaining elements as second number
    for (let j = i + 1; j < nums.length; j++) {
      // If pair sums to target, return their indices
      if (nums[i] + nums[j] === target) {
        return [i, j]; // Found the pair
      }
    }
  }
  // If no pair found (though problem assumes one), return empty
  return [];
}
// Time: O(n^2) - bad for large arrays, Space: O(1) - no extra storage
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple, intuitive nested loops for all pairs.
  • No extra data structures, minimal space.
  • Slow O(n²) time, not ideal for large inputs.

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

Javascript
// Optimized (Hash Map): Use Map for O(1) lookups of complements
function twoSum(nums, target) {
  // Create a Map to store number and its index
  const numMap = new Map();
  // Single loop through array
  for (let i = 0; i < nums.length; i++) {
    // Calculate needed complement
    const complement = target - nums[i];
    // Check if complement already in Map (before adding current)
    if (numMap.has(complement)) {
      // Return indices if found
      return [numMap.get(complement), i];
    }
    // Add current num and index to Map
    numMap.set(nums[i], i);
  }
  // No solution (assumes one exists)
  return [];
}
// Time: O(n) - one pass, Space: O(n) - Map stores all elements
Why This Solution? यह सॉल्यूशन क्यों?
  • O(n) time via hash map for O(1) lookups.
  • Single pass, handles duplicates/negatives.
  • Best for interviews due to efficiency.

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

Brute force is two nested loops — O(n²). Works but too slow for large n. Alternative is sorting + two pointers (O(n log n)), but since we need original indices, it complicates tracking. Hash map is optimal O(n): store seen numbers and check complements. Here's how I'd implement it. ब्रूट फोर्स दो नेस्टेड लूप्स है — O(n²)। काम करता लेकिन बड़े n के लिए धीमा। वैकल्पिक सॉर्टिंग + टू पॉइंटर्स (O(n log n)), लेकिन ओरिजिनल इंडेक्स चाहिए तो ट्रैकिंग कॉम्प्लिकेट। हैश मैप ऑप्टिमल O(n): देखे नंबर्स स्टोर और कॉम्प्लिमेंट्स चेक। यहाँ इम्प्लीमेंट कैसे करूंगा।

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

"So, for Two Sum, the goal is to find two indices in the array that add up to the target, and we assume exactly one solution exists. First, the brute force approach: I'd use two nested loops—outer for i from 0 to n-1, inner for j from i+1 to n-1, and check if nums[i] + nums[j] equals target. If yes, return [i, j]. This is O(n²) time and O(1) space—easy to code but too slow for large arrays. Another way is sorting the array with indices, then two pointers from left and right, adjusting based on sum, but we'd need to map back to original indices, which is O(n log n) time. For the optimal solution, I'd use a hash map to store each number's index as I iterate. For each nums[i], calculate complement = target - nums[i], and check if complement is already in the map. If it is, return [map.get(complement), i]; otherwise, put nums[i] → i in the map. This is a single pass, O(n) time and O(n) space thanks to the map's constant-time lookups. It handles duplicates fine since we add after checking, and works with negatives or zeros. For example, with [2,7,11,15] and target 9, we'd see 2 (add 2:0), then 7 (complement 2 exists, return [0,1]). In JS, Map is perfect for this as it handles any key type." "तो, टू सम के लिए, लक्ष्य ऐरे में दो इंडेक्स ढूंढना है जो टारगेट तक जोड़ें, और हम मानते हैं कि ठीक एक सॉल्यूशन है। सबसे पहले, ब्रूट फोर्स अप्रोच: मैं दो नेस्टेड लूप्स यूज करूंगा—आउटर i 0 से n-1 तक, इनर j i+1 से n-1 तक, और चेक अगर nums[i] + nums[j] टारगेट के बराबर है। अगर हां, [i, j] रिटर्न। यह O(n²) टाइम और O(1) स्पेस है—कोड करने में आसान लेकिन बड़े ऐरे के लिए बहुत धीमा। दूसरा तरीका ऐरे को इंडेक्स के साथ सॉर्ट करना, फिर लेफ्ट और राइट से टू पॉइंटर्स, सम के आधार पर अडजस्ट, लेकिन ओरिजिनल इंडेक्स मैप बैक करने पड़ेंगे, जो O(n log n) टाइम है। ऑप्टिमल सॉल्यूशन के लिए, मैं हैश मैप यूज करूंगा जो इटरेट करते हुए हर नंबर का इंडेक्स स्टोर करे। हर nums[i] के लिए, complement = target - nums[i] कैलकुलेट, और चेक अगर complement मैप में पहले से है। अगर है, तो [map.get(complement), i] रिटर्न; वरना, nums[i] → i मैप में डाल दें। यह सिंगल पास है, O(n) टाइम और O(n) स्पेस मैप के कांस्टेंट-टाइम लुकअप्स की वजह से। यह डुप्लिकेट्स को फाइन हैंडल करता है क्योंकि चेक के बाद ऐड करते हैं, और नेगेटिव्स या जीरो के साथ काम करता है। उदाहरण के लिए, [2,7,11,15] और टारगेट 9 के साथ, 2 देखेंगे (2:0 ऐड), फिर 7 (complement 2 exists, [0,1] रिटर्न)। जेएस में, मैप इसके लिए परफेक्ट है क्योंकि कोई भी की टाइप हैंडल करता है।"

Contains Duplicate (LC 217) - LeetCode कंटेन्स डुप्लिकेट (LC 217) - लीटकोड

Problem: Return true if array has duplicate. समस्या: अगर ऐरे में डुप्लिकेट है तो ट्रू रिटर्न करें।

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

  • Primary: Array & Hashing
  • Secondary: Hash Set for Uniqueness
  • Frequency: Medium (Common in mid-size startups)

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

  • Big O: O(n) time, O(n) space optimized.
  • Edge: Empty/single element false, negatives.
  • Self: Sets for uniqueness; sort if space tight.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Array sorted? Element types (primitives/objects)? n up to what? Return any duplicate or just boolean?" Quick heuristic: "Is this about uniqueness or frequency? Hints ordering (maybe sort), adjacency (no), prefix (no), structure (set for seen check)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "क्या ऐरे सॉर्टेड? एलिमेंट टाइप्स (प्रिमिटिव्स/ऑब्जेक्ट्स)? n तक क्या? कोई डुप्लिकेट रिटर्न या जस्ट बूलियन?" क्विक ह्यूरिस्टिक: "क्या यह यूनिकनेस या फ्रीक्वेंसी के बारे में? हिन्ट्स ऑर्डरिंग (शायद सॉर्ट), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (सेट सीन चेक के लिए)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"return true if any duplicate" Boolean only? Large n? Modifiable array? Hash Set for O(1) seen check Breakdown: Brute pairs → Optimize with tracking seen. Ask: Space constraints?
"array contains duplicate" Sorted input? Negatives/floats? Array & Hashing, fallback to sort Think: Time vs space? Set for speed, sort for O(1) space.

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

  • Brute Force (Nested Loops): Two nested loops to compare every pair of elements. For i from 0 to n-1, j from i+1 to n-1, if nums[i] === nums[j], return true. O(n²) time, O(1) space—simple but inefficient.
  • Sorting: Sort the array in-place, then iterate once checking if adjacent elements are equal. O(n log n) time, O(1) space if sorting modifies the original—good if space is a concern.
  • Hash Set (Optimal): Iterate through the array, adding each element to a Set. If the element already exists in the Set before adding, return true. Single pass, O(n) time and O(n) space with O(1) lookups.

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

Javascript
// Brute Force (Nested Loops): Compare every pair
function containsDuplicate(nums) {
  // Outer loop for first element
  for (let i = 0; i < nums.length; i++) {
    // Inner loop for comparisons
    for (let j = i + 1; j < nums.length; j++) {
      // If match, duplicate found
      if (nums[i] === nums[j]) {
        return true;
      }
    }
  }
  // No duplicates
  return false;
}
// Time: O(n^2) - quadratic, bad for big n, Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple nested loops, no extra space.
  • Works for any element type.
  • O(n²) time, impractical for large arrays.

Optimized Solution (Hash Set) ऑप्टिमाइज्ड सॉल्यूशन (हैश सेट)

Javascript
// Optimized (Hash Set): Track seen elements for O(1) checks
function containsDuplicate(nums) {
  // Create Set to track seen numbers
  const seen = new Set();
  // Loop through array
  for (let num of nums) {
    // If already in Set, duplicate
    if (seen.has(num)) {
      return true;
    }
    // Add to Set
    seen.add(num);
  }
  // No duplicates
  return false;
}
// Time: O(n) - linear scan, Space: O(n) - Set size up to n
Why This Solution? यह सॉल्यूशन क्यों?
  • O(n) time with Set for O(1) checks.
  • Efficient for large arrays, O(n) space.
  • Preferred in interviews for speed.

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

Brute force is nested loops comparing pairs — O(n²), correct but slow. Sorting works in O(n log n) by checking adjacents after sort. But hash set is optimal O(n): track seen elements and return on duplicate. Here's the code. ब्रूट फोर्स नेस्टेड लूप्स पेयर्स कंपेयर — O(n²), सही लेकिन धीमा। सॉर्टिंग O(n log n) में एडजेसेंट्स चेक सॉर्ट बाद। लेकिन हैश सेट ऑप्टिमल O(n): देखे एलिमेंट्स ट्रैक और डुप्लिकेट पर रिटर्न। यहाँ कोड।

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

"The problem is to check if any duplicate exists in the array—return true if yes. Starting with brute force: Nested loops to compare every pair, like i from 0 to n-1 and j > i, if equal return true. That's O(n²) time, O(1) space—correct but scales poorly. A better alternative: Sort the array first, then scan adjacent elements for equality, O(n log n) time and O(1) extra space if in-place. For optimal, I'd use a Set to track seen elements. Iterate once: for each num, if Set.has(num), return true; else Set.add(num). If we finish without finding one, return false. This is O(n) time and space, leveraging the Set's O(1) operations. It works great for negatives or any primitives. Edges like empty array or single element return false. In JS, Set is hash-based, so it's fast and handles collisions well." "समस्या ऐरे में कोई डुप्लिकेट चेक करना है—हां तो ट्रू रिटर्न। ब्रूट फोर्स से शुरू: नेस्टेड लूप्स हर पेयर कंपेयर, जैसे i 0 से n-1 और j > i, बराबर तो ट्रू। O(n²) टाइम, O(1) स्पेस—सही लेकिन बड़े के लिए स्केल नहीं। बेहतर वैकल्पिक: पहले ऐरे सॉर्ट, फिर एडजेसेंट चेक, O(n log n) टाइम और O(1) एक्स्ट्रा स्पेस अगर इन-प्लेस। ऑप्टिमल के लिए, सेट यूज देखे गए एलिमेंट्स ट्रैक। एक बार इटरेट: हर num के लिए, अगर Set.has(num), ट्रू रिटर्न; वरना Set.add(num)। खत्म बिना मिले तो फॉल्स। O(n) टाइम और स्पेस, सेट के O(1) ऑपरेशन्स से। नेगेटिव्स या प्रिमिटिव्स के लिए शानदार। एज जैसे खाली ऐरे या सिंगल एलिमेंट फॉल्स। जेएस में, सेट हैश-बेस्ड है, फास्ट और कोलिजन्स हैंडल करता।"

Valid Anagram (LC 242) - LeetCode वैलिड एनाग्राम (LC 242) - लीटकोड

Problem: Check if s and t are anagrams (same letters, counts). समस्या: चेक करें अगर s और t एनाग्राम हैं (एक ही लेटर्स, काउंट्स)।

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

  • Primary: Array & Hashing, String Frequency
  • Secondary: Sorting
  • Frequency: Medium (Common in string manipulation rounds)

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

  • Big O: O(n) time, O(1) space for fixed charset (26 letters).
  • Edge: Different lengths false, empty true, case-sensitive? (assume lowercase).

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Case-sensitive? Only lowercase letters? Lengths up to? Unicode or ASCII?" Quick heuristic: "Is this about character frequency matching? Hints ordering (sort), adjacency (no), prefix (no), structure (count array/map)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "केस-सेंसिटिव? सिर्फ लोअरकेस? लेंथ्स तक? यूनिकोड या ASCII?" क्विक ह्यूरिस्टिक: "क्या यह कैरेक्टर फ्रीक्वेंसी मैचिंग के बारे में? हिन्ट्स ऑर्डरिंग (सॉर्ट), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (काउंट ऐरे/मैप)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"same characters same frequencies" Lengths equal? Charset size? Case? Hash Map or Fixed Array for counts Breakdown: Sort compare → Optimize with counts. Ask: Fixed alphabet?
"anagram", "rearrangement" Empty strings? Special chars? String Frequency, fallback sort Think: O(1) space if 26 letters? Use array indices.

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

  • Sorting (Simple): First check if lengths differ—if yes, false. Sort both strings and compare if equal. O(n log n) time due to sort, O(n) space for sorted copies—easy but not linear time.
  • Two Hash Maps: Use two Maps or counters: one for s, one for t. Iterate each string to count frequencies, then compare the maps. O(n) time, O(n) space—clear and handles any charset.
  • Single Array (Optimal): Assuming lowercase English letters, use a fixed-size array of 26 zeros. Iterate both strings in parallel: increment for s's char, decrement for t's. If lengths match and final array all zeros, true. O(n) time, O(1) space.
Approach Time Space When to Use
Sort O(n log n) O(n) Simple, no extra structures
Two Maps O(n) O(n) Clear for interviews
One Array O(n) O(1) for alphabet Best for constraints

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

Javascript
// Sorting Approach (Non-Optimized): Sort and compare strings
function isAnagram(s, t) {
  // Quick length check - if different, not anagram
  if (s.length !== t.length) return false;
  // Sort both strings into arrays
  const sortedS = s.split('').sort().join('');
  const sortedT = t.split('').sort().join('');
  // Compare sorted versions
  return sortedS === sortedT;
}
// Time: O(n log n) - due to sort, Space: O(n) - new arrays
Why This Solution? यह सॉल्यूशन क्यों?
  • Sorting simplifies comparison to equality check.
  • Built-in sort, no complex logic.
  • O(n log n) time, suitable for small strings.

Optimized Solution (Fixed Array Count) ऑप्टिमाइज्ड सॉल्यूशन (फिक्स्ड ऐरे काउंट)

Javascript
// Optimized (Fixed Array Count): Frequency array for O(1) space
function isAnagram(s, t) {
  // Length check
  if (s.length !== t.length) return false;
  // Array of 26 zeros for a-z
  const count = new Array(26).fill(0);
  // Loop: Increment for s, decrement for t
  for (let i = 0; i < s.length; i++) {
    // 'a'.charCodeAt(0) = 97, so index = char - 'a'
    count[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
    count[t.charCodeAt(i) - 'a'.charCodeAt(0)]--;
  }
  // Check if all zero
  return count.every(c => c === 0);
}
// Time: O(n) - single loop, Space: O(1) - fixed array
Why This Solution? यह सॉल्यूशन क्यों?
  • O(n) time, O(1) space for fixed alphabet.
  • Single array tracks counts efficiently.
  • Ideal for interviews, handles lowercase.

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

Sorting both strings and comparing is simple — O(n log n), but not linear. Two maps for counts work in O(n), but for lowercase letters, fixed array is optimal O(n) with O(1) space. Implementation below. दोनों स्ट्रिंग्स सॉर्ट और कंपेयर सरल — O(n log n), लेकिन लीनियर नहीं। टू मैप्स काउंट्स O(n) में काम, लेकिन लोअरकेस के लिए फिक्स्ड ऐरे ऑप्टिमल O(n) O(1) स्पेस। नीचे इम्प्लीमेंटेशन।

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

"To check if two strings are anagrams—same characters with same frequencies—first, always check if lengths differ; if so, return false right away. A simple way: Convert both to arrays, sort them, and compare the sorted versions for equality. That's O(n log n) time from sorting and O(n) space for the copies—quick to implement but not optimal. For linear time, we could use two hash maps: one to count chars in s, another for t, then iterate the maps to ensure counts match, O(n) time and space. But since the problem likely assumes lowercase English letters, the best is a fixed array of size 26 initialized to zero. Loop through both strings simultaneously: for each char in s, increment count[char - 'a']; for t, decrement. After the loop, check if every count is zero—if yes, they're anagrams. This is O(n) time and O(1) space because the array size is constant. Empty strings are anagrams (true), and it handles case by assuming lowercase. If it were full Unicode, I'd fall back to a Map. In JS, charCodeAt(0) for 'a' makes indexing clean." "दो स्ट्रिंग्स एनाग्राम हैं चेक करने के लिए—एक ही कैरेक्टर्स समान फ्रीक्वेंसी के साथ—पहले, हमेशा चेक करें अगर लेंथ्स अलग हैं; अगर हां, तुरंत फॉल्स। सरल तरीका: दोनों को ऐरे में कन्वर्ट, सॉर्ट, और सॉर्टेड वर्जन्स कंपेयर इक्वल। O(n log n) टाइम सॉर्टिंग से और O(n) स्पेस कॉपीज के लिए—इम्प्लीमेंट करने में तेज लेकिन ऑप्टिमल नहीं। लीनियर टाइम के लिए, दो हैश मैप्स: s में कैर काउंट एक, t में दूसरा, फिर मैप्स इटरेट मैच सुनिश्चित, O(n) टाइम और स्पेस। लेकिन प्रॉब्लम लोअरकेस इंग्लिश लेटर्स मानता है, तो बेस्ट फिक्स्ड 26 साइज ऐरे जीरो से इनिशियलाइज। दोनों स्ट्रिंग्स समानांतर लूप: s के हर कैर के लिए count[char - 'a'] इंक्रीमेंट; t के लिए डेक्रीमेंट। लूप बाद, हर काउंट जीरो चेक—हां तो एनाग्राम। O(n) टाइम और O(1) स्पेस क्योंकि ऐरे साइज कांस्टेंट। खाली स्ट्रिंग्स एनाग्राम (ट्रू), और केस हैंडल लोअरकेस से। अगर फुल यूनिकोड, मैप पर फॉल बैक। जेएस में, charCodeAt(0) 'a' के लिए इंडेक्सिंग क्लीन।"

Product of Array Except Self (LC 238) - LeetCode प्रोडक्ट ऑफ ऐरे एक्सेप्ट सेल्फ (LC 238) - लीटकोड

Problem: Return array where each is product of all except itself, no division. समस्या: ऐरे रिटर्न करें जहां हर एक सभी के प्रोडक्ट है खुद को छोड़कर, बिना डिवीजन।

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

  • Primary: Array, Prefix/Suffix
  • Secondary: No Division
  • Frequency: High (FAANG on-site common)

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

  • Big O: O(n) time, O(1) space (output separate).
  • Edge: Zeros (multiple zeros → all zero except positions).
  • Self: Prefix/suffix products; handle zeros carefully.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Division allowed? Zeros present? n up to? Output modify input?" Quick heuristic: "Is this about products excluding self? Hints ordering (no), adjacency (no), prefix (yes, left/right products), structure (two passes)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "डिवीजन अलाउड? जीरोस प्रेजेंट? n तक? आउटपुट इनपुट मॉडिफाई?" क्विक ह्यूरिस्टिक: "क्या यह सेल्फ एक्सक्लूड प्रोडक्ट्स के बारे में? हिन्ट्स ऑर्डरिंग (नहीं), एडजेसेंसी (नहीं), प्रीफिक्स (हां, लेफ्ट/राइट), स्ट्रक्चर (टू पास)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"product of all except itself", "no division" Zeros? Large numbers (overflow)? Prefix/Suffix Arrays Breakdown: Brute multiply → Prefix left, suffix right multiply. Ask: Handle zeros?
"array", "except self" Modify input? n=1? Array Prefix, O(1) extra space Think: Two passes to avoid extra space.

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

  • Brute Force (Nested Loops): For each index i, iterate through the array multiplying all elements except i. O(n²) time, O(1) extra space—direct but quadratic.
  • Division (Invalid Here): Compute total product of all elements, then for each i, result[i] = total / nums[i]. O(n) time, but forbidden by constraints and fails with zeros (division by zero).
  • Prefix/Suffix Products (Optimal): First pass left-to-right to compute prefix products (left of i), store in result. Second pass right-to-left to multiply suffix products (right of i) into result. O(n) time, O(1) extra space excluding output.

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

Javascript
// Brute Force (Nested Loops): Multiply all others for each index
function productExceptSelf(nums) {
  const result = [];
  // Loop for each position
  for (let i = 0; i < nums.length; i++) {
    let product = 1;
    // Inner loop: Multiply everything except i
    for (let j = 0; j < nums.length; j++) {
      if (i !== j) {
        product *= nums[j];
      }
    }
    // Push to result
    result.push(product);
  }
  return result;
}
// Time: O(n^2) - nested, Space: O(1) besides output
Why This Solution? यह सॉल्यूशन क्यों?
  • Directly computes products, no division.
  • Simple logic, no edge case handling.
  • O(n²) time, not scalable for large n.

Optimized Solution (Prefix/Suffix) ऑप्टिमाइज्ड सॉल्यूशन (प्रीफिक्स/सफिक्स)

Javascript
// Optimized (Prefix/Suffix Products): Two passes for left/right products
function productExceptSelf(nums) {
  const n = nums.length;
  // Result array starts as prefix products
  const result = new Array(n).fill(1);
  // Prefix: Left-to-right cumulative product
  let prefix = 1;
  for (let i = 1; i < n; i++) {
    prefix *= nums[i - 1]; // Update prefix
    result[i] = prefix; // Set result[i] to prefix product
  }
  // Suffix: Right-to-left cumulative
  let suffix = 1;
  for (let i = n - 2; i >= 0; i--) {
    suffix *= nums[i + 1]; // Update suffix
    result[i] *= suffix; // Multiply with existing prefix
  }
  return result;
}
// Time: O(n) - three passes, Space: O(1) output aside
Why This Solution? यह सॉल्यूशन क्यों?
  • O(n) time, O(1) space excluding output.
  • Handles zeros without division.
  • Two-pass prefix/suffix, interview-friendly.

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

Brute force multiplies others per index — O(n²), too slow. Division is O(n) but banned and fails on zeros. Prefix/suffix products in two passes is optimal O(n), O(1) space. Code follows. ब्रूट फोर्स प्रति इंडेक्स अन्य मल्टिप्लाई — O(n²), धीमा। डिवीजन O(n) लेकिन बैन और जीरो पर फेल। टू पास में प्रीफिक्स/सफिक्स प्रोडक्ट्स ऑप्टिमल O(n), O(1) स्पेस। कोड आगे।

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

"The task is to return an array where each element is the product of all others, without using division. Brute force: For every index i, loop through the array multiplying everything except nums[i]—that's O(n²) time and O(1) space, correct but too slow. A naive optimization might be to compute the total product once, then divide for each, but that's banned and breaks on zeros. Instead, for optimal, we do two passes: First, left-to-right to fill result with prefix products—result[0] = 1, result[i] = result[i-1] * nums[i-1]. This gives products to the left of i. Then, right-to-left: Start suffix = 1, for i from n-2 to 0, suffix *= nums[i+1], then result[i] *= suffix. Now result[i] has left * right products. Total O(n) time, O(1) extra space (output doesn't count). It naturally handles zeros—if there's one zero, the product is zero everywhere except at that zero's position (which is 1 * right product). Multiple zeros make everything zero. In JS, be mindful of integer overflow, but for interviews, this two-pass method shows good thinking on space tradeoffs." "कार्य खुद को छोड़कर सभी के प्रोडक्ट्स का ऐरे रिटर्न, बिना डिवीजन। ब्रूट फोर्स: हर i के लिए, ऐरे लूप मल्टिप्लाई सब nums[i] को छोड़कर—O(n²) टाइम और O(1) स्पेस, सही लेकिन धीमा। नेव अप्टिमाइजेशन टोटल प्रोडक्ट एक बार, फिर हर के लिए डिवाइड, लेकिन बैन और जीरो पर ब्रेक। इसके बजाय, ऑप्टिमल दो पास: पहला लेफ्ट-टू-राइट रिजल्ट प्रीफिक्स प्रोडक्ट्स से भरें—result[0] = 1, result[i] = result[i-1] * nums[i-1]। यह i के लेफ्ट प्रोडक्ट्स देता। फिर राइट-टू-लेफ्ट: suffix = 1 शुरू, i n-2 से 0, suffix *= nums[i+1], फिर result[i] *= suffix। अब result[i] में लेफ्ट * राइट। टोटल O(n) टाइम, O(1) एक्स्ट्रा स्पेस (आउटपुट काउंट नहीं)। जीरो नैचुरली हैंडल—एक जीरो तो सब जीरो एक्सेप्ट जीरो पोजीशन (1 * राइट), मल्टिपल तो सब जीरो। जेएस में, इंट ओवरफ्लो ध्यान, लेकिन इंटरव्यू में यह टू-पास स्पेस ट्रेडऑफ्स पर अच्छा थिंकिंग दिखाता।"

Strings (Days 3-4) स्ट्रिंग्स (दिन 3-4)

Strings in JS are immutable; use arrays for mutation. Focus on sliding windows, two pointers. जेएस में स्ट्रिंग्स इम्यूटेबल हैं; म्यूटेशन के लिए ऐरे यूज करें। फोकस स्लाइडिंग विंडोज, टू पॉइंटर्स पर।

Longest Substring Without Repeating Characters (LC 3) - LeetCode लॉन्गेस्ट सबस्ट्रिंग विदाउट रिपीटिंग कैरेक्टर्स (LC 3) - लीटकोड

Problem: Find length of longest substring no repeats. समस्या: सबसे लंबी सबस्ट्रिंग की लेंथ ढूंढें बिना रिपीट्स।

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

  • Primary: String, Sliding Window
  • Secondary: Hash Map for Last Index
  • Frequency: High (FAANG string classic)

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

  • Big O: O(n) time, O(min(n, charset)) space.
  • Edge: Empty "", all unique, all same.
  • Self: Sliding window + Map; update start on duplicate.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Return length or substring? Charset size? n up to? Contiguous substring?" Quick heuristic: "Is this about max length without repeats? Hints ordering (window), adjacency (yes), prefix (no), structure (map for positions)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "लेंथ या सबस्ट्रिंग रिटर्न? चारसेट साइज? n तक? कंटिगुअस सबस्ट्रिंग?" क्विक ह्यूरिस्टिक: "क्या यह रिपीट्स बिना मैक्स लेंथ के बारे में? हिन्ट्स ऑर्डरिंग (विंडो), एडजेसेंसी (हां), प्रीफिक्स (नहीं), स्ट्रक्चर (मैप पोजीशन्स के लिए)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"longest substring without repeating" Contiguous? Length only? Sliding Window with Hash Breakdown: Brute substrings → Window shrink on duplicate. Ask: All unique chars?
"substring", "no repeating characters" Charset (26/256)? n=10^4? String Sliding Window Think: Track last seen to jump left pointer.

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

  • Brute Force (Nested Loops): Nested loops: outer for start i, inner for end j >= i, use a Set to track unique chars in s[i..j]. Break inner if duplicate, update max length. O(n²) time worst-case, O(n) space for Set.
  • Sliding Window with Set: Maintain a window [left, right], expand right, if duplicate, shrink left until no duplicate using a Set for current window chars. Update max at each step. Still O(n²) in worst case but better average.
  • Sliding Window with Map (Optimal): Use a Map for char to last index seen. Expand right, if s[right] seen and index >= left, set left = lastIndex + 1. Update max = right - left + 1. O(n) time as each char processed at most twice.

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

Javascript
// Brute Force (Nested Loops): Check every possible substring with Set
function lengthOfLongestSubstring(s) {
  let max = 0;
  // Outer: Start index
  for (let i = 0; i < s.length; i++) {
    // Set for unique in current substring
    const seen = new Set();
    // Inner: Extend from i
    for (let j = i; j < s.length; j++) {
      if (seen.has(s[j])) break; // Duplicate, stop
      seen.add(s[j]); // Add
      max = Math.max(max, j - i + 1); // Update max
    }
  }
  return max;
}
// Time: O(n^2) - nested, Space: O(n) worst Set
Why This Solution? यह सॉल्यूशन क्यों?
  • Checks all substrings, ensures correctness.
  • Set for O(1) duplicate checks in window.
  • O(n²) time, only for small strings.

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

Javascript
// Optimized (Sliding Window with Hash Set): Expand/shrink window on duplicates
function lengthOfLongestSubstring(s) {
  let max = 0;
  const seen = new Set(); // Track unique chars in window
  let left = 0; // Left pointer
  // Right pointer loops
  for (let right = 0; right < s.length; right++) {
    // While duplicate, remove from left and move left
    while (seen.has(s[right])) {
      seen.delete(s[left]); // Remove left char
      left++; // Shrink window
    }
    // Add right char
    seen.add(s[right]);
    // Update max length
    max = Math.max(max, right - left + 1);
  }
  return max;
}
// Time: O(n) - each char added/removed once, Space: O(min(n, charset))
Why This Solution? यह सॉल्यूशन क्यों?
  • O(n) time, chars visited at most twice.
  • Map tracks last seen index, optimizes window.
  • Scales well, interview-preferred.

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

Brute force checks all substrings with sets — O(n²), inefficient. Basic sliding window can be O(n²) worst. Optimized sliding window with last index map is O(n): jump left on duplicate. Code here. ब्रूट फोर्स सभी सबस्ट्रिंग्स सेट्स से चेक — O(n²), इनएफिशिएंट। बेसिक स्लाइडिंग विंडो वर्स्ट O(n²)। लास्ट इंडेक्स मैप से ऑप्टिमाइज्ड विंडो O(n): डुप्लिकेट पर लेफ्ट जंप। कोड यहाँ।

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

"We need the length of the longest substring without repeating characters. Brute force: For each possible start i, extend j from i, using a Set to add chars—if duplicate, break and update max length j-i+1. That's O(n²) time since inner loop can run n times per i. To optimize, use a sliding window: left and right pointers, a Set for current window. Expand right, while duplicate (Set.has(s[right])), delete s[left] and increment left. Add s[right], update max. But this can still be O(n²) worst-case if left moves a lot. The linear solution: Use a Map. Initialize left=0, max=0. For right=0 to n-1: if s[right] in Map and Map[s[right]] >= left, set left = Map[s[right]] + 1. Update Map[s[right]]=right, then max = Math.max(max, right-left+1). This is O(n) because left only moves forward, and each char is updated/checked once effectively. Examples: 'abc' → 3, 'pwwkew' → 3 ('wke'). Space O(min(n, charset size)). In JS, Map or even object works, but Map is cleaner for strings." "हमें बिना रिपीटिंग कैरेक्टर्स की सबसे लंबी सबस्ट्रिंग की लेंथ चाहिए। ब्रूट फोर्स: हर पॉसिबल स्टार्ट i के लिए, j i से एक्सटेंड, सेट यूज कैर ऐड—डुप्लिकेट तो ब्रेक और मैक्स j-i+1 अपडेट। O(n²) टाइम क्योंकि इनर n बार i प्रति। ऑप्टिमाइज के लिए, स्लाइडिंग विंडो: लेफ्ट राइट पॉइंटर्स, सेट करेंट विंडो के लिए। राइट एक्सपैंड, जबकि डुप्लिकेट (Set.has(s[right])), s[left] डिलीट और लेफ्ट++, ऐड s[right], मैक्स अपडेट। लेकिन वर्स्ट O(n²) अगर लेफ्ट बहुत मूव। लीनियर सॉल्यूशन: मैप<कैर, लास्टइंडेक्स>। left=0, max=0 इनिश। राइट 0 से n-1: अगर s[right] मैप में और >=left, left = मैप[s[right]] +1। मैप[s[right]]=राइट अपडेट, max = Math.max(max, right-left+1)। O(n) क्योंकि लेफ्ट फॉरवर्ड मूव, हर कैर अपडेट/चेक एक बार। उदाहरण: 'abc' → 3, 'pwwkew' → 3 ('wke')। स्पेस O(min(n, charset))। जेएस में, मैप या ऑब्जेक्ट, लेकिन मैप स्ट्रिंग्स के लिए क्लीनर।"

Valid Palindrome (LC 125) - LeetCode वैलिड पैलिंड्रोम (LC 125) - लीटकोड

Problem: Is string palindrome ignoring non-alphanum, case. समस्या: स्ट्रिंग पैलिंड्रोम है नॉन-एल्फान्यूम, केस इग्नोर करके।

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

  • Primary: String, Two Pointers
  • Secondary: Palindrome Check
  • Frequency: Medium (Basic string round)

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

  • Big O: O(n) time, O(1) space.
  • Edge: Empty true, single true, punctuation.
  • Self: Two pointers, skip non-alphanum, lowercase compare.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Ignore case? Only alphanum? Punctuation? Empty valid?" Quick heuristic: "Is this palindrome validation? Hints ordering (two pointers), adjacency (no), prefix (no), structure (inward scan)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "केस इग्नोर? सिर्फ अल्फान्यूम? पंक्चुएशन? खाली वैलिड?" क्विक ह्यूरिस्टिक: "क्या यह पैलिंड्रोम वैलिडेशन? हिन्ट्स ऑर्डरिंग (टू पॉइंटर्स), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (इनवर्ड स्कैन)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"palindrome ignoring case, non-alphanum" What counts as valid char? Case? Two Pointers Inward Breakdown: Clean reverse → Pointers skip invalid. Ask: Regex for alphanum?
"valid palindrome" n up to? Unicode? String Two Pointers Think: O(1) space by scanning ends to center.

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

  • Clean and Reverse: Filter out non-alphanumeric chars, convert to lowercase, create a reversed copy, and compare. O(n) time, O(n) space for new strings—straightforward but uses extra space.
  • Two Pointers (Optimal): Start left at 0, right at end-1. While left < right, skip non-alphanum by incrementing left or decrementing right, then compare lowercase chars. If mismatch, false; else move inward. O(n) time, O(1) space.

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

Javascript
// Non-Optimized (Clean and Reverse): Filter and reverse full string
function isPalindrome(s) {
  // Filter alphanum, lowercase
  const cleaned = s.toLowerCase().split('').filter(c => /[a-z0-9]/.test(c)).join('');
  // Reverse copy
  const reversed = cleaned.split('').reverse().join('');
  // Compare
  return cleaned === reversed;
}
// Time: O(n) - linear, Space: O(n) - new strings
Why This Solution? यह सॉल्यूशन क्यों?
  • Cleans string with regex for easy check.
  • O(n) space due to new string creation.
  • Simple but not space-efficient.

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

Javascript
// Optimized (Two Pointers): Inward scan skipping invalid chars
function isPalindrome(s) {
  s = s.toLowerCase(); // Lowercase once
  let left = 0, right = s.length - 1; // Pointers
  while (left < right) {
    // Skip non-alphanum left
    while (left < right && !/[a-z0-9]/.test(s[left])) left++;
    // Skip right
    while (left < right && !/[a-z0-9]/.test(s[right])) right--;
    // Compare
    if (s[left] !== s[right]) return false;
    left++; right--; // Move inward
  }
  return true;
}
// Time: O(n) - scan once, Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • O(1) space, no string allocation.
  • Two pointers skip invalid chars fast.
  • Interview-preferred for efficiency.

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

Clean and reverse the string after filtering — O(n) time/space, easy. But two pointers scanning inward while skipping non-alphanum is optimal O(n), O(1) space. Here's the implementation. फिल्टर बाद स्ट्रिंग क्लीन एंड रिवर्स — O(n) टाइम/स्पेस, आसान। लेकिन नॉन-अल्फान्यूम स्किप करते इनवर्ड टू पॉइंटर्स ऑप्टिमल O(n), O(1) स्पेस। इम्प्लीमेंटेशन यहाँ।

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

"To validate a palindrome ignoring case and non-alphanumeric characters, one easy way: Use regex to filter only alphanum, lowercase it, reverse the cleaned string, and check equality. That's O(n) time and space—simple, but we create extra strings. For space efficiency, use two pointers: left starts at 0, right at s.length-1. While left < right, if s[left] isn't alphanum, increment left; same for right, decrement. Then, compare s[left].toLowerCase() and s[right].toLowerCase()—if not equal, return false; else left++, right--. If we cross without mismatch, it's true. Still O(n) time since each char visited once, but O(1) space. Great for edges like empty string (true) or 'A man, a plan, a canal: Panama' (true after cleaning). The pointers simulate cleaning without allocating. In JS, regex /[a-z0-9]/i works, but since we lowercase first, /[a-z0-9]/ is fine." "केस और नॉन-एल्फान्यूम इग्नोर करके पैलिंड्रोम वैलिडेट करने के लिए, आसान तरीका: रेगेक्स से सिर्फ एल्फान्यूम फिल्टर, लोअरकेस, क्लीन स्ट्रिंग रिवर्स, और इक्वल चेक। O(n) टाइम और स्पेस—सरल, लेकिन एक्स्ट्रा स्ट्रिंग्स क्रिएट। स्पेस एफिशिएंसी के लिए, टू पॉइंटर्स: लेफ्ट 0 पर, राइट s.length-1। जबकि left < right, अगर s[left] नॉन-एल्फान्यूम, left++; राइट के लिए decrement। फिर, s[left].toLowerCase() और s[right].toLowerCase() कंपेयर—न बराबर तो फॉल्स; वरना left++, right--। क्रॉस बिना मिसमैच तो ट्रू। अभी भी O(n) टाइम हर कैर एक बार, लेकिन O(1) स्पेस। एज जैसे खाली (ट्रू) या 'A man, a plan, a canal: Panama' (क्लीनिंग बाद ट्रू)। पॉइंटर्स सिमुलेट क्लीनिंग बिना अलोकेट। जेएस में, रेगेक्स /[a-z0-9]/i, लेकिन लोअरकेस पहले तो /[a-z0-9]/ फाइन।"

Longest Palindromic Substring (LC 5) - LeetCode लॉन्गेस्ट पैलिंड्रोमिक सबस्ट्रिंग (LC 5) - लीटकोड

Problem: Find longest palindrome substring. समस्या: सबसे लंबी पैलिंड्रोम सबस्ट्रिंग ढूंढें।

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

  • Primary: String, Expand Around Centers
  • Secondary: DP for Palindromes
  • Frequency: High (String DP variant)

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

  • Big O: O(n²) time, O(1) space.
  • Edge: Single char, even/odd length.
  • Self: Expand around centers; check all positions.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Return substring or length? Contiguous? Case-sensitive? n up to?" Quick heuristic: "Is this longest palindrome? Hints ordering (expand), adjacency (yes), prefix (no), structure (centers)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "सबस्ट्रिंग या लेंथ रिटर्न? कंटिगुअस? केस-सेंसिटिव? n तक?" क्विक ह्यूरिस्टिक: "क्या यह लॉन्गेस्ट पैलिंड्रोम? हिन्ट्स ऑर्डरिंग (एक्सपैंड), एडजेसेंसी (हां), प्रीफिक्स (नहीं), स्ट्रक्चर (सेंटर्स)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"longest palindromic substring" Substring or length? Odd/even? Expand Around Centers Breakdown: Brute all subs → Expand from 2n centers. Ask: Multiple same length?
"palindrome", "substring" n=1000? Case? String Expansion Think: O(n^2) acceptable; avoid full DP space.

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

  • Brute Force (Nested Loops + Reverse): Generate all substrings (nested loops i to j), check if palindrome by reversing and comparing. O(n³) time (n² substrings * n reverse), O(1) space—too slow.
  • Dynamic Programming: 2D table dp[i][j] true if s[i..j] palindrome. Fill based on lengths: singles true, adjacents if equal, longer if ends equal and inner true. O(n²) time and space.
  • Expand Around Centers (Optimal Space): For each i, expand around i (odd) and i,i+1 (even): while bounds valid and chars match, expand left/right. Track longest substring. O(n²) time (n centers * O(n) expand), O(1) space.

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

Javascript
// Brute Force (Nested Loops + Reverse Check): All substrings
function longestPalindrome(s) {
  let longest = '';
  // Helper: Is substring palindrome?
  function isPal(sub) {
    return sub === sub.split('').reverse().join('');
  }
  // All substrings
  for (let i = 0; i < s.length; i++) {
    for (let j = i + 1; j <= s.length; j++) {
      const sub = s.slice(i, j);
      if (isPal(sub) && sub.length > longest.length) {
        longest = sub;
      }
    }
  }
  return longest;
}
// Time: O(n^3) - slices + reverses, Space: O(1) main
Why This Solution? यह सॉल्यूशन क्यों?
  • Exhaustive, checks all substrings.
  • Reverse check ensures correctness.
  • O(n³) time, impractical for large n.

Optimized Solution (Expand Around Centers) ऑप्टिमाइज्ड सॉल्यूशन (एक्सपैंड अराउंड सेंटर्स)

Javascript
// Optimized (Expand Around Centers): Check from each potential center
function longestPalindrome(s) {
  let longest = '';
  // Helper: Expand from left/right
  function expand(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      // If longer, update
      if (right - left + 1 > longest.length) {
        longest = s.slice(left, right + 1);
      }
      left--; right++; // Expand
    }
  }
  // For each possible center
  for (let i = 0; i < s.length; i++) {
    expand(i, i); // Odd length
    expand(i, i + 1); // Even length
  }
  return longest;
}
// Time: O(n^2) - n centers * O(n) expand, Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • O(n²) time, O(1) space, efficient expansion.
  • Handles odd/even palindromes cleanly.
  • Interview-preferred for balance.

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

Brute force checks all substrings by reverse — O(n³), way too slow. DP table is O(n²) time/space. Expand around centers is optimal O(n²) time, O(1) space using palindrome symmetry. See code. ब्रूट फोर्स सभी सबस्ट्रिंग्स रिवर्स से चेक — O(n³), बहुत धीमा। डीपी टेबल O(n²) टाइम/स्पेस। सेंटर्स अराउंड एक्सपैंड पैलिंड्रोम सिमेट्री से ऑप्टिमल O(n²) टाइम, O(1) स्पेस। कोड देखें।

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

"The goal is to find the longest palindromic substring. Brute force: Check every possible substring s[i..j] by reversing it and comparing—O(n³) time, way too slow. DP approach: Use a 2D boolean table where dp[i][j] is true if substring i to j is palindrome. Initialize diagonals true, then for length 2 if equal true, longer lengths if s[i]==s[j] and dp[i+1][j-1] true. Track max length and substring, O(n²) time and space—solid but space-heavy. For better space, expand around centers: Every index i is a potential center for odd-length (expand left=i-1, right=i+1), and even-length (left=i, right=i+1). While left >=0, right max, update longest = s.slice(left, right+1). Do this for all 2n-1 centers. O(n²) time since each expansion scans O(n), O(1) space. Example: 'babad' could be 'bab' or 'aba', both length 3. This leverages palindrome symmetry efficiently. In JS, string slice is fine for small n." "लक्ष्य सबसे लंबी पैलिंड्रोमिक सबस्ट्रिंग ढूंढना। ब्रूट फोर्स: हर पॉसिबल s[i..j] रिवर्स करके कंपेयर—O(n³) टाइम, बहुत धीमा। डीपी: 2D बूलियन टेबल dp[i][j] अगर i से j पैलिंड्रोम। डायगोनल्स ट्रू इनिश, लेंथ 2 अगर बराबर ट्रू, लॉन्गर अगर s[i]==s[j] और dp[i+1][j-1] ट्रू। मैक्स लेंथ और सबस्ट्रिंग ट्रैक, O(n²) टाइम और स्पेस—सॉलिड लेकिन स्पेस-हैवी। बेहतर स्पेस के लिए, सेंटर्स के आसपास एक्सपैंड: हर i ऑड-लेंथ सेंटर (left=i-1, right=i+1), ईवन (left=i, right=i+1)। जबकि left>=0, right मैक्स तो longest = s.slice(left, right+1) अपडेट। सभी 2n-1 सेंटर्स के लिए। O(n²) टाइम हर एक्सपैंशन O(n) स्कैन, O(1) स्पेस। उदाहरण: 'babad' 'bab' या 'aba', दोनों 3। यह पैलिंड्रोम सिमेट्री एफिशिएंटली यूज। जेएस में, स्ट्रिंग स्लाइस स्मॉल n के लिए फाइन।"

Valid Parentheses (LC 20) - LeetCode वैलिड पैरेंथेसीस (LC 20) - लीटकोड

Problem: Check if parentheses valid (balanced). समस्या: पैरेंथेसीस वैलिड हैं चेक (बैलेंस्ड)।

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

  • Primary: Stack
  • Secondary: Valid Parentheses
  • Frequency: High (Stack intro problem)

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

  • Big O: O(n) time, O(n) space.
  • Edge: Odd length false, nested brackets.
  • Self: Stack push opens, pop on close if match.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Only these brackets? Nested? Empty valid? Other chars?" Quick heuristic: "Is this balanced brackets? Hints ordering (stack LIFO), adjacency (no), prefix (no), structure (push/pop matching)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "सिर्फ ये ब्रैकेट्स? नेस्टेड? खाली वैलिड? अन्य कैरेक्टर्स?" क्विक ह्यूरिस्टिक: "क्या यह बैलेंस्ड ब्रैकेट्स? हिन्ट्स ऑर्डरिंग (स्टैक LIFO), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (पुश/पॉप मैचिंग)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"valid parentheses", "balanced" Nesting order? Only 3 types? Stack for Matching Breakdown: Count fails nesting → Stack pop match. Ask: Extra chars?
"parentheses", "valid sequence" n even? Deep nesting? Stack LIFO Think: Map closing to opening for quick check.

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

  • Counter-Based (Incorrect for Nesting): Count opening and closing brackets—if totals match, assume valid. O(n) time, but fails on nested mismatches like '([)]'.
  • Recursive Pair Removal: Repeatedly remove innermost matching pairs using regex replace until no change—valid if empty. O(n²) worst, risks stack overflow on deep recursion.
  • Stack (Optimal): Push opening brackets onto stack. For closing, check if stack empty or top doesn't match via a map—pop if match, else false. Valid if stack empty at end. O(n) time/space.

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

Javascript
// Non-Optimized (Recursive Pair Removal): Repeatedly remove pairs
function isValid(s) {
  // Helper: Remove innermost pairs recursively
  function removePairs(str) {
    if (str.length === 0) return true; // Empty valid
    const newStr = str.replace(/\(\)|\[\]|\{\}/g, ''); // Remove pairs
    if (newStr === str) return false; // No change, invalid
    return removePairs(newStr); // Recurse
  }
  return removePairs(s);
}
// Time: O(n^2) worst - multiple replaces, Space: O(n) call stack
Why This Solution? यह सॉल्यूशन क्यों?
  • Removes pairs recursively, intuitive.
  • O(n²) worst case due to string replace.
  • Risks stack overflow for deep nesting.

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

Javascript
// Optimized (Stack with Mapping): Push opens, pop on matching close
function isValid(s) {
  const stack = []; // Store opening brackets
  const map = { ')': '(', ']': '[', '}': '{' }; // Closing to opening
  for (let char of s) {
    if ('([{'.includes(char)) {
      stack.push(char); // Opening: push
    } else {
      // Closing: Check if matches top
      if (stack.length === 0 || stack.pop() !== map[char]) {
        return false; // Mismatch or empty
      }
    }
  }
  return stack.length === 0; // All closed
}
// Time: O(n) - single pass, Space: O(n) - stack worst
Why This Solution? यह सॉल्यूशन क्यों?
  • O(n) time/space, stack handles nesting.
  • Map for O(1) bracket matching.
  • Interview-standard, robust solution.

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

Simple counters fail on nesting — wrong for '([)]'. Recursive removal is O(n²) and risky. Stack with mapping is optimal O(n): push opens, pop on match. Implementation below. सिंपल काउंटर्स नेस्टिंग पर फेल — '([)]' के लिए गलत। रिकर्सिव रिमूवल O(n²) और रिस्की। मैपिंग से स्टैक ऑप्टिमल O(n): ओपन्स पुश, मैच पर पॉप। नीचे इम्प्लीमेंटेशन।

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

"To check if brackets are valid and balanced, the key is handling nesting order—simple counts won't work for '([)]'. A naive recursive way: Repeatedly replace matching pairs like '()' with empty until no change, then check if empty string. But that's inefficient and risks overflow. The standard solution: Use a stack for opening brackets. Iterate through string: If opening '([{', push it. If closing, check if stack empty (false) or stack.pop() != matching open via a map like {')':'(', ...}—if mismatch, false. After loop, return stack.length === 0. O(n) time and space, perfect for nesting because stack's LIFO matches bracket order. Edges: Empty true, odd length false, '()' true, '([)]' false. In JS, I can use an object as the map for quick lookups—super clean." "ब्रैकेट्स वैलिड और बैलेंस्ड चेक करने के लिए, नेस्टिंग ऑर्डर हैंडल की—'([)]' के लिए सिंपल काउंट्स फेल। नेव रिकर्सिव: मैचिंग पेयर्स '()' को खाली से रिप्लेस रेपिटेडली जब तक चेंज न, फिर खाली चेक। लेकिन इनएफिशिएंट और ओवरफ्लो रिस्क। स्टैंडर्ड सॉल्यूशन: ओपनिंग के लिए स्टैक। स्ट्रिंग इटरेट: अगर '([{', पुश। क्लोजिंग पर, स्टैक एंप्टी (फॉल्स) या stack.pop() != मैचिंग ओपन मैप से जैसे {')':'(', ...}—मिसमैच तो फॉल्स। लूप बाद, stack.length === 0 तो ट्रू। O(n) टाइम/स्पेस, नेस्टिंग के लिए परफेक्ट क्योंकि LIFO ब्रैकेट ऑर्डर मैच। एज: खाली ट्रू, ऑड लेंथ फॉल्स, '()' ट्रू, '([)]' फॉल्स। जेएस में, ऑब्जेक्ट मैप क्विक लुकअप्स के लिए—सुपर क्लीन।"

Linked Lists (Day 5) लिंक्ड लिस्ट्स (दिन 5)

Linked lists: Nodes with val/next. No random access; traversal O(n). लिंक्ड लिस्ट्स: नोड्स वैल/नेक्स्ट के साथ। कोई रैंडम एक्सेस नहीं; ट्रैवर्सल O(n)।

Reverse Linked List (LC 206) - LeetCode रिवर्स लिंक्ड लिस्ट (LC 206) - लीटकोड

Problem: Reverse list. समस्या: लिस्ट रिवर्स करें।

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

  • Primary: Linked List, In-Place Reversal
  • Secondary: Pointer Manipulation
  • Frequency: High (List basics)

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

  • Big O: O(n) time, O(1) space.
  • Edge: Empty, single node.
  • Self: Prev, curr, next pointers; iterative best.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Singly linked? Modify in-place? n up to? Cycle?" Quick heuristic: "Is this list reversal? Hints ordering (pointers), adjacency (yes), prefix (no), structure (three pointers)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "सिंगली लिंक्ड? इन-प्लेस मॉडिफाई? n तक? साइकल?" क्विक ह्यूरिस्टिक: "क्या यह लिस्ट रिवर्सल? हिन्ट्स ऑर्डरिंग (पॉइंटर्स), एडजेसेंसी (हां), प्रीफिक्स (नहीं), स्ट्रक्चर (थ्री पॉइंटर्स)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"reverse the list" In-place? Return new head? Linked List Pointer Reversal Breakdown: Array rebuild → Iterative pointers. Ask: Recursive OK?
"linked list", "reverse" n=10^5? Cycles? List In-Place Think: Save next before flipping link.

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

  • Array Conversion: Traverse to array of values, reverse array, rebuild list from it. O(n) time, O(n) space—easy but uses extra space.
  • Recursive: Recurse to end, then reverse links on unwind. O(n) time, O(n) stack space—elegant but risks overflow for long lists.
  • Iterative Pointers (Optimal): Three pointers: prev=null, curr=head. While curr, save next=curr.next, set curr.next=prev, prev=curr, curr=next. Return prev. O(n) time, O(1) space.

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

Javascript
// Non-Optimized (Array Conversion): To array, reverse, rebuild
class ListNode { constructor(val = 0, next = null) { this.val = val; this.next = next; } }
function reverseList(head) {
  const arr = [];
  let curr = head;
  // To array
  while (curr) {
    arr.push(curr.val);
    curr = curr.next;
  }
  // Reverse array
  arr.reverse();
  // Rebuild list
  let newHead = null, tail = null;
  for (let val of arr) {
    const node = new ListNode(val);
    if (!newHead) newHead = tail = node;
    else { tail.next = node; tail = node; }
  }
  return newHead;
}
// Time: O(n), Space: O(n) - array
Why This Solution? यह सॉल्यूशन क्यों?
  • Uses array for straightforward reversal.
  • O(n) space, easier to understand.
  • Not ideal for space constraints.

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

Javascript
// Optimized (Iterative Pointer Reversal): Flip links with three pointers
function reverseList(head) {
  let prev = null, curr = head; // Start with prev null
  while (curr) {
    let next = curr.next; // Save next
    curr.next = prev; // Reverse pointer
    prev = curr; // Move prev
    curr = next; // Move curr
  }
  return prev; // New head
}
// Time: O(n), Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • In-place reversal, O(1) space.
  • O(n) time, single pass.
  • Interview-standard for efficiency.

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

Array conversion and rebuild is O(n) but uses extra space. Recursive is elegant but O(n) stack. Iterative pointer reversal is optimal O(n) time, O(1) space—in-place. Code shown. ऐरे कन्वर्शन एंड रिबिल्ड O(n) लेकिन एक्स्ट्रा स्पेस। रिकर्सिव एलिगेंट लेकिन O(n) स्टैक। इटरेटिव पॉइंटर रिवर्सल ऑप्टिमल O(n) टाइम, O(1) स्पेस—इन-प्लेस। कोड दिखाया।

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

"To reverse a singly linked list, one way: Traverse to collect values in an array, reverse the array, then create new nodes linking in that order—O(n) time and space, simple but not space-optimal. Recursive: Base case null or single returns itself; else, reverse rest, then attach current as tail by setting next.next = current, current.next = null. But recursion uses O(n) stack. For optimal iterative: Use prev = null, curr = head. While curr != null: next = curr.next (save), curr.next = prev (reverse), prev = curr, curr = next. At end, prev is new head. O(n) time, O(1) space, in-place. Edges: Null returns null, single node unchanged. The key is saving next before overwriting the link. In JS, it's straightforward pointer juggling—interviewers love this for showing pointer manipulation." "सिंगली लिंक्ड लिस्ट रिवर्स करने के लिए, एक तरीका: वैल्यूज ऐरे में कलेक्ट ट्रैवर्स, ऐरे रिवर्स, फिर न्यू नोड्स लिंक—O(n) टाइम/स्पेस, सरल लेकिन स्पेस-ऑप्टिमल नहीं। रिकर्सिव: बेस null या सिंगल खुद रिटर्न; वरना, रेस्ट रिवर्स, फिर करेंट टेल अटैच next.next = current, current.next = null। लेकिन O(n) स्टैक। ऑप्टिमल इटरेटिव के लिए: prev = null, curr = head। जबकि curr != null: next = curr.next (सेव), curr.next = prev (रिवर्स), prev = curr, curr = next। एंड पर, prev न्यू हेड। O(n) टाइम, O(1) स्पेस, इन-प्लेस। एज: null null, सिंगल अनचेंज्ड। की सेव नेक्स्ट ओवरराइट से पहले। जेएस में, स्ट्रेटफॉरवर्ड पॉइंटर जुगलिंग—इंटरव्यूअर्स पॉइंटर मैनिपुलेशन के लिए लव।"

Merge Two Sorted Lists (LC 21) - LeetCode मर्ज टू सॉर्टेड लिस्ट्स (LC 21) - लीटकोड

Problem: Merge two sorted lists. समस्या: दो सॉर्टेड लिस्ट्स मर्ज करें।

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

  • Primary: Linked List, Merge Sorted
  • Secondary: Two Pointers
  • Frequency: Medium (List merge basics)

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

  • Big O: O(m+n) time, O(1) space.
  • Edge: One empty returns other.
  • Self: Dummy node, compare/link smaller.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Both sorted ascending? New list or modify? m,n up to?" Quick heuristic: "Is this merging sorted lists? Hints ordering (two pointers), adjacency (yes), prefix (no), structure (dummy tail)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "दोनों सॉर्टेड एसेंडिंग? न्यू लिस्ट या मॉडिफाई? m,n तक?" क्विक ह्यूरिस्टिक: "क्या यह सॉर्टेड लिस्ट्स मर्जिंग? हिन्ट्स ऑर्डरिंग (टू पॉइंटर्स), एडजेसेंसी (हां), प्रीफिक्स (नहीं), स्ट्रक्चर (डमी टेल)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"merge two sorted lists" New list? Duplicates? Linked List Two Pointers Breakdown: Array merge → Pointer compare link. Ask: Stable sort?
"sorted linked lists" m+n=10^4? Cycles? List Merge Think: Dummy to handle head, append remaining.

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

  • Array Merge (Non-Optimized): Extract both lists to arrays, merge like merge sort (two pointers), then rebuild new list. O(m+n) time, O(m+n) space—straightforward but extra space.
  • Recursive: Compare heads, recursively merge tails, attach smaller head. O(m+n) time, O(m+n) stack space—clean but recursive depth issue.
  • Two Pointers (Optimal): Dummy node for head, tail pointer. While both lists non-null, compare heads, attach smaller to tail, advance that pointer and tail. Append remaining. O(m+n) time, O(1) space.

Non-Optimized Solution (Array Merge) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (ऐरे मर्ज)

Javascript
// Non-Optimized (Array + Sort): Extract to arrays, sort, rebuild
function mergeTwoLists(list1, list2) {
  const arr = [];
  // Add list1
  let curr = list1;
  while (curr) { arr.push(curr.val); curr = curr.next; }
  // Add list2
  curr = list2;
  while (curr) { arr.push(curr.val); curr = curr.next; }
  // Sort array
  arr.sort((a,b) => a-b);
  // Rebuild
  let head = null, tail = null;
  for (let val of arr) {
    const node = new ListNode(val);
    if (!head) head = tail = node;
    else { tail.next = node; tail = node; }
  }
  return head;
}
// Time: O((m+n) log (m+n)), Space: O(m+n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Arrays simplify merging with sort.
  • O((m+n) log(m+n)) time, extra space.
  • Easier but inefficient for large lists.

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

Javascript
// Optimized (Two Pointers Merge): Compare and link smaller nodes iteratively
function mergeTwoLists(list1, list2) {
  const dummy = new ListNode(); // Dummy head
  let tail = dummy; // Tail pointer
  let p1 = list1, p2 = list2; // Pointers
  while (p1 && p2) {
    if (p1.val <= p2.val) {
      tail.next = p1; // Link smaller
      p1 = p1.next;
    } else {
      tail.next = p2;
      p2 = p2.next;
    }
    tail = tail.next; // Move tail
  }
  // Append remaining
  tail.next = p1 || p2;
  return dummy.next; // Real head
}
// Time: O(m+n), Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • O(m+n) time, O(1) space, in-place.
  • Dummy node simplifies head logic.
  • Interview-preferred for efficiency.

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

Array extraction and sort is O((m+n) log(m+n)), extra space. Recursive merge is clean but O(m+n) stack. Two pointers with dummy is optimal O(m+n) time, O(1) space. Here's how. ऐरे एक्सट्रैक्शन एंड सॉर्ट O((m+n) log(m+n)), एक्स्ट्रा स्पेस। रिकर्सिव मर्ज क्लीन लेकिन O(m+n) स्टैक। डमी से टू पॉइंटर्स ऑप्टिमल O(m+n) टाइम, O(1) स्पेस। कैसे यहाँ।

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

"To merge two sorted linked lists into one sorted list, an easy way: Traverse both to arrays, use two pointers to merge like in merge sort, then build a new list from the merged array—O(m+n) time but O(m+n) space. Recursive: If either null return other; else, if list1.val <= list2.val, list1.next = merge(list1.next, list2), return list1; swap otherwise. Clean, but O(m+n) stack. For optimal iterative: Create a dummy node, tail = dummy. p1 = list1, p2 = list2. While p1 and p2: if p1.val <= p2.val, tail.next = p1, p1 = p1.next; else tail.next = p2, p2 = p2.next. tail = tail.next. Then tail.next = p1 || p2 (remaining). Return dummy.next. O(m+n) time, O(1) space, in-place. Edges: One null returns other. Dummy simplifies head removal cases. In JS, pointer assignments are direct." "दो सॉर्टेड लिंक्ड लिस्ट्स को एक सॉर्टेड में मर्ज, आसान तरीका: दोनों ट्रैवर्स ऐरे, टू पॉइंटर्स मर्ज सॉर्ट लाइक, फिर मर्ज्ड ऐरे से न्यू लिस्ट बिल्ड—O(m+n) टाइम लेकिन O(m+n) स्पेस। रिकर्सिव: अगर कोई null दूसरा रिटर्न; वरना, अगर list1.val <= list2.val, list1.next = merge(list1.next, list2), list1 रिटर्न; स्वैप वरना। क्लीन, लेकिन O(m+n) स्टैक। ऑप्टिमल इटरेटिव: डमी नोड, tail = dummy। p1 = list1, p2 = list2। जबकि p1 और p2: अगर p1.val <= p2.val, tail.next = p1, p1 = p1.next; वरना tail.next = p2, p2 = p2.next। tail = tail.next। फिर tail.next = p1 || p2 (रिमेनिंग)। dummy.next रिटर्न। O(m+n) टाइम, O(1) स्पेस, इन-प्लेस। एज: एक null दूसरा। डमी हेड रिमूवल केस सिम्प्लिफाई। जेएस में, पॉइंटर अस्याइनमेंट्स डायरेक्ट।"

Linked List Cycle (LC 141) - LeetCode लिंक्ड लिस्ट साइकल (LC 141) - लीटकोड

Problem: Detect cycle. समस्या: साइकल डिटेक्ट।

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

  • Primary: Linked List, Cycle Detection
  • Secondary: Two Pointers (Slow/Fast)
  • Frequency: High (Floyd's algorithm)

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

  • Big O: O(n) time, O(1) space.
  • Edge: Null head, single node no cycle.
  • Self: Floyd’s tortoise/hare, meet if cycle.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Return boolean or entry point? Singly linked? n up to?" Quick heuristic: "Is this cycle detection? Hints ordering (fast/slow), adjacency (no), prefix (no), structure (pointer meet)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "बूलियन या एंट्री पॉइंट रिटर्न? सिंगली लिंक्ड? n तक?" क्विक ह्यूरिस्टिक: "क्या यह साइकल डिटेक्शन? हिन्ट्स ऑर्डरिंग (फास्ट/स्लो), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (पॉइंटर मीट)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"cycle in linked list" Detect or find start? O(1) space? Two Pointers Slow/Fast Breakdown: Hash visited → Floyd meet. Ask: Space limit?
"detect cycle" n=10^4? Entry node? List Cycle Detection Think: Fast laps slow in cycle.

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

  • Hash Set (Non-Optimized): Traverse, add nodes to Set—if node already in Set, cycle. O(n) time, O(n) space—works but space-heavy for lists.
  • Floyd's Tortoise and Hare (Optimal): Slow pointer moves 1 step, fast 2 steps. If they meet, cycle; if fast reaches end, no. O(n) time, O(1) space—math proves meeting in cycle.

Non-Optimized Solution (Hash Set) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (हैश सेट)

Javascript
// Non-Optimized (Hash Set): Track visited nodes
function hasCycle(head) {
  const seen = new Set();
  let curr = head;
  while (curr) {
    if (seen.has(curr)) return true; // Cycle
    seen.add(curr); // Add node
    curr = curr.next;
  }
  return false;
}
// Time: O(n), Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Set detects node revisits for cycle.
  • O(n) time, O(n) space, straightforward.
  • Not ideal for space constraints.

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

Javascript
// Optimized (Two Pointers - Slow/Fast): Floyd's tortoise and hare
function hasCycle(head) {
  let slow = head, fast = head; // Start same
  while (fast && fast.next) {
    slow = slow.next; // Move 1
    fast = fast.next.next; // Move 2
    if (slow === fast) return true; // Meet = cycle
  }
  return false; // End reached
}
// Time: O(n), Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • O(1) space, Floyd’s algorithm.
  • Fast/slow pointers detect cycle.
  • Interview-standard, mathematically sound.

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

Hash set tracks visited — O(n) space, works fine. But slow/fast pointers (Floyd's) is optimal O(n) time, O(1) space: fast laps slow in cycle. Code below. हैश सेट विजिटेड ट्रैक — O(n) स्पेस, फाइन काम। लेकिन स्लो/फास्ट पॉइंटर्स (फ्लॉयड्स) ऑप्टिमल O(n) टाइम, O(1) स्पेस: साइकल में फास्ट स्लो को लैप। कोड नीचे।

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

"To detect a cycle in a linked list, a simple way: Use a Set to store visited nodes—traverse, if current in Set, cycle; else add. O(n) time and space, reliable but uses extra space. The clever O(1) space method is Floyd's cycle detection, aka tortoise and hare: Slow moves one step (slow = slow.next), fast two (fast = fast.next.next), starting both at head. While fast and fast.next exist: Move them, if slow === fast, return true (they meet in cycle). If fast null, no cycle. Why? In a cycle, fast laps slow eventually due to double speed—math shows they meet. O(n) time worst-case. Edges: Null head false, single node false (fast.next null). This is interview gold for showing algorithm knowledge. In JS, null checks prevent errors." "लिंक्ड लिस्ट में साइकल डिटेक्ट, सिंपल तरीका: सेट विजिटेड नोड्स स्टोर—ट्रैवर्स, करेंट सेट में तो साइकल; वरना ऐड। O(n) टाइम/स्पेस, रिलायबल लेकिन एक्स्ट्रा स्पेस। क्लीवर O(1) स्पेस फ्लॉयड्स साइकल डिटेक्शन, टॉर्टोइज एंड हेयर: स्लो एक स्टेप (slow = slow.next), फास्ट दो (fast = fast.next.next), दोनों हेड से। जबकि फास्ट और fast.next: मूव, अगर slow === fast, ट्रू (साइकल में मिलते)। फास्ट null तो नो। क्यों? साइकल में, फास्ट डबल स्पीड से स्लो को लैप—मैथ मिलना दिखाता। O(n) वर्स्ट टाइम। एज: null हेड फॉल्स, सिंगल नोड फॉल्स (fast.next null)। यह इंटरव्यू गोल्ड अल्गो नॉलेज दिखाने के लिए। जेएस में, null चेक्स एरर्स प्रिवेंट।"

Remove Nth Node From End of List (LC 19) - LeetCode रिमूव एनथ नोड फ्रॉम एंड ऑफ लिस्ट (LC 19) - लीटकोड

Problem: Remove nth node from end. समस्या: एनथ नोड एंड से रिमूव।

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

  • Primary: Linked List, Two Pointers Gap
  • Secondary: Remove Node
  • Frequency: Medium (List traversal)

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

  • Big O: O(n) time, O(1) space.
  • Edge: Remove head, n=1, single node.
  • Self: Two pointers, fast n steps ahead.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "1-indexed n? Remove head OK? n > length?" Quick heuristic: "Is this remove from end? Hints ordering (two pointers gap), adjacency (no), prefix (no), structure (dummy for head)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "1-इंडेक्स्ड n? हेड रिमूव OK? n > लेंथ?" क्विक ह्यूरिस्टिक: "क्या यह एंड से रिमूव? हिन्ट्स ऑर्डरिंग (टू पॉइंटर्स गैप), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (डमी फॉर हेड)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"remove nth from end" Return new head? n=length? Two Pointers with Gap Breakdown: Count length → Gap pointers. Ask: Invalid n?
"linked list", "nth from end" n=10^5? Dummy needed? List Two Pointers Think: Fast ahead n+1, move together to prev.

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

  • Two Passes (Non-Optimized): First traverse to count length L, then from head go to L-n position, set its next = next.next to skip. O(n) time, O(1) space—simple, handles head remove if L==n.
  • One Pass Two Pointers (Optimal): Use dummy head. Fast starts at dummy, move n+1 steps. Then move slow and fast together until fast null—slow now at prev of target, slow.next = slow.next.next. O(n) time, O(1) space.

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

Javascript
// Non-Optimized (Two Passes): Count length, then remove
function removeNthFromEnd(head, n) {
  let len = 0, curr = head;
  // First: Get length
  while (curr) { len++; curr = curr.next; }
  if (len < n) return head; // Invalid
  if (len === n) return head.next; // Remove head
  // Second: Traverse to len-n
  curr = head;
  for (let i = 1; i < len - n; i++) curr = curr.next;
  // Remove
  curr.next = curr.next.next;
  return head;
}
// Time: O(n), Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • Calculates length, then traverses to target, O(n) time.
  • Clear logic, no need for complex pointers.
  • Two passes less efficient than one-pass.

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

Javascript
// Optimized (Two Pointers Gap): Fast ahead n+1, then move together
function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head); // Handle head remove
  let fast = dummy, slow = dummy;
  // Fast ahead by n+1 (for prev)
  for (let i = 0; i <= n; i++) fast = fast.next;
  // Move both until fast ends
  while (fast) {
    slow = slow.next;
    fast = fast.next;
  }
  // Remove
  slow.next = slow.next.next;
  return dummy.next;
}
// Time: O(n), Space: O(1)
Why This Solution? यह सॉल्यूशन क्यों?
  • Single pass with two pointers, O(n) time.
  • O(1) space, no extra storage.
  • Interview-preferred for efficiency.

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

Two passes: count length then remove — O(n), simple. But two pointers with gap is one-pass O(n), O(1) space: fast ahead n+1, then sync to find prev. Code here. टू पास: लेंथ काउंट फिर रिमूव — O(n), सरल। लेकिन गैप से टू पॉइंटर्स वन-पास O(n), O(1) स्पेस: फास्ट n+1 आगे, फिर सिंक प्रेव ढूंढ। कोड यहाँ।

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

"To remove the nth node from the end of a linked list, first pass way: Traverse to count total length L. If n == L, return head.next (remove head). Else, go to index L-n-1 (prev of target), set its next = next.next. O(n) time, two passes. For one pass: Add dummy = new Node(0, head). Let fast = dummy, slow = dummy. Move fast n+1 steps ahead (so when fast at end, slow at prev). Then while fast != null: slow = slow.next, fast = fast.next. Now slow.next = slow.next.next to skip. Return dummy.next. O(n) time, O(1) space. Why n+1? Gap ensures slow is exactly before target when fast ends. Edges: n=1 (remove last), n=L (remove head via dummy), single node (dummy.next = null). This two-pointer gap technique is common for list problems. In JS, creating dummy is easy." "लिंक्ड लिस्ट के एंड से nth नोड रिमूव, फर्स्ट पास: ट्रैवर्स टोटल लेंथ L काउंट। अगर n == L, head.next रिटर्न (हेड रिमूव)। वरना, L-n-1 (टारगेट का प्रेव) जाएं, next = next.next सेट। O(n) टाइम, दो पास। वन पास के लिए: dummy = new Node(0, head)। fast = dummy, slow = dummy। fast n+1 स्टेप्स आगे मूव (फास्ट एंड पर स्लो प्रेव पर)। फिर जबकि fast != null: slow = slow.next, fast = fast.next। अब slow.next = slow.next.next स्किप। dummy.next रिटर्न। O(n) टाइम, O(1) स्पेस। क्यों n+1? गैप सुनिश्चित स्लो टारगेट से पहले जब फास्ट एंड। एज: n=1 (लास्ट रिमूव), n=L (डमी से हेड), सिंगल (dummy.next = null)। यह टू-पॉइंटर गैप लिस्ट प्रॉब्लम्स में कॉमन। जेएस में, डमी क्रिएट आसान।"

Stacks & Queues (Days 7-8) स्टैक्स एंड क्यूज (दिन 7-8)

Stacks: LIFO. Queues: FIFO. JS arrays for both (push/pop, push/shift). स्टैक्स: LIFO. क्यूज: FIFO। जेएस ऐरे दोनों के लिए (push/pop, push/shift)।

Min Stack (LC 155) - LeetCode मिन स्टैक (LC 155) - लीटकोड

Problem: Stack with O(1) min. समस्या: O(1) मिन के साथ स्टैक।

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

  • Primary: Stack, Design
  • Secondary: Monotonic Stack Variant
  • Frequency: Medium (Stack design problems)

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

  • Big O: O(1) per op, O(n) space.
  • Edge: Empty min? (problem assumes calls valid).
  • Self: Two stacks or pairs in one.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "O(1) for all ops including min? Handle negatives/duplicates? n up to 10^4?" Quick heuristic: "Is this stack design with extra query? Hints ordering (LIFO with min), adjacency (no), prefix (no), structure (aux stack or pairs)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "सब ऑप्स के लिए O(1) मिन सहित? नेगेटिव्स/डुप्स हैंडल? n 10^4 तक?" क्विक ह्यूरिस्टिक: "क्या यह एक्स्ट्रा क्वेरी के साथ स्टैक डिजाइन? हिन्ट्स ऑर्डरिंग (LIFO मिन के साथ), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (ऑक्स स्टैक या पेयर्स)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"getMin in O(1)", "push/pop/top O(1)" All ops O(1)? Negatives? Empty behavior? Stack with Auxiliary Structure Breakdown: Scan for min → Pairs or second stack. Ask: Space trade-off OK?
"design stack", "constant time min" n=10^4? Frequent mins? Stack Design, Paired Values Think: Precompute mins on push for O(1) access.

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

  • Brute Force (Single Array): Use a single array for the stack; for getMin, iterate through the entire array with Math.min. O(1) for push/pop/top, but O(n) for getMin—simple but inefficient for frequent mins.
  • Two Stacks: One main stack for values, one min stack that pushes the current min on each push (or only when smaller). On pop, pop both; getMin is top of min stack. O(1) all, O(n) space.
  • Paired Values (Optimal): Store pairs [val, currentMin] in one stack. On push, currentMin = min(val, prev min or val). getMin is top pair's second element. O(1) all operations, O(n) space.

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

Javascript
// Brute Force (Single Array): Compute min by scanning stack each time
class MinStack {
  constructor() { this.stack = []; }
  push(val) { this.stack.push(val); }
  pop() { this.stack.pop(); }
  top() { return this.stack[this.stack.length - 1]; }
  getMin() { return Math.min(...this.stack); } // O(n) scan
}
// Time: getMin O(n), others O(1), Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Straightforward single array for stack operations.
  • Easy to implement basic push/pop/top.
  • O(n) for getMin makes it slow for repeated queries.

Optimized Solution (Paired Values) ऑप्टिमाइज्ड सॉल्यूशन (पेयर्ड वैल्यूज)

Javascript
// Optimized (Paired Values): Store [val, currentMin] for O(1) access
class MinStack {
  constructor() { this.stack = []; }
  push(val) {
    // Min is smaller of val or prev min (or val if empty)
    const min = this.stack.length === 0 ? val : Math.min(val, this.getMin());
    this.stack.push([val, min]); // Push pair
  }
  pop() { this.stack.pop(); }
  top() { return this.stack[this.stack.length - 1][0]; }
  getMin() { return this.stack[this.stack.length - 1][1]; }
}
// Time: All O(1), Space: O(n) - doubles
Why This Solution? यह सॉल्यूशन क्यों?
  • All operations O(1) by precomputing min in pairs.
  • Single stack, handles pops correctly by removing pairs.
  • Space efficient relative to functionality.

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

Naive scan for min on each getMin — O(n), fails requirement. Two stacks track mins, but paired values in one stack is optimal O(1) all ops, O(n) space. Implementation follows. नेव getMin पर स्कैन — O(n), रिक्वायरमेंट फेल। टू स्टैक्स मिन्स ट्रैक, लेकिन एक स्टैक में पेयर्ड वैल्यूज ऑप्टिमल O(1) सब, O(n) स्पेस। इम्प्लीमेंटेशन आगे।

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

"For Min Stack, we need push, pop, top, and getMin all in O(1) time. A naive way: Just use an array for the stack, and for getMin, loop through with Math.min—that's O(1) for most ops but O(n) for min, which fails the requirement. To fix it, one common approach is two stacks: main for values, minStack that always has the current minimum on top—on push, push to main, and push min(current min, val) to minStack. But to save space, we can use one stack storing pairs [val, minSoFar], where minSoFar is the min of val and the previous min (or val if first). On push, compute new min and push the pair. Pop removes the pair, top returns pair[0], getMin pair[1]. Everything O(1). It handles negatives or duplicates fine, and for empty, we assume valid calls per problem. In JS, arrays work great for this—interviewers like seeing the pair trick for efficiency." "मिन स्टैक के लिए, push, pop, top, और getMin सब O(1) टाइम में। नेव तरीका: सिर्फ ऐरे स्टैक के लिए, getMin के लिए Math.min से लूप—ज्यादातर O(1) लेकिन मिन O(n), रिक्वायरमेंट फेल। फिक्स के लिए, कॉमन दो स्टैक्स: मेन वैल्यूज के लिए, minStack हमेशा करेंट मिन टॉप पर—push पर मेन में push, minStack में min(करेन्ट मिन, val) push। लेकिन स्पेस सेव के लिए, एक स्टैक [val, minSoFar] पेयर्स। minSoFar val और प्रेव मिन का मिन (या val अगर फर्स्ट)। push पर न्यू मिन कंप्यूट push पेयर। pop पेयर रिमूव, top pair[0], getMin pair[1]। सब O(1)। नेगेटिव्स या डुप्स फाइन, एंप्टी के लिए वैलिड कॉल्स असम। जेएस में, ऐरे ग्रेट—इंटरव्यूअर्स पेयर ट्रिक एफिशिएंसी के लिए लाइक।"

Valid Parentheses (LC 20 - Review) वैलिड पैरेंथेसीस (LC 20 - रिव्यू)

Reviewed from earlier—same as above. Quick note: Practice explaining stack again for reinforcement. पहले से रिव्यूड—ऊपर जैसा। क्विक नोट: स्टैक एक्सप्लेन प्रैक्टिस रीइनफोर्समेंट के लिए।

Implement Queue using Stacks (LC 232) - LeetCode इम्प्लीमेंट क्यू यूजिंग स्टैक्स (LC 232) - लीटकोड

Problem: Queue with two stacks. समस्या: दो स्टैक्स के साथ क्यू।

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

  • Primary: Stack, Design
  • Secondary: Amortized Analysis
  • Frequency: Medium (Queue simulation)

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

  • Big O: Enqueue O(1), dequeue O(1) amortized.
  • Edge: Empty.
  • Self: In stack push; out pop (shift in to out when empty).

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "All ops amortized O(1)? FIFO order? n up to 10^4?" Quick heuristic: "Is this queue sim with stacks? Hints ordering (FIFO via LIFO reverse), adjacency (no), prefix (no), structure (two stacks: input/output)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "सब ऑप्स एमोर्टाइज्ड O(1)? FIFO? n 10^4 तक?" क्विक ह्यूरिस्टिक: "क्या यह स्टैक्स से क्यू सिम? हिन्ट्स ऑर्डरिंग (LIFO रिवर्स से FIFO), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (टू स्टैक्स: इनपुट/आउटपुट)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"implement queue using stacks", "amortized O(1)" All ops? FIFO? Empty peek? Stack Simulation for Queue Breakdown: Repeated transfer → Lazy on empty out. Ask: Worst-case vs amortized?
"push/pop/peek/empty" n=10^4? Duplicates? Design, Two Stacks Think: In for enqueue, out for dequeue (reverse via pop).

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

  • Naive Transfer (Repeated): Use two stacks: 'in' for push, 'out' for pop. On every pop/peek, if out empty, transfer all from in to out (reversing). O(1) push, O(n) worst for pop—amortized ok but frequent transfers bad.
  • Lazy Transfer (Optimal): Push always to 'in' stack (O(1)). For pop/peek, if out empty, transfer from in to out once (reversing to FIFO). Then pop/peek from out. Each element transferred once, amortized O(1) all ops.

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

Javascript
// Brute Force (Repeated Transfer): Transfer on every dequeue
class MyQueue {
  constructor() { this.in = []; this.out = []; }
  push(x) { this.in.push(x); }
  pop() {
    // Transfer all every time - O(n) per pop
    while (this.in.length) this.out.push(this.in.pop());
    return this.out.pop();
  }
  peek() {
    while (this.in.length) this.out.push(this.in.pop());
    return this.out[this.out.length - 1];
  }
  empty() { return !this.in.length && !this.out.length; }
}
// Time: pop/peek O(n) worst, Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple transfer logic on every operation.
  • Works but transfers repeatedly, O(n) per pop.
  • Not efficient for many dequeues.

Optimized Solution (Lazy Transfer) ऑप्टिमाइज्ड सॉल्यूशन (लेजी ट्रांसफर)

Javascript
// Optimized (Lazy Transfer): Transfer only when out empty for amortized O(1)
class MyQueue {
  constructor() { this.in = []; this.out = []; }
  push(x) { this.in.push(x); } // O(1)
  pop() {
    // If out empty, transfer from in
    if (!this.out.length) {
      while (this.in.length) this.out.push(this.in.pop());
    }
    return this.out.pop(); // O(1) amort
  }
  peek() {
    if (!this.out.length) {
      while (this.in.length) this.out.push(this.in.pop());
    }
    return this.out[this.out.length - 1];
  }
  empty() { return !this.in.length && !this.out.length; }
}
// Time: Amortized O(1) per op, Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • Amortized O(1) by transferring only when needed.
  • Each element moved once from in to out.
  • Standard for simulating queue with stacks.

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

Repeated transfer on every pop — O(n) worst, inefficient. Lazy transfer only when out empty gives amortized O(1): each element transferred once. Code below. हर pop पर रिपीटेड ट्रांसफर — O(n) वर्स्ट, इनएफिशिएंट। आउट एंप्टी पर लेजी ट्रांसफर एमोर्टाइज्ड O(1): हर एलिमेंट एक बार ट्रांसफर। कोड नीचे।

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

"To implement a queue using stacks—enqueue front, dequeue back—we use two: 'inStack' for push (O(1) append), 'outStack' for pop (O(1) remove last). Naive: On every pop, if out empty, pour all from in to out (popping reverses to FIFO). But that's O(n) each time. Better: Lazy transfer—push always to inStack. Only when outStack empty for pop/peek, transfer once from in to out. Then pop from out. Amortized O(1) because each element is pushed to in once and transferred once. Empty if both empty. Edges: Push then immediate pop works after transfer. This shows understanding of amortization—interviewers ask about worst vs average." "स्टैक्स यूजिंग क्यू इम्प्लीमेंट—enque front, deque back—दो यूज: 'inStack' push के लिए (O(1) append), 'outStack' pop के लिए (O(1) लास्ट रिमूव)। नेव: हर pop पर, out एंप्टी तो in से out में पोर (pop रिवर्स FIFO)। लेकिन हर बार O(n)। बेहतर: लेजी ट्रांसफर—push हमेशा inStack। pop/peek पर outStack एंप्टी तो in से out ट्रांसफर एक बार। फिर out से pop। एमोर्टाइज्ड O(1) क्योंकि हर एलिमेंट in में push एक बार, ट्रांसफर एक। एंप्टी अगर दोनों। एज: push फिर इमीडिएट pop ट्रांसफर बाद। यह एमोर्टाइजेशन समझ दिखाता—इंटरव्यूअर्स वर्स्ट vs एवरेज पूछते।"

Daily Temperatures (LC 739) - LeetCode डेली टेम्परेचर्स (LC 739) - लीटकोड

Problem: Days to warmer temp. समस्या: वार्मर टेम्प तक दिन।

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

  • Primary: Array, Monotonic Stack
  • Secondary: Next Greater Element
  • Frequency: High (Stack array problems)

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

  • Big O: O(n) time, O(n) space.
  • Edge: Decreasing → 0s.
  • Self: Monotonic stack (decreasing temps).

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Strictly greater? n up to 10^5? All unique temps?" Quick heuristic: "Is this next greater element? Hints ordering (monotonic stack), adjacency (no), prefix (no), structure (decreasing stack indices)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "स्ट्रिक्टली ग्रेटर? n 10^5 तक? यूनिक टेम्प्स?" क्विक ह्यूरिस्टिक: "क्या यह नेक्स्ट ग्रेटर एलिमेंट? हिन्ट्स ऑर्डरिंग (मोनोटॉनिक स्टैक), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (डिक्रीजिंग स्टैक इंडेक्सेस)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"days until warmer temperature" Strictly greater? No warmer → 0? n=10^5? Monotonic Stack for Next Greater Breakdown: Brute forward scan → Stack pop on greater. Ask: Circular? (No)
"array of temperatures", "next warmer" Decreasing sequence? Duplicates? Array Stack, Decreasing Monotonic Think: Maintain decreasing stack of indices; pop when current > top.

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

  • Brute Force (Nested Loops): For each i, loop j > i until find warmer temp, set result[i] = j-i or 0. O(n²) time—direct but quadratic.
  • Monotonic Stack (Optimal): Stack holds indices of decreasing temperatures. For each i, while stack not empty and temp[i] > temp[stack.top], pop and set result[popped] = i - popped. Push i. O(n) time, each index pushed/popped once.

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

Javascript
// Brute Force (Nested Loops): Scan forward from each day
function dailyTemperatures(temperatures) {
  const result = new Array(temperatures.length).fill(0);
  // For each day
  for (let i = 0; i < temperatures.length; i++) {
    // Look forward
    for (let j = i + 1; j < temperatures.length; j++) {
      if (temperatures[j] > temperatures[i]) {
        result[i] = j - i; // Days
        break;
      }
    }
  }
  return result;
}
// Time: O(n^2), Space: O(1) output aside
Why This Solution? यह सॉल्यूशन क्यों?
  • Straightforward forward scan for each day.
  • Correct but O(n²) for large arrays.
  • No extra space beyond output.

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

Javascript
// Optimized (Monotonic Stack): Decreasing stack for next greater
function dailyTemperatures(temperatures) {
  const n = temperatures.length;
  const result = new Array(n).fill(0);
  const stack = []; // Indices of decreasing temps
  // Forward pass
  for (let i = 0; i < n; i++) {
    // While stack not empty and current warmer than top
    while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const idx = stack.pop(); // Pop index
      result[idx] = i - idx; // Calc days
    }
    stack.push(i); // Push current
  }
  return result;
}
// Time: O(n) - each pushed/popped once, Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • O(n) time using stack for next greater.
  • Monotonic decreasing stack efficient.
  • Space O(n) for stack worst-case.

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

Brute force scans forward from each day — O(n²), too slow. Monotonic decreasing stack finds next warmer in O(n): pop when current > top, set diff. Code next. ब्रूट फोर्स हर दिन से फॉरवर्ड स्कैन — O(n²), धीमा। मोनोटॉनिक डिक्रीजिंग स्टैक नेक्स्ट वार्मर O(n) में: करेंट > टॉप पर pop, diff सेट। कोड अगला।

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

"Given temperatures array, return days until warmer for each. Brute: For each i, scan j>i for first warmer, set diff or 0—O(n²), too slow. Optimal: Use a stack of indices, keeping decreasing temps order. Iterate i from 0 to n-1: While stack and temps[i] > temps[stack.top()], pop idx, result[idx] = i - idx (that's the next warmer). Push i. O(n) time since each index pushed and popped at most once. Space O(n). Example: [73,74,75,71,69,72,76,73] → pop 69 when 72>69, etc. For decreasing like [73,72,71] all 0. This monotonic stack is key for next greater problems—interviewers expect it." "टेम्परेचर्स ऐरे दिया, हर के लिए वार्मर तक दिन। ब्रूट: हर i के लिए j>i स्कैन फर्स्ट वार्मर, diff या 0—O(n²), धीमा। ऑप्टिमल: इंडेक्सेस का स्टैक, डिक्रीजिंग टेम्प्स। i 0 से n-1: जबकि स्टैक और temps[i] > temps[stack.top()], pop idx, result[idx] = i - idx (नेक्स्ट वार्मर)। i push। O(n) टाइम हर इंडेक्स push/pop एक बार। स्पेस O(n)। उदाहरण: [73,74,75,71,69,72,76,73] → 69 पर 72>69 pop etc। डिक्रीजिंग [73,72,71] सब 0। यह मोनोटॉनिक स्टैक नेक्स्ट ग्रेटर के लिए की—इंटरव्यूअर्स एक्सपेक्ट।"

Trees (Binary/Search) (Days 9-10) ट्रीज (बाइनरी/सर्च) (दिन 9-10)

Trees: Nodes with left/right. Traversal: DFS (recursion), BFS (queue). ट्रीज: लेफ्ट/राइट के साथ नोड्स। ट्रैवर्सल: DFS (रिकर्सन), BFS (क्यू)।

Binary Tree Inorder Traversal (LC 94) - LeetCode बाइनरी ट्री इनऑर्डर ट्रैवर्सल (LC 94) - लीटकोड

Problem: Inorder (left-root-right) array. समस्या: इनऑर्डर (लेफ्ट-रूट-राइट) ऐरे।

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

  • Primary: Tree, DFS Traversal
  • Secondary: Inorder
  • Frequency: High (Tree basics)

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

  • Big O: O(n) time, O(n) space worst (skewed).
  • Edge: Null [].
  • Self: Recursion easy; stack for iterative.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Return array? Handle null? n up to 10^4 nodes?" Quick heuristic: "Is this tree traversal? Hints ordering (inorder: left-root-right), adjacency (no), prefix (no), structure (DFS recur or stack)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "ऐरे रिटर्न? null हैंडल? n 10^4 नोड्स तक?" क्विक ह्यूरिस्टिक: "क्या यह ट्री ट्रैवर्सल? हिन्ट्स ऑर्डरिंग (inorder: लेफ्ट-रूट-राइट), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (DFS recur या स्टैक)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"inorder traversal", "left-root-right" Array output? Null nodes? Balanced? Tree DFS Inorder Breakdown: Recur left-root-right. Ask: Iterative or recursive OK?
"binary tree", "traversal" n=10^4? Skewed tree? Tree Traversal, Stack Simulation Think: Recur O(h) space; iterative for deep trees.

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

  • Recursive DFS: Helper function: If node null return; recur left, push val, recur right. O(n) time, O(h) space (recursion stack).
  • Iterative Stack: Use stack to simulate: While curr or stack, go left pushing, pop and push val, go right. O(n) time, O(h) space—avoids recursion depth issues.

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

Javascript
// Iterative Stack Simulation: Mimic recursion with explicit stack
class TreeNode { constructor(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }
function inorderTraversal(root) {
  const result = [];
  const stack = [];
  let curr = root;
  while (curr || stack.length) {
    while (curr) { // Go left
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop(); // Root
    result.push(curr.val);
    curr = curr.right; // Right
  }
  return result;
}
// Time: O(n), Space: O(n) - this is actually optimized; no "loose" for this simple problem
Why This Solution? यह सॉल्यूशन क्यों?
  • Iterative mimics recursion without call stack risk.
  • Handles skewed trees with O(n) space.
  • Clear pointer simulation.

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

Javascript
// Optimized (Recursive DFS): Simple recur for left-root-right
function inorderTraversal(root) {
  const result = [];
  function dfs(node) {
    if (!node) return; // Base
    dfs(node.left); // Left
    result.push(node.val); // Root
    dfs(node.right); // Right
  }
  dfs(root);
  return result;
}
// Time: O(n), Space: O(h) avg, O(n) worst
Why This Solution? यह सॉल्यूशन क्यों?
  • Recursive is concise and readable.
  • O(h) space average, easy for balanced trees.
  • Standard DFS pattern.

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

Iterative stack simulates recursion — O(n) space worst. Recursive inorder (left-root-right) is optimal O(n) time, O(h) space: clean and standard. Code here. इटरेटिव स्टैक रिकर्सन सिमुलेट — O(n) स्पेस वर्स्ट। रिकर्सिव inorder (लेफ्ट-रूट-राइट) ऑप्टिमल O(n) टाइम, O(h) स्पेस: क्लीन स्टैंडर्ड। कोड यहाँ।

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

"Inorder traversal: left-root-right order. Recursive is simplest: Define dfs(node): if !node return; dfs(left); result.push(val); dfs(right). Call dfs(root). O(n) time, O(h) space from recursion—fine for most trees, but skewed O(n). Iterative alternative: Stack and curr = root; while curr or stack: while curr, push curr, curr=left; curr=pop, push val, curr=right. Simulates the call stack. Both correct, but recur is cleaner unless depth worried. Edge: Null returns []. In JS, recursion is ok up to ~10k depth." "इनऑर्डर ट्रैवर्सल: लेफ्ट-रूट-राइट। रिकर्सिव सिंपल: dfs(node): !node रिटर्न; dfs(left); result.push(val); dfs(right)। dfs(root) कॉल। O(n) टाइम, O(h) स्पेस रिकर्सन से—ज्यादातर फाइन, लेकिन स्क्यूड O(n)। इटरेटिव अल्टरनेटिव: स्टैक curr=root; जबकि curr या स्टैक: जबकि curr, push curr, curr=left; curr=pop, push val, curr=right। कॉल स्टैक सिमुलेट। दोनों सही, लेकिन recur क्लीनर unless डेप्थ वरी। एज: null []। जेएस में, ~10k डेप्थ तक रिकर्सन ok।"

Same Tree (LC 100) - LeetCode सेम ट्री (LC 100) - लीटकोड

Problem: Are two trees same. समस्या: दो ट्रीज समान हैं।

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

  • Primary: Tree, Recursion
  • Secondary: Structure Match
  • Frequency: High (Tree comparison)

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

  • Big O: O(n) time, O(h) space.
  • Edge: Both null true, one null false.
  • Self: Recur check val and subtrees.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Same structure and values? Nulls match? n up to 10^4?" Quick heuristic: "Is this tree equality? Hints ordering (recur on subtrees), adjacency (no), prefix (no), structure (parallel DFS)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "सम संरचना वैल्यूज? nulls मैच? n 10^4 तक?" क्विक ह्यूरिस्टिक: "क्या यह ट्री इक्वालिटी? हिन्ट्स ऑर्डरिंग (सबट्रीज पर recur), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (पैरलल DFS)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"identical trees", "same structure values" Nulls equal? Vals exact? Subtrees? Tree Recursion Match Breakdown: Serialize compare → Recur val + subs. Ask: Early exit on mismatch?
"binary trees", "same tree" n=10^4? Balanced? Tree DFS Parallel Think: Base both null true; recur left/right after val check.

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

  • Serialization (Non-Optimized): Recursively build string like val,left,right (null as 'N'), compare strings. O(n) time, O(n) space for strings—works but wasteful.
  • Recursive (Optimal): Base: Both null true; one null or vals differ false. Else recur lefts and rights. O(n) time, O(h) space—visits min nodes needed.
  • BFS: Queues for both trees, level by level compare nodes. Similar complexity, but recursive cleaner.

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

Javascript
// Non-Optimized (Serialization): Build strings and compare
function isSameTree(p, q) {
  function serialize(root) {
    if (!root) return 'null';
    return root.val + ',' + serialize(root.left) + ',' + serialize(root.right);
  }
  return serialize(p) === serialize(q);
}
// Time: O(n), Space: O(n) strings
Why This Solution? यह सॉल्यूशन क्यों?
  • Serialization turns tree to comparable string.
  • Easy to verify structure and values.
  • Extra O(n) space for strings inefficient.

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

Javascript
// Optimized (Recursive Match): Check vals and subtrees recursively
function isSameTree(p, q) {
  if (!p && !q) return true; // Both null
  if (!p || !q || p.val !== q.val) return false; // Mismatch
  // Recur subtrees
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
// Time: O(n), Space: O(h)
Why This Solution? यह सॉल्यूशन क्यों?
  • Recursive mirrors tree structure naturally.
  • O(h) space, early exit on mismatch.
  • Minimal nodes visited.

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

Serialization to strings compares easily — O(n) space waste. Recursive check val then subtrees is optimal O(n) time, O(h) space: early mismatch exit. Code follows. स्ट्रिंग्स में सीरियलाइजेशन आसान कंपेयर — O(n) स्पेस वेस्ट। वैल चेक फिर सबट्रीज रिकर्सिव ऑप्टिमल O(n) टाइम, O(h) स्पेस: अर्ली मिसमैच एग्जिट। कोड आगे।

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

"To check if two binary trees are identical—same structure and values—recursive is best: If both null, true (matching empty). If one null or root.val differ, false. Else, recur on left pair and right pair, return both true. O(n) time worst, O(h) space. Edges: Both null true, one leaf one branch false. Alternative: Serialize to string (val + serialize(left) + serialize(right)), compare—but extra space. Or BFS queues compare level-wise. Recur shows tree recursion understanding—interview staple." "दो बाइनरी ट्रीज आइडेंटिकल चेक—सम संरचना वैल्यूज—रिकर्सिव बेस्ट: दोनों null तो ट्रू (एंप्टी मैच)। एक null या root.val differ तो फॉल्स। वरना, लेफ्ट पेयर राइट पेयर पर recur, दोनों ट्रू रिटर्न। O(n) टाइम वर्स्ट, O(h) स्पेस। एज: दोनों null ट्रू, एक लीफ एक ब्रांच फॉल्स। अल्टरनेटिव: स्ट्रिंग सीरियलाइज (val + serialize(left) + serialize(right)), कंपेयर—लेकिन एक्स्ट्रा स्पेस। या BFS क्यूज लेवल-वाइज। recur ट्री रिकर्सन समझ दिखाता—इंटरव्यू स्टेपल।"

Maximum Depth of Binary Tree (LC 104) - LeetCode मैक्सिमम डेप्थ ऑफ बाइनरी ट्री (LC 104) - लीटकोड

Problem: Max root to leaf depth. समस्या: रूट से लीफ मैक्स डेप्थ।

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

  • Primary: Tree, Recursion
  • Secondary: Depth/Height
  • Frequency: High (Tree metrics)

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

  • Big O: O(n) time, O(h) space.
  • Edge: Null 0.
  • Self: Recur max(left, right) +1.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Nodes to farthest leaf? Null 0? n up to 10^4?" Quick heuristic: "Is this tree height? Hints ordering (recur subtrees), adjacency (no), prefix (no), structure (max left/right +1)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "फर्सेस्ट लीफ तक नोड्स? null 0? n 10^4 तक?" क्विक ह्यूरिस्टिक: "क्या यह ट्री हाइट? हिन्ट्स ऑर्डरिंग (सबट्रीज recur), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (मैक्स लेफ्ट/राइट +1)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"maximum depth", "root to leaf" Node count or edges? Null 0? Balanced? Tree Recursion Height Breakdown: BFS levels → Recur max subs +1. Ask: Balanced tree?
"binary tree", "depth" n=10^4? Skewed? Tree DFS Post-Order Think: Base null 0; max(left depth, right depth) +1.

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

  • BFS Level Order (Non-Optimized): Queue starting with root, count levels by processing size at each layer. O(n) time, O(w) space (width)—natural for depth.
  • Recursive DFS (Optimal Space): Base null 0; return max(left depth, right depth) +1. O(n) time, O(h) space—visits all nodes once.

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

Javascript
// Non-Optimized (BFS Level Order): Queue for level-by-level depth
function maxDepth(root) {
  if (!root) return 0;
  let queue = [root], depth = 0;
  while (queue.length) {
    depth++; // Level
    let newQ = [];
    for (let node of queue) {
      if (node.left) newQ.push(node.left);
      if (node.right) newQ.push(node.right);
    }
    queue = newQ;
  }
  return depth;
}
// Time: O(n), Space: O(n) width
Why This Solution? यह सॉल्यूशन क्यों?
  • BFS naturally processes levels for depth.
  • Queue handles wide trees well.
  • O(n) space for queue in wide cases.

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

Javascript
// Optimized (Recursive DFS): Max of subtrees +1
function maxDepth(root) {
  if (!root) return 0; // Base
  // Max of left/right +1
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
// Time: O(n), Space: O(h)
Why This Solution? यह सॉल्यूशन क्यों?
  • Recursive concise, O(h) space better for deep trees.
  • Post-order like computation.
  • Easy to extend for other tree metrics.

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

BFS level order counts depths — O(n) space wide. Recursive max(subs) +1 is optimal O(n) time, O(h) space: simple and extendable. See code. BFS लेवल ऑर्डर डेप्थ्स काउंट — O(n) स्पेस वाइड। रिकर्सिव max(सब्स) +1 ऑप्टिमल O(n) टाइम, O(h) स्पेस: सिंपल एक्सटेंडेबल। कोड देखें।

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

"Max depth: Number of nodes from root to farthest leaf. Recursive: If !root return 0; else 1 + max(maxDepth(left), maxDepth(right)). O(n) time (all nodes), O(h) space. BFS alt: Queue with root, depth=0; while queue, depth++, newQ for children. Returns level count. Both fine, recur simpler. Edges: Null 0, single node 1, skewed h=n. Recur good for follow-ups like diameter." "मैक्स डेप्थ: रूट से फर्सेस्ट लीफ नोड्स। रिकर्सिव: !root 0; वरना 1 + max(maxDepth(left), maxDepth(right))। O(n) टाइम (सब नोड्स), O(h) स्पेस। BFS अल्ट: क्यू root, depth=0; जबकि क्यू, depth++, बच्चों के लिए newQ। लेवल काउंट। दोनों फाइन, recur सिंपलर। एज: null 0, सिंगल 1, स्क्यूड h=n। recur फॉलो-अप्स जैसे diameter के लिए गुड।"

Invert Binary Tree (LC 226) - LeetCode इनवर्ट बाइनरी ट्री (LC 226) - लीटकोड

Problem: Swap left/right. समस्या: लेफ्ट/राइट स्वैप।

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

  • Primary: Tree, Recursion
  • Secondary: Mirror/Invert
  • Frequency: High (Tree manipulation)

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

  • Big O: O(n) time, O(h) space.
  • Edge: Null null.
  • Self: Recur swap subtrees.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "In-place? Return root? n up to 10^4?" Quick heuristic: "Is this tree mirror? Hints ordering (recur swap children), adjacency (no), prefix (no), structure (pre/post-order swap)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "इन-प्लेस? रूट रिटर्न? n 10^4 तक?" क्विक ह्यूरिस्टिक: "क्या यह ट्री मिरर? हिन्ट्स ऑर्डरिंग (चिल्ड्रन स्वैप recur), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (pre/post-order स्वैप)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"invert/mirror tree", "swap left right" In-place? Subtrees too? Null unchanged? Tree Recursion Swap Breakdown: BFS queue → Recur swap children. Ask: Order of swap (pre/post)?
"binary tree", "invert" n=10^4? Balanced? Tree DFS Pre-Order Think: Base null return; swap after recur on children.

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

  • BFS (Non-Optimized): Queue root, while queue: Dequeue node, swap left/right, enqueue children if exist. O(n) time, O(w) space—level by level.
  • Recursive DFS (Optimal Space): Base null return null; Swap root.left and root.right after recursing on them (or before, order doesn't matter). Return root. O(n) time, O(h) space.

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

Javascript
// Non-Optimized (BFS): Queue level-by-level swap
function invertTree(root) {
  if (!root) return null;
  let queue = [root];
  while (queue.length) {
    let node = queue.shift();
    // Swap
    [node.left, node.right] = [node.right, node.left];
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return root;
}
// Time: O(n), Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • BFS visits all nodes level-wise.
  • Queue for children ensures full traversal.
  • O(n) space for wide trees.

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

Javascript
// Optimized (Recursive Swap): Recur and swap children
function invertTree(root) {
  if (!root) return null; // Base
  // Swap children
  [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
  return root;
}
// Time: O(n), Space: O(h)
Why This Solution? यह सॉल्यूशन क्यों?
  • Recursive elegant, mirrors tree swap.
  • O(h) space, in-place modification.
  • Pre or post-order swap works.

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

BFS queue swaps level-by-level — O(n) space wide. Recursive swap children is optimal O(n) time, O(h) space: simple mirror. Code next. BFS क्यू लेवल-बाय-लेवल स्वैप — O(n) स्पेस वाइड। रिकर्सिव चिल्ड्रन स्वैप ऑप्टिमल O(n) टाइम, O(h) स्पेस: सिंपल मिरर। कोड अगला।

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

"Invert binary tree: Mirror left and right subtrees. Recursive: If !root return null; Then [root.left, root.right] = [invert(root.right), invert(root.left)]; Return root. O(n) time (all nodes), O(h) space. Swap can be before or after recur—post-order ensures children inverted first. BFS alt: Queue root, dequeue swap enqueue children. Recur preferred for simplicity. Edges: Null unchanged, leaf unchanged. Fun fact: Google interview classic—'Write code to reverse a binary tree.'" "बाइनरी ट्री इनवर्ट: लेफ्ट राइट सबट्रीज मिरर। रिकर्सिव: !root null; फिर [root.left, root.right] = [invert(root.right), invert(root.left)]; root रिटर्न। O(n) टाइम (सब नोड्स), O(h) स्पेस। स्वैप recur से पहले या बाद—post-order बच्चों को पहले। BFS अल्ट: क्यू root, deque स्वैप children enqueue। recur सिंप्लिसिटी के लिए प्रेफर्ड। एज: null अनचेंज्ड, लीफ अनचेंज्ड। फन फैक्ट: गूगल इंटरव्यू क्लासिक—'कोड लिखो बाइनरी ट्री रिवर्स।' "

Trees (Advanced) (Days 11-12) ट्रीज (एडवांस्ड) (दिन 11-12)

Build on basics; height, diameter, validation. बेसिक्स पर बिल्ड; हाइट, डायमीटर, वैलिडेशन।

Balanced Binary Tree (LC 110) - LeetCode बैलेंस्ड बाइनरी ट्री (LC 110) - लीटकोड

Problem: Is height-balanced (|left-right| <=1). समस्या: हाइट-बैलेंस्ड (|लेफ्ट-राइट| <=1)।

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

  • Primary: Tree, Recursion
  • Secondary: Height Balance
  • Frequency: Medium (Tree validation)

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

  • Big O: O(n) time, O(h) space.
  • Edge: Skewed false.
  • Self: Recur height, check diff; -1 for unbalanced.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Every subtree balanced? |hL - hR| <=1? n up to 10^4?" Quick heuristic: "Is this AVL-like balance check? Hints ordering (post-order height), adjacency (no), prefix (no), structure (recur with flag for imbalance)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "हर सबट्री बैलेंस्ड? |hL - hR| <=1? n 10^4 तक?" क्विक ह्यूरिस्टिक: "क्या यह AVL-लाइक बैलेंस चेक? हिन्ट्स ऑर्डरिंग (post-order हाइट), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (इम्बैलेंस फ्लैग के साथ recur)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"height balanced", "|left - right| <=1 every subtree" Every node? Height edges or nodes? n=10^4? Tree Recursion with Flag Breakdown: Separate heights + checks → Single pass bottom-up. Ask: Skewed trees?
"binary tree", "balanced" Null true? AVL strict? Tree Post-Order Height Think: Return height or -1 to propagate imbalance.

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

  • Top-Down (Brute Force): For each node, compute heights of left/right, check |diff| <=1, and recur subtrees. O(n²) time if skewed (repeated height calls).
  • Bottom-Up (Optimal): Post-order: Compute leftH and rightH; if either -1 (unbalanced), return -1. Else if |leftH - rightH| >1 return -1; else max+1. Propagate imbalance. O(n) time.

Non-Optimized Solution (Top-Down) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (टॉप-डाउन)

Javascript
// Brute Force (Top-Down Height): Compute heights per node separately
function height(node) {
  if (!node) return 0;
  return Math.max(height(node.left), height(node.right)) + 1;
}
function isBalanced(root) {
  if (!root) return true;
  // Check diff
  const diff = Math.abs(height(root.left) - height(root.right));
  if (diff > 1) return false;
  // Recur
  return isBalanced(root.left) && isBalanced(root.right);
}
// Time: O(n^2) - repeated heights, Space: O(h)
Why This Solution? यह सॉल्यूशन क्यों?
  • Separate height function clear.
  • Checks diff at each node.
  • O(n²) due to recomputing heights.

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

Javascript
// Optimized (Bottom-Up with Flag): Propagate -1 for unbalanced
function isBalanced(root) {
  function getHeight(node) {
    if (!node) return 0; // Base height
    const leftH = getHeight(node.left); // Left
    if (leftH === -1) return -1; // Propagate unbalanced
    const rightH = getHeight(node.right); // Right
    if (rightH === -1) return -1;
    // Check diff
    if (Math.abs(leftH - rightH) > 1) return -1;
    return Math.max(leftH, rightH) + 1; // Height
  }
  return getHeight(root) !== -1;
}
// Time: O(n) - each node once, Space: O(h)
Why This Solution? यह सॉल्यूशन क्यों?
  • O(n) by computing height once per node.
  • Early propagation of imbalance.
  • Combines height and balance check.

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

Top-down computes heights repeatedly — O(n²) skewed. Bottom-up with -1 flag for imbalance is optimal O(n): single pass post-order. Code below. टॉप-डाउन हाइट्स रीपीट — O(n²) स्क्यूड। -1 फ्लैग से बॉटम-अप इम्बैलेंस ऑप्टिमल O(n): सिंगल पास post-order। कोड नीचे।

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

"Balanced if every subtree |leftH - rightH| <=1. Top-down naive: Define height recur, at each node check diff and recur children—O(n²) skewed. Optimized bottom-up: getHeight returns height or -1 if unbalanced. Compute leftH = getHeight(left); if -1 return -1. Same right. If |leftH-rightH|>1 return -1; else return max+1. Root call != -1 is true. O(n) time, each node once, O(h) space. Edges: Null true, skewed false. This optimizes by avoiding redundant height calls—key insight." "हर सबट्री |leftH - rightH| <=1 तो बैलेंस्ड। टॉप-डाउन नेव: हाइट recur डिफाइन, हर नोड पर diff चेक children recur—O(n²) स्क्यूड। ऑप्टिमाइज्ड बॉटम-अप: getHeight हाइट या -1 अगर अनबैलेंस्ड। leftH = getHeight(left); -1 तो -1। राइट सम। |leftH-rightH|>1 तो -1; वरना max+1। रूट != -1 ट्रू। O(n) टाइम, हर नोड एक बार, O(h) स्पेस। एज: null ट्रू, स्क्यूड फॉल्स। यह रिडंडेंट हाइट कॉल्स अवॉइड—की इनसाइट।"

Diameter of Binary Tree (LC 543) - LeetCode डायमीटर ऑफ बाइनरी ट्री (LC 543) - लीटकोड

Problem: Longest path nodes. समस्या: लॉन्गेस्ट पाथ नोड्स।

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

  • Primary: Tree, Recursion
  • Secondary: Diameter/Paths
  • Frequency: Medium (Tree paths)

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

  • Big O: O(n) time, O(h) space.
  • Edge: Null 0.
  • Self: Max (left+right) at each, track global.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Nodes count? Any two nodes? n up to 10^4?" Quick heuristic: "Is this tree diameter? Hints ordering (post-order heights), adjacency (no), prefix (no), structure (max left+right through each)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "नोड्स काउंट? किसी दो नोड्स? n 10^4 तक?" क्विक ह्यूरिस्टिक: "क्या यह ट्री डायमीटर? हिन्ट्स ऑर्डरिंग (post-order हाइट्स), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (हर थ्रू max left+right)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"diameter", "longest path nodes" Nodes or edges? Through root? n=10^4? Tree Recursion Heights Breakdown: Brute per-node paths → Update during height. Ask: Max path any nodes?
"binary tree", "diameter" Skewed? Balanced? Tree Post-Order Global Max Think: At each node, leftH + rightH candidate; track max.

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

  • Brute Force (Per-Node Paths): For each node, compute height left + height right as path through it, max over all + sub-diameters. O(n²) from repeated heights.
  • During Height (Optimal): Global maxDia=0. In height recur: leftH=getHeight(left), rightH=getHeight(right), update maxDia = max(maxDia, leftH+rightH), return max(leftH,rightH)+1. O(n) time.

Non-Optimized Solution (Per-Node) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (प्रति-नोड)

Javascript
// Brute Force (Per-Node Paths): Height for each possible root
function diameterOfBinaryTree(root) {
  function height(node) { if (!node) return 0; return Math.max(height(node.left), height(node.right)) + 1; }
  function diameterThrough(node) {
    if (!node) return 0;
    return height(node.left) + height(node.right);
  }
  if (!root) return 0;
  // Max of through root, left dia, right dia
  return Math.max(diameterThrough(root), diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right));
}
// Time: O(n^2), Space: O(h)
Why This Solution? यह सॉल्यूशन क्यों?
  • Explicitly computes paths through each node.
  • Recursive max over all possibilities.
  • O(n²) due to height recomputes.

Optimized Solution (During Height) ऑप्टिमाइज्ड सॉल्यूशन (हाइट के दौरान)

Javascript
// Optimized (During Height Traversal): Update global max at each node
function diameterOfBinaryTree(root) {
  let maxDia = 0; // Global
  function getHeight(node) {
    if (!node) return 0;
    const leftH = getHeight(node.left);
    const rightH = getHeight(node.right);
    // Update max with through current
    maxDia = Math.max(maxDia, leftH + rightH);
    return Math.max(leftH, rightH) + 1;
  }
  getHeight(root);
  return maxDia;
}
// Time: O(n), Space: O(h)
Why This Solution? यह सॉल्यूशन क्यों?
  • O(n) by updating during single traversal.
  • Global tracks max path through any node.
  • Combines with height computation.

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

Brute computes left+right heights per node — O(n²) repeated work. Updating max during single height traversal is optimal O(n): candidate paths at each. Code here. ब्रूट प्रति नोड left+right हाइट्स — O(n²) रीपीटेड। सिंगल हाइट ट्रैवर्सल के दौरान मैक्स अपडेट ऑप्टिमल O(n): हर पर कैंडिडेट पाथ्स। कोड यहाँ।

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

"Diameter: Longest path between any two nodes (nodes count). Brute: For each node, leftH + rightH as through-path, max with sub-diameters—O(n²). Optimized: While computing heights recursively, at each node update global max with leftH + rightH (path through root). Return height as max(left,right)+1. getHeight(root), return maxDia. O(n) time, since height visits all, O(h) space. Note: Diameter may not pass root. Edges: Single node 0, line tree n-1. Ties to balanced tree height." "डायमीटर: किसी दो नोड्स के बीच लॉन्गेस्ट पाथ (नोड्स काउंट)। ब्रूट: हर नोड पर leftH + rightH थ्रू-पाथ, सब-डायमीटर्स के साथ मैक्स—O(n²)। ऑप्टिमाइज्ड: हाइट्स कंप्यूट करते recur, हर नोड पर ग्लोबल मैक्स leftH + rightH से अपडेट (रूट थ्रू पाथ)। हाइट max(left,right)+1। getHeight(root), maxDia रिटर्न। O(n) टाइम, हाइट सब विजिट, O(h) स्पेस। नोट: डायमीटर रूट से न पास। एज: सिंगल 0, लाइन n-1। बैलेंस्ड ट्री हाइट से टाई।"

Binary Tree Level Order Traversal (LC 102) - LeetCode बाइनरी ट्री लेवल ऑर्डर ट्रैवर्सल (LC 102) - लीटकोड

Problem: Array of levels. समस्या: लेवल्स का ऐरे।

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

  • Primary: Tree, BFS
  • Secondary: Level Order
  • Frequency: High (Tree traversal)

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

  • Big O: O(n) time, O(n) space.
  • Edge: Null [].
  • Self: BFS queue, process level size.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Array of arrays by level? Root level 0? n up to 2000?" Quick heuristic: "Is this level-order traversal? Hints ordering (BFS queue), adjacency (no), prefix (no), structure (process queue size per level)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "लेवल्स से ऐरे ऑफ ऐरे? रूट 0? n 2000 तक?" क्विक ह्यूरिस्टिक: "क्या यह लेवल-ऑर्डर ट्रैवर्सल? हिन्ट्स ऑर्डरिंग (BFS क्यू), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (प्रति लेवल क्यू साइज प्रोसेस)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"level order traversal", "array of levels" By level? Null nodes? n=2000? Tree BFS Level Order Breakdown: DFS with level param → BFS queue size. Ask: Reverse levels? (No)
"binary tree", "level order" Balanced? Skewed? Tree Queue BFS Think: While queue, for current size: Dequeue that many, collect vals, enqueue children.

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

  • DFS with Levels (Non-Optimized): Recursive dfs(node, level): If levels[level] undefined, init []; push val; recur left/right with level+1. O(n) time, O(n) space for levels array.
  • BFS (Optimal): Queue with root; while queue: For current level size, dequeue that many, collect vals in level array, enqueue children. Push level to result. O(n) time, O(w) space.

Non-Optimized Solution (DFS with Levels) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (DFS विद लेवल्स)

Javascript
// Non-Optimized (DFS with Levels): Recursion tracks level
function levelOrder(root) {
  const levels = [];
  function dfs(node, level) {
    if (!node) return;
    if (!levels[level]) levels[level] = []; // New level
    levels[level].push(node.val);
    dfs(node.left, level + 1);
    dfs(node.right, level + 1);
  }
  dfs(root, 0);
  return levels;
}
// Time: O(n), Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • DFS uses recursion with level tracking.
  • Builds levels array dynamically.
  • O(n) space for result anyway.

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

Javascript
// Optimized (BFS Queue): Process levels by queue size
function levelOrder(root) {
  if (!root) return [];
  const result = [], queue = [root];
  while (queue.length) {
    const level = [], len = queue.length; // Current size
    for (let i = 0; i < len; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level); // Add level
  }
  return result;
}
// Time: O(n), Space: O(n)
Why This Solution? यह सॉल्यूशन क्यों?
  • BFS naturally groups by levels.
  • Uses queue size to process per level.
  • Standard for level-order.

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

DFS recursion with level param builds arrays — works but less natural. BFS queue processing by size per level is optimal O(n): standard for level order. Code follows. लेवल param के साथ DFS रिकर्सन ऐरे बिल्ड — वर्क्स लेकिन कम नेचुरल। साइज प्रति लेवल BFS क्यू प्रोसेसिंग ऑप्टिमल O(n): लेवल ऑर्डर स्टैंडर्ड। कोड आगे।

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

"Level order: Root level 0, then children, etc., as array of arrays. BFS perfect: If !root [], else queue.push(root), result=[]; while queue: level=[], len=queue.length; for i< len: node=queue.shift(), level.push(node.val), if left/right queue.push. result.push(level). O(n) time, O(w) space queue. DFS alt: Recur with level param, push to levels[level]. But BFS cleaner for levels. Edges: Null [], single [ [val] ]. Key: Use len to bound per level loop." "लेवल ऑर्डर: रूट लेवल 0, फिर बच्चों, etc., ऐरे ऑफ ऐरे। BFS परफेक्ट: !root [], वरना queue.push(root), result=[]; जबकि queue: level=[], len=queue.length; i< len: node=shift, level.push(val), left/right push। result.push(level)। O(n) टाइम, O(w) स्पेस क्यू। DFS अल्ट: level param recur, levels[level] push। लेकिन BFS क्लीनर। एज: null [], सिंगल [ [val] ]। की: len से प्रति लेवल बाउंड लूप।"

Validate Binary Search Tree (LC 98) - LeetCode वैलिडेट बाइनरी सर्च ट्री (LC 98) - लीटकोड

Problem: Is valid BST (left < root < right). समस्या: वैलिड BST (लेफ्ट < रूट < राइट)।

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

  • Primary: Tree, BST Validation
  • Secondary: Recursion Bounds
  • Frequency: High (BST properties)

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

  • Big O: O(n) time, O(h) space.
  • Edge: Duplicates invalid, skewed.
  • Self: Recur with min/max bounds.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Strict < or <=? Duplicates allowed? n up to 10^4?" Quick heuristic: "Is this BST validation? Hints ordering (inorder sorted), adjacency (no), prefix (no), structure (bounds passing or inorder check)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "स्ट्रिक्ट < या <=? डुप्लिकेट्स अलाउड? n 10^4 तक?" क्विक ह्यूरिस्टिक: "क्या यह BST वैलिडेशन? हिन्ट्स ऑर्डरिंग (inorder सॉर्टेड), एडजेसेंसी (नहीं), प्रीफिक्स (नहीं), स्ट्रक्चर (बाउंड्स पासिंग या inorder चेक)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"valid BST", "left < root < right all subtrees" Strict < ? Duplicates? n=10^4? Tree Recursion Bounds Breakdown: Inorder sorted check → Bounds pass. Ask: Duplicates invalid?
"binary search tree", "validate" Skewed? Balanced? Tree Inorder or Bounds Think: Pass min/max to enforce property without array.

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

  • Inorder Traversal (Non-Optimized): Do inorder, check if strictly increasing (no dups). O(n) time, O(n) space array—validates BST property.
  • Recursive Bounds (Optimal Space): Validate(node, min=-inf, max=inf): If val <=min or >=max false; recur left (min, node.val), right (node.val, max). O(n) time, O(h) space—no extra array.

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

Javascript
// Non-Optimized (Inorder to Array): Traverse and check sorted
function isValidBST(root) {
  const inorder = [];
  function dfs(node) {
    if (!node) return;
    dfs(node.left);
    inorder.push(node.val);
    dfs(node.right);
  }
  dfs(root);
  // Check increasing, no dups
  for (let i = 1; i < inorder.length; i++) {
    if (inorder[i] <= inorder[i-1]) return false;
  }
  return true;
}
// Time: O(n), Space: O(n) array
Why This Solution? यह सॉल्यूशन क्यों?
  • Inorder gives sorted order for BST check.
  • Easy to verify increasing sequence.
  • O(n) space for inorder array.

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

Javascript
// Optimized (Recursive Bounds): Pass min/max constraints
function isValidBST(root) {
  function validate(node, min = -Infinity, max = Infinity) {
    if (!node) return true; // Base
    if (node.val <= min || node.val >= max) return false; // Bound check
    // Left: max = node.val, right: min = node.val
    return validate(node.left, min, node.val) && validate(node.right, node.val, max);
  }
  return validate(root);
}
// Time: O(n), Space: O(h)
Why This Solution? यह सॉल्यूशन क्यों?
  • Bounds pass prunes invalid quickly.
  • O(h) space, no array needed.
  • Directly enforces BST property.

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

Inorder traversal to array then check sorted — O(n) space extra. Recursive with min/max bounds is optimal O(n) time, O(h) space: enforces property directly. Code next. इनऑर्डर ऐरे फिर सॉर्टेड चेक — O(n) एक्स्ट्रा स्पेस। मिन/मैक्स बाउंड्स रिकर्सिव ऑप्टिमल O(n) टाइम, O(h) स्पेस: प्रॉपर्टी डायरेक्ट एनफोर्स। कोड अगला।

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

"Valid BST: Left < root < right recursively. One way: Inorder traversal to array, check strictly increasing (BST sorted). O(n) time/space. Better: Recursive with bounds—validate(node, low=-inf, high=inf): If node.val <=low or >=high false. Recur left (low, node.val), right (node.val, high). True if both. O(n) time, O(h) space. Handles dups as false (<=). Edges: Single true, [5,1,4,null,null,3,6] false (1<5 but 3>1 invalid). Bounds prevent wrong placements without full inorder." "वैलिड BST: लेफ्ट < रूट < राइट रिकर्सिवली। एक तरीका: इनऑर्डर ऐरे, स्ट्रिक्टली इंक्रीजिंग चेक (BST सॉर्टेड)। O(n) टाइम/स्पेस। बेहतर: बाउंड्स के साथ रिकर्सिव—validate(node, low=-inf, high=inf): node.val <=low या >=high फॉल्स। left (low, node.val) recur, right (node.val, high)। दोनों ट्रू। O(n) टाइम, O(h) स्पेस। डुप्स फॉल्स (<=)। एज: सिंगल ट्रू, [5,1,4,null,null,3,6] फॉल्स (1<5 लेकिन 3>1 इनवैलिड)। बाउंड्स फुल इनऑर्डर बिना गलत प्लेसमेंट प्रिवेंट।"

Graphs (Days 13-14) ग्राफ्स (दिन 13-14)

Graphs: Maps for adj lists. Traversal: DFS/BFS. ग्राफ्स: एडज लिस्ट्स के लिए मैप्स। ट्रैवर्सल: DFS/BFS।

Number of Islands (LC 200) - LeetCode नंबर ऑफ आइलैंड्स (LC 200) - लीटकोड

Problem: Count '1' islands in grid. समस्या: ग्रिड में '1' आइलैंड्स काउंट।

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

  • Primary: Graph/Grid, DFS/BFS
  • Secondary: Connected Components
  • Frequency: High (Grid traversal)

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

  • Big O: O(mn) time, O(mn) space worst.
  • Edge: Empty 0.
  • Self: DFS/BFS mark visited.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "4-dir adjacent? Modify grid OK? m,n up to 300?" Quick heuristic: "Is this connected components in grid? Hints ordering (DFS/BFS flood), adjacency (yes, 4-dir), prefix (no), structure (mark visited as '0')?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "4-डिर एडजेसेंट? ग्रिड मॉडिफाई OK? m,n 300 तक?" क्विक ह्यूरिस्टिक: "क्या यह ग्रिड में कनेक्टेड कंपोनेंट्स? हिन्ट्स ऑर्डरिंग (DFS/BFS फ्लड), एडजेसेंसी (हां, 4-डिर), प्रीफिक्स (नहीं), स्ट्रक्चर ('0' मार्क विजिटेड)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"number of islands", "connected '1's" 4-dir? Modify grid? m,n=300? Grid DFS/BFS Components Breakdown: Union-find → Flood fill mark. Ask: 8-dir? (No)
"grid", "islands" Empty rows? All '0'? Graph Grid Traversal Think: On '1', count++, DFS/BFS mark all connected '0'.

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

  • Union-Find: Treat each '1' as component, union adjacent '1's, count roots. O(mn α(mn)) time (near linear), O(mn) space—good for dynamic but overkill here.
  • BFS (Queue-based): Traverse grid, on '1' increment count, BFS to mark connected '1's as '0' (visited). O(mn) time, O(mn) space queue worst—explores level by level.
  • DFS (Recursive, Optimal Space): Traverse, on '1' count++, recur DFS on four directions marking '0'. O(mn) time, O(mn) stack space skewed—simpler, no queue.

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

Javascript
// Non-Optimized (BFS Queue): Explore each island level by level
function numIslands(grid) {
  if (!grid.length) return 0;
  const m = grid.length, n = grid[0].length;
  let count = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === '1') {
        count++; // New island
        const queue = [[i,j]];
        while (queue.length) {
          const [x,y] = queue.shift();
          if (x<0 || x>=m || y<0 || y>=n || grid[x][y]!=='1') continue;
          grid[x][y] = '0'; // Mark
          queue.push([x-1,y], [x+1,y], [x,y-1], [x,y+1]); // Neighbors
        }
      }
    }
  }
  return count;
}
// Time: O(m*n), Space: O(m*n) queue worst
Why This Solution? यह सॉल्यूशन क्यों?
  • BFS explores islands level by level.
  • Queue handles connected components.
  • O(mn) space for queue in large islands.

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

Javascript
// Optimized (DFS Recursive): Flood fill marks connected land
function numIslands(grid) {
  if (!grid.length) return 0;
  const m = grid.length, n = grid[0].length;
  function dfs(i, j) {
    if (i<0 || i>=m || j<0 || j>=n || grid[i][j]!=='1') return;
    grid[i][j] = '0'; // Mark
    dfs(i-1, j); dfs(i+1, j); dfs(i, j-1); dfs(i, j+1); // Recur neighbors
  }
  let count = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === '1') {
        count++;
        dfs(i, j);
      }
    }
  }
  return count;
}
// Time: O(m*n), Space: O(m*n) call stack worst (flood fill)
Why This Solution? यह सॉल्यूशन क्यों?
  • DFS recursive simpler, no explicit queue.
  • Marks visited in-place efficiently.
  • Flood fill explores deeply first.

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

Union-find unions lands — near O(mn) but complex. BFS queues components — O(mn) space. DFS flood fill is optimal O(mn) time, recursive simplicity. Code here. यूनियन-फाइंड लैंड्स यूनियन — near O(mn) लेकिन कॉम्प्लेक्स। BFS क्यू कंपोनेंट्स — O(mn) स्पेस। DFS फ्लड फिल ऑप्टिमल O(mn) टाइम, रिकर्सिव सिंप्लिसिटी। कोड यहाँ।

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

"For Number of Islands, grid of '1' land '0' water, count connected '1' components (4-dir). Traverse every cell: If '1', increment count (new island), then DFS/BFS to mark all connected '1's as '0' (visited). For DFS: Recur on up/down/left/right if valid '1', mark current '0'. O(mn) time (visit each once), O(mn) space stack/queue worst. BFS alt: Queue start cell, dequeue mark enqueue neighbors. Union-find possible but DFS/BFS standard for grids. Edges: Empty grid 0, all '0' 0, single '1' 1. In JS, modify grid in-place—interviewers like flood fill for components." "नंबर ऑफ आइलैंड्स के लिए, '1' लैंड '0' वॉटर ग्रिड, 4-डिर कनेक्टेड '1' कंपोनेंट्स काउंट। हर सेल ट्रैवर्स: '1' तो काउंट++ (न्यू आइलैंड), फिर DFS/BFS से कनेक्टेड सब '1' को '0' मार्क (विजिटेड)। DFS: वैलिड '1' पर up/down/left/right recur, करेंट '0' मार्क। O(mn) टाइम (हर एक विजिट), O(mn) स्पेस स्टैक/क्यू वर्स्ट। BFS अल्ट: क्यू स्टार्ट सेल, deque मार्क neighbors enqueue। यूनियन-फाइंड पॉसिबल लेकिन DFS/BFS ग्रिड्स के लिए स्टैंडर्ड। एज: एंप्टी 0, सब '0' 0, सिंगल '1' 1। जेएस में, in-place मॉडिफाई—इंटरव्यूअर्स कंपोनेंट्स के लिए फ्लड फिल लाइक।"

Clone Graph (LC 133) - LeetCode क्लोन ग्राफ (LC 133) - लीटकोड

Problem: Deep copy graph. समस्या: डीप कॉपी ग्राफ।

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

  • Primary: Graph, DFS/BFS
  • Secondary: Copy with Cycles
  • Frequency: Medium (Graph copy)

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

  • Big O: O(V+E) time, O(V) space.
  • Edge: Null null.
  • Self: BFS/DFS, Map old to new nodes.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Deep copy nodes/edges? Cycles? V up to 100?" Quick heuristic: "Is this graph copy? Hints ordering (DFS/BFS visit), adjacency (yes), prefix (no), structure (Map old→new for cycles)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "नोड्स/एजेज डीप कॉपी? साइकल्स? V 100 तक?" क्विक ह्यूरिस्टिक: "क्या यह ग्राफ कॉपी? हिन्ट्स ऑर्डरिंग (DFS/BFS विजिट), एडजेसेंसी (हां), प्रीफिक्स (नहीं), स्ट्रक्चर (साइकल्स के लिए old→new मैप)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"clone graph", "deep copy" Cycles? Undirected? V=100? Graph DFS with Memo Breakdown: Naive recur → Map to avoid cycles. Ask: Return cloned node?
"undirected graph", "nodes neighbors" Disconnected? Self-loops? Graph Traversal Copy Think: BFS/DFS, create new nodes, link cloned neighbors.

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

  • Without Memo (Brute Force): Recur/iterate create new node, copy neighbors recur—O(V+E) time, but infinite loop on cycles.
  • BFS with Map: Queue start, Map old→new. While queue: Dequeue old, if not in Map create new, set neighbors to cloned (queue them). O(V+E) time, O(V) space.
  • DFS with Map (Optimal): Recur dfs(old): If in Map return it; create new, Map set, for neighbors push dfs(neighbor). Handles cycles via memo. O(V+E) time, O(V) space.

Non-Optimized Solution (No Memo) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (नो मेमो)

Javascript
// Brute Force (No Memo): Recur without cycle check (assumes acyclic)
class Node { constructor(val = 0, neighbors = []) { this.val = val; this.neighbors = neighbors; } }
function cloneGraph(node) {
  if (!node) return null;
  const newNode = new Node(node.val);
  // Recur neighbors
  for (let neighbor of node.neighbors) {
    newNode.neighbors.push(cloneGraph(neighbor));
  }
  return newNode;
}
// Time: O(V+E), but infinite if cycles (loose assumption no cycles)
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple recursion for tree-like graphs.
  • Creates nodes and links directly.
  • Fails on cycles (infinite recur).

Optimized Solution (DFS with Map) ऑप्टिमाइज्ड सॉल्यूशन (DFS विद मैप)

Javascript
// Optimized (DFS with Map): Memoize cloned nodes to handle cycles
function cloneGraph(node) {
  if (!node) return null;
  const map = new Map(); // Old to new
  function dfs(old) {
    if (map.has(old)) return map.get(old); // Already cloned
    const newNode = new Node(old.val); // Create
    map.set(old, newNode); // Store
    // Clone neighbors
    for (let neighbor of old.neighbors) {
      newNode.neighbors.push(dfs(neighbor));
    }
    return newNode;
  }
  return dfs(node);
}
// Time: O(V+E), Space: O(V)
Why This Solution? यह सॉल्यूशन क्यों?
  • Map memos cloned nodes, prevents cycles.
  • DFS explores deeply, efficient for graphs.
  • Visits each node/edge once.

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

Naive recursion copies without memo — infinite on cycles. DFS with Map old→new handles cycles O(V+E): memo prevents re-clone. Code below. नेव रिकर्सन मेमो बिना कॉपी — साइकल्स पर इन्फिनिट। old→new मैप से DFS साइकल्स हैंडल O(V+E): मेमो री-क्लोन प्रिवेंट। कोड नीचे।

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

"Clone undirected graph with possible cycles: Deep copy nodes and edges. Naive recur: Create new node, recur neighbors push copies—but loops infinitely on cycles. Fix with Map old→newNode. DFS: dfs(old): If map.has(old) return it; newNode=Node(old.val), map.set(old,newNode); for neighbor: newNode.neighbors.push(dfs(neighbor)). Start dfs(node). O(V+E) time (visit each once), O(V) space map/stack. BFS alt: Queue node, while: If not mapped create, queue neighbors after cloning. Map handles revisits. Edges: Null null, single node itself. In JS, Map with Node keys works—interviewers test cycle handling." "अंडायरेक्टेड ग्राफ क्लोन साइकल्स पॉसिबल: नोड्स एजेज डीप कॉपी। नेव recur: न्यू नोड क्रिएट, neighbors recur push कॉपीज—लेकिन साइकल्स पर इन्फिनिट लूप। फिक्स मैप old→newNode। DFS: dfs(old): map.has तो रिटर्न; newNode=Node(old.val), set, for neighbor: push dfs(neighbor)। dfs(node) स्टार्ट। O(V+E) टाइम (हर एक विजिट), O(V) स्पेस मैप/स्टैक। BFS अल्ट: क्यू node, जबकि: नॉट मैप्ड क्रिएट, neighbors क्यू क्लोन बाद। मैप रीविजिट्स हैंडल। एज: null null, सिंगल खुद। जेएस में, Node कीज के साथ मैप वर्क्स—इंटरव्यूअर्स साइकल हैंडलिंग टेस्ट।"

Max Area of Island (LC 695) - LeetCode मैक्स एरिया ऑफ आइलैंड (LC 695) - लीटकोड

Problem: Largest '1' island area. समस्या: सबसे बड़ा '1' आइलैंड एरिया।

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

  • Primary: Graph/Grid, DFS
  • Secondary: Connected Components Size
  • Frequency: Medium (Grid areas)

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

  • Big O: O(mn) time, O(mn) space.
  • Edge: No islands 0.
  • Self: Like numIslands, but track size in DFS.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "4-dir? Modify grid? m,n up to 50?" Quick heuristic: "Is this max component size in grid? Hints ordering (DFS return size), adjacency (yes), prefix (no), structure (flood fill count)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "4-डिर? ग्रिड मॉडिफाई? m,n 50 तक?" क्विक ह्यूरिस्टिक: "क्या यह ग्रिड में मैक्स कंपोनेंट साइज? हिन्ट्स ऑर्डरिंग (DFS साइज रिटर्न), एडजेसेंसी (हां), प्रीफिक्स (नहीं), स्ट्रक्चर (फ्लड फिल काउंट)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"max area of island", "connected '1's" 4-dir? Largest only? m,n=50? Grid DFS Size Return Breakdown: Like islands count → DFS returns area. Ask: 0/1 only?
"grid", "island area" All '0'? Single cell? Graph Grid Flood Fill Think: On '1', max = max(max, dfs(i,j)); dfs returns 1 + sum neighbors.

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

  • BFS Count (Non-Optimized): Traverse, on '1' BFS queue start, count=0, dequeue mark '0' count++ enqueue neighbors if '1'. Update maxArea. O(mn) time, O(mn) queue.
  • DFS Count (Optimal): Traverse, on '1' area = dfs(i,j) where dfs: If invalid/'0' 0; mark '0', return 1 + sum dfs four dirs. Update max. O(mn) time, O(mn) stack—returns size.

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

Javascript
// Non-Optimized (BFS Queue): Count each island with queue
function maxAreaOfIsland(grid) {
  if (!grid.length) return 0;
  const m = grid.length, n = grid[0].length;
  let maxArea = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        let area = 0;
        const queue = [[i,j]];
        while (queue.length) {
          const [x,y] = queue.shift();
          if (x<0 || x>=m || y<0 || y>=n || grid[x][y]!==1) continue;
          grid[x][y] = 0;
          area++; // Count
          queue.push([x-1,y], [x+1,y], [x,y-1], [x,y+1]);
        }
        maxArea = Math.max(maxArea, area);
      }
    }
  }
  return maxArea;
}
// Time: O(m*n), Space: O(m*n)
Why This Solution? यह सॉल्यूशन क्यों?
  • BFS counts level by level.
  • Queue for connected '1's.
  • Space O(mn) for large islands.

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

Javascript
// Optimized (DFS Recursive): Return area from each land cell
function maxAreaOfIsland(grid) {
  if (!grid.length) return 0;
  const m = grid.length, n = grid[0].length;
  function dfs(i, j) {
    if (i<0 || i>=m || j<0 || j>=n || grid[i][j]!==1) return 0;
    grid[i][j] = 0; // Mark
    // Count 1 + neighbors
    return 1 + dfs(i-1,j) + dfs(i+1,j) + dfs(i,j-1) + dfs(i,j+1);
  }
  let maxArea = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        maxArea = Math.max(maxArea, dfs(i, j));
      }
    }
  }
  return maxArea;
}
// Time: O(m*n), Space: O(m*n) stack
Why This Solution? यह सॉल्यूशन क्यों?
  • DFS returns size directly.
  • No queue, recursive simplicity.
  • In-place marking efficient.

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

BFS queues to count each island — O(mn) space. DFS recursive returns area sum is optimal O(mn): flood fill size. Code follows. BFS क्यूज हर आइलैंड काउंट — O(mn) स्पेस। DFS रिकर्सिव एरिया सम रिटर्न ऑप्टिमल O(mn): फ्लड फिल साइज। कोड आगे।

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

"Max island area: Largest connected '1's (4-dir). Like islands count, but instead of ++count, compute size via DFS/BFS, track max. For DFS: On '1', maxArea = max(maxArea, dfs(i,j)); dfs: If invalid or '0' return 0; mark '0', return 1 + dfs(up) + dfs(down) + dfs(left) + dfs(right). O(mn) time (each cell once), O(mn) space stack. BFS alt: Queue, area=0, while queue dequeue mark area++ enqueue neighbors. Edges: No '1' 0, single 1. Modified flood fill—interviewers ask variations." "मैक्स आइलैंड एरिया: सबसे बड़ा कनेक्टेड '1's (4-डिर)। आइलैंड्स काउंट जैसा, लेकिन ++count की बजाय DFS/BFS से साइज कंप्यूट, मैक्स ट्रैक। DFS के लिए: '1' पर maxArea = max(maxArea, dfs(i,j)); dfs: इनवैलिड या '0' 0; '0' मार्क, 1 + dfs(up)+dfs(down)+dfs(left)+dfs(right)। O(mn) टाइम (हर सेल एक), O(mn) स्पेस स्टैक। BFS अल्ट: क्यू, area=0, जबकि क्यू deque मार्क area++ neighbors enqueue। एज: नो '1' 0, सिंगल 1। मॉडिफाइड फ्लड फिल—इंटरव्यूअर्स वेरिएशन्स पूछते।"

Rotting Oranges (LC 994) - LeetCode रोटिंग ऑरेंजेस (LC 994) - लीटकोड

Problem: Time to rot all oranges. समस्या: सब ऑरेंजेस रॉट टाइम।

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

  • Primary: Graph/Grid, BFS
  • Secondary: Multi-Source Shortest Path
  • Frequency: Medium (Grid BFS)

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

  • Big O: O(mn) time, O(mn) space.
  • Edge: No fresh -1, no rotten 0.
  • Self: BFS from all rotten, levels = time.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "4-dir rot? Modify grid? m,n up to 10?" Quick heuristic: "Is this grid rotting spread? Hints ordering (multi-source BFS), adjacency (yes), prefix (no), structure (queue with time levels)?" डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "4-डिर रॉट? ग्रिड मॉडिफाई? m,n 10 तक?" क्विक ह्यूरिस्टिक: "क्या यह ग्रिड रॉटिंग स्प्रेड? हिन्ट्स ऑर्डरिंग (मल्टी-सोर्स BFS), एडजेसेंसी (हां), प्रीफिक्स (नहीं), स्ट्रक्चर (टाइम लेवल्स के साथ क्यू)?"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"rotting spread", "minutes to rot all" 4-dir? All rot or -1? m,n=10? Grid Multi-Source BFS Breakdown: Minute sim → BFS levels from all 2's. Ask: Isolated fresh -1?
"grid", "oranges rotting" No fresh? All rotten? Graph Grid Shortest Path Think: Queue initial 2's time=0; enqueue neighbors time+1, track max and fresh count.

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

  • Simulation (Brute Force): Each minute, scan all rotten, rot adjacent fresh, copy grid avoid concurrent. While changes, time++. O(mn * t) time (t max minutes)—inefficient if t large.
  • Multi-Source BFS (Optimal): Initial queue all rotten with time=0, count fresh. BFS: Dequeue, maxTime=max(time), for neighbors if fresh: Mark rotten, fresh--, enqueue time+1. If fresh>0 -1 else maxTime. O(mn) time.

Non-Optimized Solution (Simulation) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (सिमुलेशन)

Javascript
// Brute Force (Minute Simulation): Scan and rot each minute
function orangesRotting(grid) {
  const m = grid.length, n = grid[0].length;
  let fresh = 0;
  for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) if (grid[i][j] === 1) fresh++;
  if (!fresh) return 0; // No fresh
  let time = 0;
  while (true) {
    let rotted = false;
    const temp = grid.map(row => row.slice()); // Copy
    for (let i = 0; i < m; i++) {
      for (let j = 0; j < n; j++) {
        if (temp[i][j] === 2) { // Rotten
          // Rot neighbors
          if (i>0 && temp[i-1][j]===1) { grid[i-1][j]=2; rotted=true; fresh--; }
          if (i<m-1 && temp[i+1][j]===1) { grid[i+1][j]=2; rotted=true; fresh--; }
          if (j>0 && temp[i][j-1]===1) { grid[i][j-1]=2; rotted=true; fresh--; }
          if (j<n-1 && temp[i][j+1]===1) { grid[i][j+1]=2; rotted=true; fresh--; }
        }
      }
    }
    if (!rotted) break; // No change
    time++;
  }
  return fresh > 0 ? -1 : time;
}
// Time: O(m*n * time), Space: O(m*n) copy
Why This Solution? यह सॉल्यूशन क्यों?
  • Simulates minute by minute explicitly.
  • Copy grid for safe neighbor checks.
  • O(mn * t) slow for deep grids.

Optimized Solution (Multi-Source BFS) ऑप्टिमाइज्ड सॉल्यूशन (मल्टी-सोर्स BFS)

Javascript
// Optimized (Multi-Source BFS): Start from all rotten, levels = time
function orangesRotting(grid) {
  const m = grid.length, n = grid[0].length;
  let queue = [], fresh = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 2) queue.push([i,j,0]); // Rotten with time 0
      if (grid[i][j] === 1) fresh++;
    }
  }
  if (!fresh) return 0;
  let maxTime = 0;
  while (queue.length) {
    const [i,j,time] = queue.shift();
    maxTime = Math.max(maxTime, time);
    // Rot neighbors
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    for (let [di,dj] of dirs) {
      const x = i + di, y = j + dj;
      if (x>=0 && x<m && y>=0 && y<n && grid[x][y]===1) {
        grid[x][y] = 2; // Rot
        fresh--;
        queue.push([x,y,time+1]); // Next level
      }
    }
  }
  return fresh > 0 ? -1 : maxTime;
}
// Time: O(m*n), Space: O(m*n) queue
Why This Solution? यह सॉल्यूशन क्यों?
  • BFS levels = minutes exactly.
  • Multi-source starts all rotten simultaneously.
  • Visits each cell once.

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

Minute-by-minute simulation scans grid repeatedly — O(mn t). Multi-source BFS from all rotten gives optimal O(mn): levels as time, track fresh. Code next. मिनट-बाय-मिनट सिमुलेशन ग्रिड रीपीट स्कैन — O(mn t)। सब रॉटन से मल्टी-सोर्स BFS ऑप्टिमल O(mn): लेवल्स टाइम, फ्रेश ट्रैक। कोड अगला।

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

"Rotting Oranges: Grid 0 empty, 1 fresh, 2 rotten; rotten rot adjacent fresh in 1 min, find min time all rot or -1. Naive: Loop minutes, scan rotten rot neighbors on copy—O(mn t). Optimal multi-source BFS: Queue initial all 2's with time=0, fresh count. While queue: Dequeue [i,j,time], maxTime=max(time); for 4 dirs if 1: Set 2, fresh--, enqueue [x,y,time+1]. End: Fresh>0 -1 else maxTime. O(mn) time (each cell enqueued once), O(mn) queue. Edges: No fresh 0, isolated fresh -1. BFS for shortest path in unweighted—interview grid classic." "रोटिंग ऑरेंजेस: ग्रिड 0 एंप्टी, 1 फ्रेश, 2 रॉटन; रॉटन 1 मिन में एडज फ्रेश रॉट, मिन टाइम सब रॉट या -1। नेव: मिनट्स लूप, रॉटन स्कैन neighbors रॉट कॉपी पर—O(mn t)। ऑप्टिमल मल्टी-सोर्स BFS: क्यू इनिशियल सब 2's टाइम=0, फ्रेश काउंट। जबकि क्यू: Dequeue [i,j,time], maxTime=max(time); 4 dirs अगर 1: 2 सेट, fresh--, [x,y,time+1] enqueue। एंड: fresh>0 -1 else maxTime। O(mn) टाइम (हर सेल enqueue एक), O(mn) क्यू। एज: नो फ्रेश 0, आइसोलेटेड -1। BFS अनवेटेड शॉर्टेस्ट पाथ—इंटरव्यू ग्रिड क्लासिक।"

Sorting & Searching (Days 15-16) सॉर्टिंग एंड सर्चिंग (दिन 15-16)

Sort: O(n log n). Search: Binary O(log n). सॉर्ट: O(n log n)। सर्च: बाइनरी O(log n)।

Sort an Array (LC 912) - LeetCode सॉर्ट एन ऐरे (LC 912) - लीटकोड

Problem: Sort array (impl quicksort). समस्या: ऐरे सॉर्ट (क्विकसॉर्ट इम्प्ल)।

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

  • Primary: Sorting, Divide and Conquer
  • Secondary: Quickselect Partition
  • Frequency: Medium (Implement sort algo)

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

  • Big O: O(n log n) avg, O(n^2) worst.
  • Edge: Empty, duplicates.
  • Self: Pivot, partition, recur.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Stable sort needed? Duplicates? n up to 10^5? In-place?" Quick heuristic: "Implement sort? Hints partition (quicksort), merge (mergesort), quadratic bad (bubble)." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "स्टेबल सॉर्ट? डुप्लिकेट्स? n 10^5? इन-प्लेस?" क्विक ह्यूरिस्टिक: "सॉर्ट इम्प्ल? हिन्ट्स पार्टिशन (क्विक), मर्ज (मर्जसॉर्ट), क्वाड्रेटिक बैड (बबल)।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"sort the array", "return sorted" Ascending? Stable? In-place preferred? Quicksort or Mergesort Breakdown: Bubble O(n^2) → n log n divide. Ask: Pivot choice?
"implement sorting" n range? Negatives? Duplicates ok? Partition and Recur Think: Worst case? Randomize pivot.

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

  • Bubble Sort: Nested loops, swap adjacent if out order, outer n-1 passes. O(n²) time, O(1) space—simple but quadratic.
  • Merge Sort: Divide to singles, merge sorted halves. O(n log n) time, O(n) space—stable, guaranteed.
  • Quicksort (Optimal Avg): Choose pivot (last), partition smaller left/larger right, recur sides. Avg O(n log n), worst O(n²) sorted (random pivot fixes), O(log n) space stack.

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

Javascript
// Non-Optimized (Bubble Sort): Adjacent swaps in nested loops
function sortArray(nums) {
  // Outer loop for passes (n-1 times max)
  for (let i = 0; i < nums.length; i++) {
    // Inner loop for comparisons up to unsorted portion
    for (let j = 0; j < nums.length - i - 1; j++) {
      // If adjacent elements out of order
      if (nums[j] > nums[j + 1]) {
        // Swap them to bubble larger up
        [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
      }
    }
  }
  // Array is now sorted in-place
  return nums;
// Time: O(n^2) - quadratic comparisons/swaps, Space: O(1) - in-place
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple adjacent swaps.
  • In-place, no extra space.
  • O(n²) inefficient for large n.

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

Javascript
// Optimized (Quicksort): Partition around pivot recursively
function sortArray(nums) {
  // Recursive helper function for quicksort
  function quick(left, right) {
    // Base case: single or no elements, already sorted
    if (left >= right) return;
    // Choose last element as pivot
    const pivot = nums[right];
    // Partition index starts at left
    let partition = left;
    // Scan left to right-1, partition smaller elements
    for (let i = left; i < right; i++) {
      // If current < pivot, swap to partition side
      if (nums[i] < pivot) {
        [nums[i], nums[partition]] = [nums[partition], nums[i]]; // Swap
        partition++; // Increment partition
      }
    }
    // Place pivot in correct position
    [nums[right], nums[partition]] = [nums[partition], nums[right]]; // Final swap
    // Recur on left subarray (smaller elements)
    quick(left, partition - 1);
    // Recur on right subarray (larger elements)
    quick(partition + 1, right);
  }
  // Start recursion on full array
  quick(0, nums.length - 1);
  return nums;
// Time: O(n log n) average, O(n^2) worst, Space: O(log n) recursion stack
Why This Solution? यह सॉल्यूशन क्यों?
  • Avg O(n log n), in-place partitions.
  • Recur divides problem.
  • Fast in practice.

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

Bubble O(n²) swaps adjacent. Quicksort O(n log n): Partition pivot, recur. Code here. बबल O(n²) एडजेसेंट स्वैप्स। क्विकसॉर्ट O(n log n): pivot पार्टिशन, recur। कोड।

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

"Sort array ascending. Bubble O(n²): Outer i=0 to n-2, inner j=0 to n-i-2, swap if nums[j]>nums[j+1]—correct but slow. Merge O(n log n): Divide mid, sort left/right, merge—stable but O(n) space. Quicksort avg O(n log n): quick(left,right): If left>=right return; Pivot=nums[right], partition=left; For i=left to right-1 if nums[i] "ऐरे सॉर्ट एसेंडिंग। बबल O(n²): आउटर i=0 n-2, इनर j=0 n-i-2, nums[j]>nums[j+1] स्वैप—सही लेकिन धीमा। मर्ज O(n log n): mid डिवाइड, left/right सॉर्ट, मर्ज—स्टेबल लेकिन O(n) स्पेस। क्विकसॉर्ट avg O(n log n): quick(left,right): left>=right रिटर्न; pivot=nums[right], partition=left; i=left right-1 अगर nums[i]

Search in Rotated Sorted Array (LC 33) - LeetCode सर्च इन रोटेटेड सॉर्टेड ऐरे (LC 33) - लीटकोड

Problem: Find target in rotated sorted. समस्या: रोटेटेड सॉर्टेड में टारगेट ढूंढें।

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

  • Primary: Binary Search, Rotated Array
  • Secondary: Sorted Half Identification
  • Frequency: High (Twist on binary)

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

  • Big O: O(log n) time.
  • Edge: No rotation, target not.
  • Self: Binary find sorted half.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "One rotation only? Duplicates? n up to 10^4? Unique elements?" Quick heuristic: "Rotated sorted search? Hints modified binary (check halves sorted), log time." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "वन रोटेशन? डुप्लिकेट्स? n 10^4? यूनिक?" क्विक ह्यूरिस्टिक: "रोटेटेड सॉर्टेड सर्च? हिन्ट्स मॉडिफाइड बाइनरी (हाफ्स सॉर्टेड चेक), लॉग टाइम।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"rotated sorted array", "find target" One rotation? Duplicates? Sorted ascending originally? Modified Binary Search Breakdown: Linear → Find pivot + binary → Single mod binary. Ask: Duplicates handle?
"return index or -1" n size? Negatives? No rotation case? Discard unsorted half Think: Identify sorted half, target in it?

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

  • Linear: Scan full array for target. O(n) time—ignores sorted, works but misses log n.
  • Find Pivot + Binary: Binary find rotation point O(log n), then binary on correct half O(log n). Total O(log n).
  • Modified Binary (Optimal): While left<=right: mid; If == return; If left-mid sorted (nums[left]<=nums[mid]): If target in [left,mid) right=mid-1 else left=mid+1; Else right sorted: If in (mid,right] left=mid+1 else right=mid-1. O(log n) time.

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

Javascript
// Non-Optimized (Linear Scan): Full array traversal ignoring rotation
function search(nums, target) {
  // Use built-in indexOf for simplicity (equivalent to manual loop)
  return nums.indexOf(target); // Returns first occurrence or -1
}
// Time: O(n) - full scan, Space: O(1) - no extra storage
Why This Solution? यह सॉल्यूशन क्यों?
  • Simple full scan.
  • No rotation handling.
  • O(n) misses efficiency.

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

Javascript
// Optimized (Modified Binary Search): Handle rotation by checking sorted halves
function search(nums, target) {
  // Initialize pointers for binary search
  let left = 0, right = nums.length - 1;
  // Continue while valid search space
  while (left <= right) {
    // Midpoint calculation
    const mid = Math.floor((left + right) / 2);
    // Direct match at mid
    if (nums[mid] === target) {
      return mid; // Found
    }
    // Check if left half is sorted (nums[left] <= nums[mid])
    if (nums[left] <= nums[mid]) {
      // Target in left sorted half?
      if (target >= nums[left] && target < nums[mid]) {
        right = mid - 1; // Search left
      } else {
        left = mid + 1; // Search right
      }
    } else { // Right half must be sorted
      // Target in right sorted half?
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1; // Search right
      } else {
        right = mid - 1; // Search left
      }
    }
  }
  // Not found after search
  return -1;
// Time: O(log n) - binary despite rotation, Space: O(1) - iterative
Why This Solution? यह सॉल्यूशन क्यों?
  • Adapts binary to rotation.
  • Discards unsorted half.
  • O(log n) always.

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

Linear O(n) scan. Mod binary O(log n): Check sorted half, discard other. Code. लीनियर O(n) स्कैन। मॉड बाइनरी O(log n): सॉर्टेड हाफ चेक, अन्य डिस्कार्ड। कोड।

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

"Search rotated sorted array (one rotation): Find target index or -1. Linear O(n): Just indexOf—works but slow. Better: Binary find pivot (min index) O(log n), then binary on unrotated half. Optimal single binary: left=0 right=n-1; while <=: mid; == return; If nums[left]<=nums[mid] (left sorted): Target in [left,mid)? right=mid-1 else left=mid+1; Else right sorted: Target in (mid,right]? left=mid+1 else right=mid-1. O(log n) time, O(1) space—always halves viable part. Edges: No rotation like normal binary, not found -1, duplicates? Assume unique. In JS, careful bounds. Interviewers probe sorted invariant." "रोटेटेड सॉर्टेड ऐरे सर्च (वन रोटेशन): टारगेट इंडेक्स या -1। लीनियर O(n): indexOf—वर्क्स लेकिन धीमा। बेहतर: बाइनरी pivot (मिन इंडेक्स) O(log n), फिर अनरोटेटेड हाफ पर बाइनरी। ऑप्टिमल सिंगल बाइनरी: left=0 right=n-1; जबकि <=: mid; == रिटर्न; nums[left]<=nums[mid] (लेफ्ट सॉर्टेड): टारगेट [left,mid)? right=mid-1 else left=mid+1; वरना राइट सॉर्टेड: (mid,right]? left=mid+1 else right=mid-1। O(log n) टाइम, O(1) स्पेस—हमेशा हाफ वायबल। एज: नो रोटेशन नॉर्मल, नॉट -1, डुप्स? यूनिक असम। जेएस में बाउंड्स केयर। इंटरव्यूअर्स सॉर्टेड इनवैरिएंट प्रोब।"

Kth Largest Element in an Array (LC 215) - LeetCode केथ लार्जेस्ट एलिमेंट इन एन ऐरे (LC 215) - लीटकोड

Problem: Find kth largest. समस्या: kth लार्जेस्ट ढूंढें।

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

  • Primary: Quickselect, Heap
  • Secondary: Sorting
  • Frequency: Medium (Selection algo)

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

  • Big O: O(n log n) sort, O(n) quickselect avg.
  • Edge: k=1 max.
  • Self: Quickselect partition.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "k from 1 to n? Duplicates? n up to 10^5? Return value not index?" Quick heuristic: "Kth order statistic? Hints partition (quickselect), heap (min k), sort easy." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "k 1 to n? डुप्लिकेट्स? n 10^5? वैल्यू नॉट इंडेक्स?" क्विक ह्यूरिस्टिक: "kth ऑर्डर? हिन्ट्स पार्टिशन (क्विकसिलेक्ट), हीप (मिन k), सॉर्ट आसान।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"kth largest", "array" 1-based k? Duplicates? Unsorted? Quickselect or Min-Heap Breakdown: Sort O(n log n) → Avg O(n) partition. Ask: Worst case?
"return the kth" n size? Negatives? k=1 max? Partition to isolate Think: Target index n-k after sort desc.

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

  • Heap (Min-Heap k): PriorityQueue min-heap size k, add all, top is kth largest. O(n log k) time, O(k) space—good small k.
  • Sort: Sort desc, return nums[k-1]. O(n log n) time, O(1) space in-place—simple, guaranteed.
  • Quickselect (Optimal Avg): Partition around pivot to right k elements, recur side with kth. Avg O(n), worst O(n²), O(1) space.

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

Javascript
// Non-Optimized (Full Sort): Sort descending and pick k-1 index
function findKthLargest(nums, k) {
  // Sort array in descending order
  nums.sort((a, b) => b - a); // Larger first
  // Return the element at position k-1 (0-based)
  return nums[k - 1];
// Time: O(n log n) - full sort, Space: O(1) - in-place sort
Why This Solution? यह सॉल्यूशन क्यों?
  • Sort descending easy access.
  • Handles dups fine.
  • O(n log n) not linear.

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

Javascript
// Optimized (Quickselect): Partition to isolate kth largest
function findKthLargest(nums, k) {
  // Recursive quickselect targeting index (n - k) for kth largest
  function quickselect(left, right, idx) {
    // Base: single element
    if (left === right) return nums[left];
    // Pivot as last element
    const pivot = nums[right];
    // Partition index
    let partition = left;
    // Partition: elements > pivot go left (for largest)
    for (let i = left; i < right; i++) {
      if (nums[i] > pivot) { // Greater than pivot (larger)
        [nums[i], nums[partition]] = [nums[partition], nums[i]]; // Swap
        partition++;
      }
    }
    // Place pivot
    [nums[right], nums[partition]] = [nums[partition], nums[right]];
    // If partition is target index
    if (partition === idx) return nums[partition];
    // Recur right if target larger index (smaller values? Wait, for largest idx = n-k large end)
    else if (partition < idx) return quickselect(partition + 1, right, idx);
    // Recur left
    else return quickselect(left, partition - 1, idx);
  }
  // Target index for kth largest: length - k (0-based, largest at end after partition)
  return quickselect(0, nums.length - 1, nums.length - k);
// Time: O(n) average, O(n^2) worst, Space: O(1) - in-place recursion
Why This Solution? यह सॉल्यूशन क्यों?
  • Avg O(n) by pruning partitions.
  • In-place, no extra space.
  • Similar to quicksort partition.

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

Sort O(n log n) desc, pick k-1. Quickselect O(n) avg: Partition to n-k. Code. सॉर्ट O(n log n) desc, k-1 पिक। क्विकसिलेक्ट O(n) avg: n-k पार्टिशन। कोड।

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

"Kth largest: ith biggest element (1-based). Sort desc O(n log n): nums.sort((a,b)=>b-a), return nums[k-1]—easy, but not linear. Min-heap size k: Add all, heap top kth—O(n log k). Optimal quickselect: Like quicksort, partition pivot so >pivot left, < right (for largest, >pivot smaller? Wait, for kth largest, partition so k-1 smaller right of partition. Recur: quick(left,right,idx=n-k); Pivot last, partition i< pivot swap leftward; If partition==idx return; left. Avg O(n) prunes half, worst O(n²). Edges: k=1 max, dups ok. In JS, in-place—interviewers like linear time selection." "kth लार्जेस्ट: ith सबसे बड़ा (1-बेस्ड)। सॉर्ट desc O(n log n): nums.sort((a,b)=>b-a), nums[k-1]—आसान, लेकिन नॉट लीनियर। मिन-हीप साइज k: सब ऐड, टॉप kth—O(n log k)। ऑप्टिमल क्विकसिलेक्ट: क्विकसॉर्ट जैसा, pivot partition >pivot left, < right (लार्जेस्ट के लिए >pivot smaller? kth largest के लिए partition k-1 smaller right। Recur: quick(left,right,idx=n-k); pivot last, partition i< pivot leftward स्वैप; partition==idx रिटर्न; left। avg O(n) हाफ प्रून, worst O(n²)। एज: k=1 max, डुप्स ok। जेएस में in-place—इंटरव्यूअर्स लीनियर टाइम सिलेक्शन लाइक।"

Dynamic Programming (Basics) (Days 17-18) डायनामिक प्रोग्रामिंग (बेसिक्स) (दिन 17-18)

DP: Memo/tab for subproblems. DP: सबप्रॉब्लम्स के लिए मेमो/टैब।

Climbing Stairs (LC 70) - LeetCode क्लाइंबिंग स्टेयर्स (LC 70) - लीटकोड

Problem: Ways to climb n stairs (1/2 steps). समस्या: n स्टेयर्स चढ़ने के तरीके (1/2 स्टेप्स)।

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

  • Primary: Fibonacci, 1D DP
  • Secondary: Recurrence Relations
  • Frequency: High (Intro to DP)

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

  • Big O: O(n) time, O(1) space.
  • Edge: 0=1, 1=1.
  • Self: Fib-like: dp[n] = dp[n-1] + dp[n-2].

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "n up to 45? Only 1/2 steps? Count ways or paths?" Quick heuristic: "Counting paths with choices? Hints fib recurrence (last step 1 or 2), overlaps (yes)." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "n 45 तक? सिर्फ 1/2 स्टेप्स? वेज़ काउंट या पाथ्स?" क्विक ह्यूरिस्टिक: "चॉइसेज के साथ पाथ्स काउंट? हिन्ट्स फिब रेकरेंस (लास्ट 1 या 2), ओवरलैप्स (हां)।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"number of ways", "1 or 2 steps" n max? Distinct ways? Modulo? Fibonacci DP Breakdown: Recur O(2^n) → Memo O(n) → Tab O(1) space. Ask: n=0?
"climb n stairs" Order matters? Cycles no? 1D Recurrence Think: Subproblems overlap? Optimal from smaller.

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

  • Brute Force Recursion: Define a recursive function climb(n): If n <= 1, return 1 (base case: 0 or 1 step has 1 way); otherwise, return climb(n-1) (take 1 step last) + climb(n-2) (take 2 steps last). This builds a binary tree of decisions, but with massive overlaps—like climb(3) computed multiple times—leading to O(2^n) time complexity due to exponential branching, and O(n) recursion stack space. It's intuitive for the problem's choice nature but explodes for n > 40.
  • Memoization (Top-Down DP): Use a memo array or Map to cache results: Before recursing, check if climb(n) is already computed; if yes, return it; else compute climb(n-1) + climb(n-2) and store. This ensures each subproblem (each value from 0 to n) is solved only once, reducing time to O(n) while keeping the recursive structure, with O(n) space for memo + O(n) stack. Great for understanding DP as 'remembering' results to avoid redo.
  • Tabulation Bottom-Up (Optimal Space-Optimized): Build iteratively from base cases: Initialize two variables a=1 (ways for 1 step), b=1 (for 2); for i=3 to n, compute next = a + b, then shift a=b, b=next. Return b at end. This is O(n) time (linear loop), O(1) space (just two vars), and avoids recursion entirely. It fills the DP table 'bottom-up' from small to large subproblems, leveraging the fact that we only need the last two values for Fibonacci-like recurrence.

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

Javascript
// Non-Optimized (Plain Recursion): Exponential branching without memo
function climbStairs(n) {
  // Base cases: 0 or 1 stair has 1 way
  if (n <= 1) return 1;
  // Recur: ways to n = ways to n-1 (last 1 step) + n-2 (last 2 steps)
  return climbStairs(n - 1) + climbStairs(n - 2);
// Time: O(2^n) - binary tree of calls with overlaps, Space: O(n) - recursion stack
Why This Solution? यह सॉल्यूशन क्यों?
  • It directly models the problem's decision tree—choosing 1 or 2 steps at each level—which makes it super intuitive for explaining the recurrence relation to yourself or interviewers.
  • Handles base cases cleanly (n=0 or 1 has exactly one way: do nothing or take the single step), and no extra data structures needed beyond the call stack.
  • While correct, its exponential time highlights the core DP issue: redundant computation of the same subproblems (e.g., ways to climb 3 steps calculated repeatedly), making it a perfect 'before DP' baseline to contrast with optimized versions.

Optimized Solution (Iterative Fibonacci) ऑप्टिमाइज्ड सॉल्यूशन (इटरेटिव फिबोनाची)

Javascript
// Optimized (Iterative Fibonacci): O(1) space bottom-up
function climbStairs(n) {
  // Base cases
  if (n <= 1) return 1;
  // Initialize for n=1 and n=2 (both 1 way, but shift for loop)
  let a = 1, b = 1; // a: ways to n-2, b: ways to n-1
  // Loop from 3 to n, compute Fibonacci-like
  for (let i = 2; i <= n; i++) { // i starts at 2 for n=2 already set
    // Next ways = sum of previous two
    [a, b] = [b, a + b]; // Shift: new a = old b, new b = old a + old b
  }
  return b; // Ways to n
// Time: O(n) - linear loop, Space: O(1) - two variables
Why This Solution? यह सॉल्यूशन क्यों?
  • Achieves linear O(n) time by computing each Fibonacci-like step exactly once in a simple loop, eliminating the branching explosion of recursion while still deriving from the same recurrence.
  • Reduces space to O(1) by using just two variables to 'roll' the previous results forward, which is crucial for large n where full arrays would waste memory—shows space optimization in DP.
  • Iterative nature avoids recursion depth limits (e.g., JS stack overflow at ~10k calls), making it robust and faster in practice, and it's the natural evolution from memoization without the overhead.

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

Recur O(2^n) branches. Tab O(n)/O(1): Roll two vars fib. Code. रिकर O(2^n) ब्रांचेस। टैब O(n)/O(1): टू वर्स रोल फिब। कोड।

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

"Okay, so Climbing Stairs is about counting the number of distinct ways to climb n stairs taking 1 or 2 steps at a time—it's essentially the Fibonacci sequence in disguise. First, the brute force: I'd write a recursive function like climb(n): if n is 0 or 1, return 1 because there's only one way—either do nothing or take that single step. Otherwise, return climb(n-1) for ending with a 1-step plus climb(n-2) for ending with a 2-step. This perfectly captures the choices, but it's exponential time, O(2^n), because it builds this huge binary tree of decisions, and subproblems like 'ways to do 3 steps' get recomputed over and over—think about it, climb(5) calls climb(3) twice independently. Space is O(n) from the recursion stack, and it'll timeout for n around 40. Now, spotting the DP pattern: This has overlapping subproblems—every climb(k) for k "ठीक है, क्लाइंबिंग स्टेयर्स n स्टेयर्स 1 या 2 स्टेप्स से चढ़ने के अलग तरीकों के बारे में—यह फिबोनाची सीक्वेंस का डिस्गाइज है। सबसे पहले, ब्रूट फोर्स: मैं रिकर्सिव फंक्शन लिखूंगा climb(n): अगर n 0 या 1, 1 रिटर्न क्योंकि सिर्फ एक तरीका—नथिंग या सिंगल स्टेप। वरना, climb(n-1) (1-स्टेप एंड) + climb(n-2) (2-स्टेप) रिटर्न। यह चॉइसेज कैप्चर करता, लेकिन O(2^n) टाइम एक्सपोनेंशियल, क्योंकि डिसीजन का बड़ा बाइनरी ट्री बनता, और सबप्रॉब्लम्स जैसे '3 स्टेप्स' मल्टीपल री컴्प्यूट—climb(5) climb(3) ट्वाइस। स्पेस O(n) स्टैक से, n~40 पर टाइमआउट। अब DP पैटर्न स्पॉट: ओवरलैपिंग सबप्रॉब्लम्स—हर climb(k) k

Fibonacci Number (LC 509) - LeetCode फिबोनाची नंबर (LC 509) - लीटकोड

Problem: Nth fib. समस्या: nth फिब।

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

  • Primary: Fibonacci, 1D DP
  • फिबोनाची, 1D DP
  • Secondary: Recurrence
  • Frequency: High (DP basics)

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

  • Similar to stairs.
  • Self: Same as above.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "F(0)=0? n up to 30? Modulo?" Quick heuristic: "Fib sequence? Hints recur F(n-1)+F(n-2), overlaps yes." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "F(0)=0? n 30? मॉडुलो?" क्विक ह्यूरिस्टिक: "फिब सीक्वेंस? हिन्ट्स F(n-1)+F(n-2), ओवरलैप्स हां।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"Fibonacci number", "nth" F(0), F(1)? n max? Large n? Fib DP Breakdown: Recur → Tab O(1). Ask: Base cases?
"F(n) = F(n-1) + F(n-2)" Modulo? Exact? Linear Recurrence Think: Overlaps, optimal sub.

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

  • Brute Force Recursion: fib(n): If n <= 1 return n (F(0)=0, F(1)=1); else fib(n-1) + fib(n-2)—creates exponential call tree with heavy overlaps (e.g., fib(4) computes fib(2) twice), O(2^n) time, O(n) stack space—matches definition but scales poorly beyond n=40.
  • Memoization (Top-Down DP): Use a memo Map or array: fib(n): If memo[n] exists return it; else memo[n] = fib(n-1) + fib(n-2), return that. Solves each fib(k) once, O(n) time, O(n) space for memo + O(n) stack—introduces caching to cut redundancy while keeping recursive feel.
  • Tabulation Bottom-Up (Optimal Space-Optimized): Iterative loop: a=0 (F(0)), b=1 (F(1)); for i=2 to n: temp = a + b, a = b, b = temp; return b. O(n) time (one pass), O(1) space (two vars only)—builds from base up, no recursion, perfect for large n without stack overflow.

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

Javascript
// Non-Optimized (Plain Recursion): Exponential without caching
function fib(n) {
  // Base cases: F(0)=0, F(1)=1
  if (n <= 1) return n;
  // Recur: F(n) = F(n-1) + F(n-2)
  return fib(n - 1) + fib(n - 2);
// Time: O(2^n) - exponential call tree, Space: O(n) - stack
Why This Solution? यह सॉल्यूशन क्यों?
  • Perfectly mirrors the mathematical definition of Fibonacci—each call directly translates to the recurrence—making it the most straightforward way to understand and implement the core idea without any extras.
  • Handles the base cases (n=0 returns 0, n=1 returns 1) elegantly in one if, and requires zero additional data structures, keeping the code minimal and focused on the problem's essence.
  • Despite its simplicity, it exposes the classic DP flaw vividly: the exponential growth from not reusing computed values (like fib(2) called exponentially many times), serving as an ideal starting point to motivate why we need memoization or tabulation.

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

Javascript
// Optimized (Iterative): Bottom-up with constant space
function fib(n) {
  // Base cases
  if (n <= 1) return n;
  // Initialize F(0)=0, F(1)=1
  let a = 0, b = 1;
  // Loop from 2 to n
  for (let i = 2; i <= n; i++) {
    // Next fib = sum previous
    [a, b] = [b, a + b]; // Roll forward
  }
  return b; // F(n)
// Time: O(n) - single loop, Space: O(1) - two vars
Why This Solution? यह सॉल्यूशन क्यों?
  • Transforms the recursive explosion into a clean linear loop that computes each Fibonacci number exactly once, achieving O(n) time while being faster and more memory-efficient than recursion for large n.
  • Optimizes space to O(1) by only tracking the two most recent values needed for the next computation, eliminating the need for an array or map—crucial for understanding how DP can evolve from O(n) to constant space in linear recurrences.
  • Being fully iterative, it sidesteps recursion stack limits (e.g., in JS around 10k depth) and is easier to debug/step through, making it production-ready and a strong demonstration of bottom-up DP's practicality over top-down for simple chains like Fibonacci.

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

Recur O(2^n). Iterative O(n)/O(1): Roll a=0 b=1. Code. रिकर O(2^n)। इटरेटिव O(n)/O(1): a=0 b=1 रोल। कोड।

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

"Fibonacci Number: Compute the nth Fibonacci where F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) for n>1—super foundational for DP. Brute force recursion: fib(n): if n<=1 return n; else return fib(n-1) + fib(n-2). This is dead simple and matches the math exactly, but it's a disaster for time—O(2^n) because the call tree branches exponentially, and you recompute the same values a ton, like fib(2) gets called way too many times in fib(5). Space is O(n) from the stack, fine for small n but crashes on large. The DP magic: Overlapping subproblems (every fib(k) reused) and optimal substructure (built from smaller ones). Memoization fixes it top-down: Use an array dp[n+1] init -1; fib(n): if dp[n] != -1 return it; dp[n] = fib(n-1) + fib(n-2); return dp[n]. Now O(n) time since each fib(0 to n) computed once, O(n) space. But for ultimate optimization, bottom-up tabulation: Set a=0 (F(0)), b=1 (F(1)); for i=2 to n: int temp = a + b; a = b; b = temp; return b. O(n) time, O(1) space—no array, just rolling vars, and no recursion depth worries. Edges: n=0 returns 0, n=1 1, n=2 1. This is often the first DP question because it's so clean—interviewers use it to check if you spot the recurrence and can optimize step-by-step from brute to space-efficient." "फिबोनाची नंबर: nth फिब कंप्यूट F(0)=0, F(1)=1, n>1 F(n)=F(n-1)+F(n-2)—DP के लिए फाउंडेशनल। ब्रूट रिकर्सन: fib(n): n<=1 n; else fib(n-1)+fib(n-2)। सिंपल मैथ मैच, लेकिन टाइम डिजास्टर—O(2^n) ब्रांचिंग, fib(2) fib(5) में many। स्पेस O(n) स्टैक, स्मॉल fाइन लेकिन लार्ज क्रैश। DP मैजिक: ओवरलैपिंग (हर fib(k) रीयूज), ऑप्टिमल (स्मॉलर से बिल्ट)। मेमो टॉप-डाउन फिक्स: dp[n+1] -1; fib(n): dp[n]!=-1 रिटर्न; dp[n]=fib(n-1)+fib(n-2); O(n) टाइम हर एक, O(n) स्पेस। अल्टिमेट बॉटम-अप: a=0 F(0), b=1 F(1); i=2 n: temp=a+b; a=b; b=temp; b रिटर्न। O(n) टाइम, O(1) स्पेस—रोलिंग, नो रिकर्सन। एज: 0 0, 1 1, 2 1। फर्स्ट DP क्वेश्चन क्योंकि क्लीन—इंटरव्यूअर्स रेकरेंस स्पॉट चेक स्टेप-बाय-स्टेप ऑप्टिमाइज।"

House Robber (LC 198) - LeetCode हाउस रॉबर (LC 198) - लीटकोड

Problem: Max rob non-adjacent. समस्या: मैक्स रॉब नॉन-एडजेसेंट।

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

  • Primary: 1D DP, House Robber
  • Secondary: Choices with Constraints
  • Frequency: High (DP classic)

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

  • Big O: O(n) time, O(1) space.
  • Edge: Empty 0.
  • Self: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Linear houses? Values positive? n up to 100? Max sum?" Quick heuristic: "Max with no adjacent? Hints rob/skip recur, DP max[i] = max(max[i-1], max[i-2] + val)." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "लीनियर हाउसेस? वैल्यूज पॉजिटिव? n 100? मैक्स सम?" क्विक ह्यूरिस्टिक: "नो एडजेसेंट मैक्स? हिन्ट्स rob/skip recur, DP max[i]=max(max[i-1], max[i-2]+val)।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"max amount", "non-adjacent houses" Positive values? Circular? n max? 1D DP Choices Breakdown: Recur 2^n → Tab O(n)/O(1). Ask: Empty?
"rob houses in line" Start/end? Duplicates no? Local Max Recur Think: Overlaps in subarrays? Optimal from prev two.

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

  • Brute Force Recursion: Define helper(i): If i >= len(nums), return 0 (no more houses); else return max( nums[i] + helper(i+2) (rob this, skip next), helper(i+1) (skip this) )—this branches at every house with rob/skip choices, leading to O(2^n) time from the binary decision tree, and O(n) stack space; it's faithful to the problem but recomputes subarrays endlessly, like the max from house 3 onward calculated multiple paths.
  • Memoization (Top-Down DP): Use a memo array where memo[i] stores the max from house i onward: Before recursing, if memo[i] exists return it; else memo[i] = max(nums[i] + memo[i+2], memo[i+1]); fill on demand. This solves each starting position i only once, O(n) time, O(n) space for memo + O(n) stack—cuts the tree to a DAG by caching, making it linear but still recursive.
  • Tabulation Space-Optimized (Optimal): Bottom-up: Initialize prev2=0 (before first), prev1=0 (first house skip); for each house num: temp = max(prev1 (skip), prev2 + num (rob)); then prev2 = prev1, prev1 = temp. Return prev1. O(n) time (one pass over houses), O(1) space (just two prev vars)—iterative, no stack, and only needs the last two decisions since recurrence looks back 1-2 steps.

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

Javascript
// Non-Optimized (Plain Recursion): Branch on rob/skip per house
function rob(nums) {
  // Helper from index i
  function helper(i) {
    // Base: beyond last house, 0
    if (i >= nums.length) return 0;
    // Max: rob this (skip next) or skip this
    return Math.max(nums[i] + helper(i + 2), helper(i + 1));
  }
  return helper(0); // Start from first
// Time: O(2^n) - binary choices per house, Space: O(n) - stack
Why This Solution? यह सॉल्यूशन क्यों?
  • It elegantly captures the core dilemma at each house—rob now and skip next, or skip to potentially rob later—making the branching recursion feel natural and easy to trace for small arrays during debugging or explanation.
  • The base case (i >= length returns 0) cleanly handles the end of the array without extra checks, and it inherently enforces the non-adjacent rule by jumping i+2 when robbing, keeping the logic tight and problem-specific.
  • Though exponential, it starkly illustrates the DP need: The same subproblem 'max from house k' arises in many paths (e.g., via different skip sequences), computed redundantly—perfect for transitioning to memo/tab in interviews.

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

Javascript
// Optimized (Space-Optimized DP): O(1) space iterative
function rob(nums) {
  // Handle empty
  if (!nums.length) return 0;
  // prev2: max before prev1, prev1: max up to previous house
  let prev2 = 0, prev1 = 0;
  // Iterate through houses
  for (let num of nums) {
    // Max: skip current (prev1) or rob current + skip prev (prev2 + num)
    const temp = Math.max(prev1, prev2 + num);
    // Shift: prev2 becomes old prev1
    prev2 = prev1;
    // prev1 becomes new max
    prev1 = temp;
  }
  return prev1; // Final max
// Time: O(n) - linear pass, Space: O(1) - two vars
Why This Solution? यह सॉल्यूशन क्यों?
  • Processes houses in a single linear pass, computing the max at each step using only the previous two decisions, ensuring O(n) time without any redundant calculations—ideal for scaling to large inputs.
  • Achieves O(1) space by reusing just two variables (prev1 for skip, prev2 + current for rob), which is a key DP optimization for 1D recurrences, freeing up memory while maintaining the same accuracy as full tables.
  • Being purely iterative, it eliminates recursion stack risks (e.g., overflow in deep calls) and is easier to optimize further or debug step-by-step, making it robust for real-world use and a strong showcase of space-efficient DP.

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

Recur 2^n rob/skip. Tab O(n)/O(1): Prev two max. Code. रिकर 2^n rob/skip। टैब O(n)/O(1): प्रेव टू मैक्स। कोड।

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

"House Robber: Given houses in a line with values nums, find max money you can rob without robbing adjacent ones—classic DP choice problem. Brute force: Recursive helper(i) starting from house i: If i >= nums.length, return 0 (nothing left); else return max( nums[i] + helper(i+2) (rob this, skip next), helper(i+1) (skip this house) ). This models the exact decisions—rob or skip at each—but it's O(2^n) time because every house branches into two paths, and subproblems like 'max from house 3' get solved exponentially many times through different routes, with O(n) stack space. To DP-ify: Optimal substructure—max to i depends on max to i-1 (skip) or i-2 + nums[i] (rob)—and overlaps everywhere. Memo top-down: Memo array, helper(i): if memo[i] return; memo[i] = max(nums[i]+helper(i+2), helper(i+1)). O(n) time, O(n) space. But bottom-up space-optimized: prev2 = 0 (before start), prev1 = 0 (skip first); for each num in nums: temp = max(prev1, prev2 + num); prev2 = prev1; prev1 = temp; return prev1. O(n) time, O(1) space—linear scan, vars roll forward the two needed prevs. Edges: Empty array 0, single house nums[0]. This builds DP intuition: Choices with constraints lead to local max recurrences—interviewers often extend to circular houses." "हाउस रॉबर: लाइन में हाउसेस वैल्यूज nums, एडजेसेंट बिना मैक्स मनी रॉब—क्लासिक DP चॉइस। ब्रूट: recur helper(i) i से: i>=length 0; max(nums[i]+helper(i+2) rob skip next, helper(i+1) skip)। डिसीज मॉडल—rob/skip हर पर—लेकिन O(2^n) ब्रांच हर हाउस, 'मैक्स from 3' many रूट्स से, O(n) स्टैक। DP-ify: ऑप्टिमल—i तक मैक्स i-1 skip या i-2 + nums[i] rob—ओवरलैप्स एवरीव्हेर। मेमो टॉप-डाउन: मेमो, helper(i): memo[i] रिटर्न; memo[i]=max(nums[i]+helper(i+2), helper(i+1))। O(n) टाइम, O(n) स्पेस। बॉटम-अप स्पेस-ऑप्ट: prev2=0, prev1=0; num in nums: temp=max(prev1, prev2+num); prev2=prev1; prev1=temp; prev1 रिटर्न। O(n) टाइम, O(1) स्पेस—लीनियर, वर्स रोल। एज: एंप्टी 0, सिंगल nums[0]। DP इंट्यूशन बिल्ड: कंस्ट्रेंट्स चॉइसेज लोकल मैक्स रेकरेंस—इंटरव्यूअर्स सर्कुलर हाउसेस एक्सटेंड।"

Min Cost Climbing Stairs (LC 746) - LeetCode मिन कॉस्ट क्लाइंबिंग स्टेयर्स (LC 746) - लीटकोड

Problem: Min cost to top, 1/2 steps. समस्या: टॉप मिन कॉस्ट, 1/2 स्टेप्स।

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

  • Primary: 1D DP, Min Cost Path
  • Secondary: Similar to House Robber
  • Frequency: Medium (DP min)

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

  • Big O: O(n) time, O(1) space.
  • Self: dp[i] = cost[i] + min(dp[i-1], dp[i-2])

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Cost on land? Start free? n up to 1000? Positive costs?" Quick heuristic: "Min cost with 1/2 steps? Hints like robber but min, recur cost[i] + min(i+1,i+2)." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "लैंड पर कॉस्ट? स्टार्ट फ्री? n 1000? पॉजिटिव?" क्विक ह्यूरिस्टिक: "1/2 स्टेप्स मिन कॉस्ट? robber जैसा लेकिन मिन, recur cost[i]+min(i+1,i+2)।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"min cost", "1 or 2 steps" Cost on step? Start 0/1 free? n max? 1D Min DP Breakdown: Recur 2^n → Tab O(1). Ask: Base end 0?
"climbing stairs cost" Positive? Empty? Local Min Recur Think: Sub min from prev two.

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

  • Brute Force Recursion: Helper(i): If i >= cost.length, return 0 (at top, no more cost); else return cost[i] + min(helper(i+1), helper(i+2)) (pay for this step, then min from landing 1 or 2 ahead)—exponential O(2^n) from branching min choices, O(n) stack; intuitive for paths but recomputes min costs to same step many times via different routes.
  • Memoization (Top-Down DP): Memo[i] = min cost from step i: If memo[i] exists return; else memo[i] = cost[i] + min(memo[i+1], memo[i+2]); fill recursively. O(n) time (each i once), O(n) space memo+stack—caches the min path from each starting step, reducing tree to linear.
  • Tabulation Space-Optimized (Optimal): prev2=0 (cost beyond end), prev1=0; for i=0 to length-1: temp = cost[i] + min(prev1, prev2); prev2=prev1, prev1=temp. But since start at 0 or 1 free, return min(helper(0), helper(1)) or adjust loop to compute up to end and min last two. O(n) time, O(1) space—iterative accumulation of min costs, rolling just prev two.

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

Javascript
// Non-Optimized (Plain Recursion): Branch on 1/2 step costs
function minCostClimbingStairs(cost) {
  // Helper from step i
  function helper(i) {
    // Base: at or beyond top, 0 cost
    if (i >= cost.length) return 0;
    // Min cost: pay for i, then min of 1 or 2 steps ahead
    return cost[i] + Math.min(helper(i + 1), helper(i + 2));
  }
  // Start free from 0 or 1
  return Math.min(helper(0), helper(1));
// Time: O(2^n) - branching per step, Space: O(n) - stack
Why This Solution? यह सॉल्यूशन क्यों?
  • It naturally encodes the problem's mechanics—pay cost[i] then choose to jump 1 or 2 steps ahead—making the recursion tree a direct representation of possible paths, easy to visualize and debug for small cases.
  • The base case (i >= length returns 0) handles reaching the top cleanly, and starting with min(helper(0), helper(1)) accounts for free start steps, keeping the logic precise without array extras.
  • Its exponential runtime underscores the DP opportunity: Min cost from step k is recomputed across multiple paths (e.g., via different jump sequences), setting up a clear 'before/after' for optimization discussions.

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

Javascript
// Optimized (Iterative DP): O(1) space bottom-up
function minCostClimbingStairs(cost) {
  // prev2: min to i-2, prev1: min to i-1
  let prev2 = 0, prev1 = 0;
  // Build from i=2 to length (but adjust for start)
  for (let i = 2; i <= cost.length; i++) {
    // Min to i-1 (current in loop): cost[i-1] + min(prev1 to i-2? Wait, standard shift
    const temp = Math.min(prev1, prev2) + cost[i - 1]; // For landing on i-1
    prev2 = prev1; // Shift
    prev1 = temp;
  }
  // Min from start 0 or 1 (which are free, so min of computed to end from them)
  return Math.min(prev1, prev2);
// Time: O(n) - linear, Space: O(1) - two vars
Why This Solution? यह सॉल्यूशन क्यों?
  • Delivers O(n) time through a straightforward loop that accumulates the min cost at each step using only the immediate previous decisions, ensuring no wasted computations on revisited subpaths.
  • Caps space at O(1) by iteratively updating two variables for the last two min costs, which is essential for memory-tight scenarios and demonstrates how 1D DP recurrences can be compressed without losing accuracy.
  • As an iterative approach, it bypasses recursion's stack limitations and potential overflows, while being simple to extend (e.g., for k-steps) or trace, making it highly practical and a go-to for linear cost minimization problems.

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

Recur 2^n min paths. Tab O(n)/O(1): Roll min prev. Code. रिकर 2^n मिन पाथ्स। टैब O(n)/O(1): मिन प्रेव रोल। कोड।

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

"Min Cost Climbing Stairs: Cost array where cost[i] is paid for landing on step i; you can take 1 or 2 steps from current, start free from 0 or 1, min total cost to reach top. Brute: Recur helper(i): if i >= cost.length return 0 (top reached); else cost[i] + min(helper(i+1), helper(i+2))—pay for i, then min path from 1 or 2 ahead; final answer min(helper(0), helper(1)). This traces all possible jump paths perfectly, but O(2^n) time from branching mins, recomputing 'min from step 3' via various routes, O(n) stack. DP key: Min cost to i = cost[i] + min(cost to i-1, cost to i-2), with cost to end=0. Memo: Array memo, helper(i): if memo[i] return; memo[i]=cost[i]+min(helper(i+1),helper(i+2)). O(n) time/space. Space-opt tab: prev2=0 (end), prev1=0; but adjust for start: Actually, loop over cost: for i=0 to len-1: temp = cost[i] + min(prev1, prev2); prev2=prev1, prev1=temp; then min over last two? Wait, better: Compute up to len, with dp[len]=0, but since free start, run loop to len, init prev2=0, prev1=cost[0] or something—no, standard: prev2=0, prev1=0; for i=2 to len: Wait, for this, since pay on land, and start min from 0/1: Loop from 0: But to match, init prev2=0 (skip 0), prev1=cost[0] (land 0), but simpler code as given. O(n)/O(1). Edges: Assume len>=2, empty 0. Like robber but min cost—interviewers link to ways (max vs min)." "मिन कॉस्ट क्लाइंबिंग स्टेयर्स: cost[i] i पर लैंड पे; करेंट से 1/2 स्टेप्स, 0/1 फ्री स्टार्ट, टॉप मिन टोटल। ब्रूट: recur helper(i): i>=length 0; cost[i] + min(helper(i+1),helper(i+2))—i पे, 1/2 ahead मिन; min(helper(0),1)। पाथ्स ट्रेस, O(2^n) मिन ब्रांच, 'मिन from 3' many, O(n) स्टैक। DP: i तक मिन = cost[i] + min(i-1, i-2), एंड=0। मेमो: मेमो, helper(i): memo[i]=cost[i]+min(helper(i+1),i+2)। O(n) टाइम/स्पेस। स्पेस-ऑप्ट टैब: prev2=0, prev1=0; i=0 len-1: temp=cost[i]+min(prev1,prev2); शिफ्ट। स्टार्ट min(0,1) फ्री, लूप len, dp[len]=0, फाइनल मिन लास्ट टू। O(n)/O(1)। एज: len>=2, एंप्टी 0। robber जैसा लेकिन मिन कॉस्ट—इंटरव्यूअर्स वेज (max vs min) लिंक।"

DP (Advanced) & Greedy (Days 19-20) DP (एडवांस्ड) एंड ग्रीडी (दिन 19-20)

Advanced: More states. एडवांस्ड: मोर स्टेट्स।

Coin Change (LC 322) - LeetCode कॉइन चेंज (LC 322) - लीटकोड

Problem: Min coins for amount. समस्या: अमाउंट के लिए मिन कॉइन्स।

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

  • Primary: Unbounded Knapsack, 1D DP
  • Secondary: Coin Change
  • Frequency: High (Knapsack intro)

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

  • Big O: O(amount * coins) time, O(amount) space.
  • Edge: 0=0, impossible -1.
  • Self: dp[amt] = min(dp[amt-coin] +1)

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Unlimited coins? Order matter? amount up to 10^4? -1 impossible?" Quick heuristic: "Min coins unbounded? Hints knapsack dp[amt] = min over coin dp[amt-coin]+1." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "अनलिमिटेड? ऑर्डर? amount 10^4? -1?" क्विक ह्यूरिस्टिक: "मिन coins अनबाउंडेड? हिन्ट्स नैपसैक dp[amt]=min coin dp[amt-coin]+1।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"min number of coins", "unlimited each" Exact amount? Positive coins? amount max? Unbounded Knapsack DP Breakdown: Recur coins^amt → Tab O(amount*coins). Ask: Impossible -1?
"make amount" Duplicates coins? 0 amount? Subproblem Min Think: Overlaps in sub-amts? Build small to large.

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

  • Brute Force Recursion: Helper(amt): If amt==0 return 0; if <0 return inf; else min over each coin: 1 + helper(amt - coin)—branches per coin choice, exponential O(coins^amount) as it tries all combinations without caching, like for amount=5 with coins=[1,2], it explores every sequence; O(amount) stack worst—complete but TLE.
  • Memoization (Top-Down DP): Memo[amt] = min(1 + memo[amt-coin] for coin if amt-coin>=0), inf if no way; check memo first. Each state (amt) computed once per call, but since coins loop inside, O(amount * coins) time, O(amount) memo + O(amount) stack—stores min coins for each sub-amount, pruning impossible paths.
  • Tabulation Bottom-Up (Optimal, Space-Optimizable): dp[0]=0, dp[1 to amount]=inf; for i=1 to amount: for each coin if i>=coin: dp[i] = min(dp[i], dp[i-coin] + 1). Return dp[amount] or -1 if inf. O(amount * coins) time (double loop), O(amount) space—unbounded knapsack where 'items' are coins unlimited, 'capacity' amount; can optimize space by reversing coin loop for in-place.

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

Javascript
// Non-Optimized (Plain Recursion): Branch on each coin subtraction
function coinChange(coins, amount) {
  // Helper for remaining amount
  function helper(amt) {
    // Base: exact 0 coins
    if (amt === 0) return 0;
    // Invalid: negative, impossible
    if (amt < 0) return Infinity;
    // Min coins: try each coin
    let min = Infinity;
    for (let coin of coins) {
      // Recur with this coin used once
      min = Math.min(min, 1 + helper(amt - coin));
    }
    return min;
  }
  // Result or -1 if impossible
  const res = helper(amount);
  return res === Infinity ? -1 : res;
// Time: O(coins^amount) - branching tree, Space: O(amount) - stack
Why This Solution? यह सॉल्यूशन क्यों?
  • It faithfully explores every possible coin combination by branching on each coin type at every remaining amount, making it easy to see the full search space and verify for tiny amounts like 3 with [1,2].
  • The base cases (amt=0 returns 0 coins, <0 inf to prune invalid) naturally handle feasibility, and returning -1 for inf keeps it simple without extra flags.
  • Its brute explosion (O(coins^amount)) perfectly motivates DP: The same sub-amount (e.g., making 4) gets tried via different coin orders, recomputed wildly—ideal for introducing memo to cache those mins.

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

Javascript
// Optimized (Bottom-Up DP Tabulation): Fill table for sub-amounts
function coinChange(coins, amount) {
  // dp[i]: min coins for amount i
  const dp = new Array(amount + 1).fill(Infinity);
  // Base: 0 amount needs 0 coins
  dp[0] = 0;
  // For each sub-amount from 1 to target
  for (let i = 1; i <= amount; i++) {
    // Try each coin for this i
    for (let coin of coins) {
      // If coin fits
      if (i - coin >= 0) {
        // Update min using subproblem
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  // Impossible if still inf
  return dp[amount] === Infinity ? -1 : dp[amount];
// Time: O(amount * coins.length) - double loop, Space: O(amount) - dp array
Why This Solution? यह सॉल्यूशन क्यों?
  • Systematically builds the min coins for every amount from 0 up using a double loop (amounts outer, coins inner), ensuring each dp[i] is the true minimum after considering all ways, in O(amount * coins) time without backtracking.
  • The inf initialization and min updates naturally propagate impossibility (stays inf if no coin fits), making it robust for cases with limited denominations, while O(amount) space is straightforward and optimizable to O(1) if needed by tracking only the last row.
  • As a classic unbounded knapsack, it teaches filling the DP table in the right order (smaller amounts first, then coins), avoiding the recursion's order issues, and scales well for amount up to 10^4—key for knapsack variants in interviews.

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

Recur coins^amt. Tab O(amount*coins): dp[i] min over coin. Code. रिकर coins^amt। टैब O(amount*coins): dp[i] मिन ओवर coin। कोड।

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

"Coin Change: Given coins array and amount, return min number of coins to make exactly amount (unlimited each), or -1 if impossible. Brute: Recursive helper(amt): if amt==0 return 0; if <0 return infinity (prune); else min over coins: 1 + helper(amt - coin). This tries every combo by subtracting one coin at a time, but O(coins^amount) time explodes for amount=100, coins=5—full permutation tree without reuse. DP fix: It's unbounded knapsack—min 'weight' (coins) for exact 'capacity' amount. Subproblems: Min coins for sub-amount k. Recurrence: dp[k] = min over coin: dp[k - coin] + 1 if k>=coin, else inf. Tabulate bottom-up: dp = array(amount+1, inf); dp[0]=0; for i=1 to amount: for coin in coins: if i>=coin dp[i] = min(dp[i], dp[i-coin] + 1). Return dp[amount] == inf ? -1 : dp[amount]. O(amount * coins) time (each cell updated per coin), O(amount) space—each sub-amount computed once, building from small to large. Memo alt top-down same. Edges: amount=0 returns 0, no way -1, single coin=amount if matches. Space opt: Loop coins outer, amounts backward for in-place. Interviewers love this as knapsack intro—ask for number of ways variant next." "कॉइन चेंज: coins ऐरे amount, एग्जैक्ट अमाउंट मिन नंबर (अनलिमिटेड), -1 इम्पॉसिबल। ब्रूट: recur helper(amt): ==0 0; <0 inf; min coin: 1 + helper(amt-coin)। हर कॉम्बो subtract, O(coins^amount) amount=100 coins=5 explode। DP: अनबाउंडेड नैपसैक—मिन 'वेट' (coins) 'कैपेसिटी' amount। सबप्रॉब्लम: k के लिए मिन। रेकरेंस: dp[k]=min coin: dp[k-coin]+1 k>=coin, else inf। टैब बॉटम-अप: dp[amount+1] inf; dp[0]=0; i=1 amount: coin in coins: i>=coin dp[i]=min(dp[i], dp[i-coin]+1)। dp[amount]==inf -1 else वैल्यू। O(amount*coins) टाइम (सेल per coin), O(amount) स्पेस—हर सब एक, स्मॉल से लार्ज। मेमो टॉप-डाउन सम। एज: 0 0, नो वे -1, सिंगल match। स्पेस ऑप्ट: coins outer, amounts backward in-place। इंटरव्यूअर्स नैपसैक इंट्रो लव—नंबर्स ऑफ वे वेरिएंट नेक्स्ट।"

Partition Equal Subset Sum (LC 416) - LeetCode पार्टिशन इक्वल सबसेट सम (LC 416) - लीटकोड

Problem: Can partition to equal sum. समस्या: इक्वल सम पार्टिशन।

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

  • Primary: 0/1 Knapsack, Subset Sum
  • Secondary: Partition Problem
  • Frequency: Medium (Feasibility DP)

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

  • Big O: O(n * sum/2) time, space.
  • Edge: Odd sum false.
  • Self: 0/1 knapsack for target sum/2.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Positive nums? sum up to 10^4? Two subsets exactly equal?" Quick heuristic: "Partition equal sum? Hints subset sum to total/2, 0/1 knapsack bool dp." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "पॉजिटिव nums? sum 10^4? टू सबसेट्स इक्वल?" क्विक ह्यूरिस्टिक: "इक्वल सम पार्टिशन? हिन्ट्स total/2 सबसेट सम, 0/1 नैपसैक बूल dp।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"two subsets equal sum" Positive? n up to 200? sum even? 0/1 Knapsack Feasibility Breakdown: 2^n subsets → DP O(n*sum/2). Ask: Odd false?
"partition array" Non-empty? Zeros? Achievable Sums Think: Target half, bool reachable.

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

  • Brute Force Subsets: Recur helper(i, current_sum): If current_sum == target return true; if i == nums.length or current_sum > target return false; else return helper(i+1, current_sum + nums[i]) (include) or helper(i+1, current_sum) (exclude)—generates all 2^n subsets, checking if any sums to target=total/2 (odd total false first); O(2^n) time, O(n) stack—exhaustive but only viable for n<=20.
  • Memoization (Top-Down DP): Memo on state (i, sum): If memo[i][sum] exists return; else recur include/exclude, store true/false. O(n * target) states (i=0..n, sum=0..target), each O(1) work, O(n * target) time/space—prunes by caching reachable sums per prefix, but still recursive.
  • 0/1 Knapsack Tabulation (Optimal Space-Optimized): If total odd false; target=total/2; bool dp[target+1] = false, dp[0]=true; for num in nums: for j=target down to num: dp[j] = dp[j] or dp[j - num] (can make j with/without this num). Return dp[target]. O(n * target) time, O(target) space—tracks achievable sums backward to avoid reuse; space opt since 1D.

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

Javascript
// Non-Optimized (Recursion Subsets): Branch include/exclude per num
function canPartition(nums) {
  // Total sum
  const total = nums.reduce((a, b) => a + b, 0);
  // Odd impossible
  if (total % 2 !== 0) return false;
  // Target half
  const target = total / 2;
  // Helper: from i with current sum
  function helper(i, sum) {
    // Achieved target
    if (sum === target) return true;
    // Exhausted nums or overshot
    if (i >= nums.length || sum > target) return false;
    // Branch: include this num or exclude
    return helper(i + 1, sum + nums[i]) || helper(i + 1, sum);
  }
  return helper(0, 0); // Start empty sum
// Time: O(2^n) - subset generation, Space: O(n) - stack
Why This Solution? यह सॉल्यूशन क्यों?
  • It systematically generates the power set by deciding include/exclude for each element, directly tying to the subset sum problem, which is easy to mentally simulate for small n like [1,5,11,5] targeting 12.
  • The early checks (sum > target false, i==length false unless exact) prune some invalid paths, and starting from sum=0 with odd total false keeps it efficient upfront without complex init.
  • Exponential 2^n highlights the DP need: Many subsets share the same partial sum, recomputed via different orders—sets stage for knapsack DP as subset sum optimization.

Optimized Solution (DP Set for Achievable Sums) ऑप्टिमाइज्ड सॉल्यूशन (DP सेट फॉर अचीवेबल सम्स)

Javascript
// Optimized (DP Set for Achievable Sums): Track reachable sums iteratively
function canPartition(nums) {
  // Total sum
  const total = nums.reduce((a, b) => a + b, 0);
  // Odd impossible
  if (total % 2 !== 0) return false;
  // Target half
  const target = total / 2;
  // Set of achievable sums starting with 0
  const dp = new Set([0]);
  // For each num
  for (let num of nums) {
    // New set to avoid concurrent mod
    const newDp = new Set();
    // For each existing sum
    for (let sum of dp) {
      // Add without this num
      newDp.add(sum);
      // Add with this num
      newDp.add(sum + num);
    }
    // Update dp
    dp = newDp;
    // Early exit if target reached
    if (dp.has(target)) return true;
  }
  return dp.has(target); // Final check
// Time: O(n * sum/2) - sums grow to target, Space: O(sum/2) - set size
Why This Solution? यह सॉल्यूशन क्यों?
  • Efficiently tracks all achievable sums up to target using a set that grows with each num (add sum and sum+num), hitting O(n * target/2) time by only storing reachable values without exploring impossibles.
  • Uses O(target/2) space with a set (or bool array), which is practical for sum~10^4, and early return if target reached avoids full computation—balances time/space for subset sum.
  • As 0/1 knapsack (each num used at most once), it generalizes to capacity problems, and the iterative update (newSet from old) prevents using the same num multiple times, making it correct and extensible.

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

2^n subsets. DP O(n*sum/2): Achievable set or bool dp. Code. 2^n सबसेट्स। DP O(n*sum/2): अचीवेबल सेट या बूल dp। कोड।

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

"Partition Equal Subset Sum: Can split nums into two subsets with equal sum? First, compute total = sum(nums); if total odd, false (can't split even). Set target = total / 2; now it's 'can we make subset sum exactly target?'—classic 0/1 knapsack feasibility. Brute: Recur helper(i, current_sum): if current_sum == target return true; if i == nums.length or current_sum > target return false; else return helper(i+1, current_sum + nums[i]) (include) || helper(i+1, current_sum) (exclude). This explores all 2^n subsets, O(2^n) time, O(n) stack—works for n=10 but not 40. DP: Subset sum has overlapping (same sum from different prefixes) and optimal (built from smaller sums). Use bool dp[target+1] = false; dp[0] = true (empty subset sums 0); for each num: for j = target down to num: dp[j] = dp[j] || dp[j - num] (j achievable without or with this num). Backward avoids using num >1 time. Return dp[target]. O(n * target) time (each cell per num), O(target) space—efficient since target <= sum/2 ~10^4. Set alt: Start achievable = {0}; for num: newSet; for sum in achievable: add sum, sum+num to newSet; if target in, true early. Edges: Empty total=0 true (two empty), odd false, [1,2,3,6] target=6 true ([3,1,2]). This is knapsack gateway—interviewers ask min coins or ways variants." "पार्टिशन इक्वल सबसेट सम: nums दो सबसेट्स इक्वल सम? total=sum(nums); ऑड फॉल्स (ईवन न स्प्लिट)। target=total/2; 'target सबसेट सम पॉसिबल?'—0/1 नैपसैक फिजिबिलिटी। ब्रूट: recur helper(i,current_sum): ==target ट्रू; i==length or >target फॉल्स; helper(i+1,sum+nums[i]) || helper(i+1,sum)। 2^n सबसेट्स, O(2^n) टाइम, O(n) स्टैक—n=10 ok नॉट 40। DP: सबसेट सम ओवरलैपिंग (सम different prefixes से), ऑप्टिमल (स्मॉलर sums से)। बूल dp[target+1]=फॉल्स; dp[0]=ट्रू (एंप्टी 0); num के लिए: j=target num down: dp[j] = dp[j] || dp[j-num] (without or with)। बैकवर्ड num >1 अवॉइड। dp[target]। O(n*target) टाइम, O(target) स्पेस—target~10^4 एफिशिएंट। सेट अल्ट: achievable={0}; num: newSet; sum in: add sum, sum+num; target in early। एज: एंप्टी 0 ट्रू (टू एंप्टी), ऑड फॉल्स, [1,2,3,6] 6 ट्रू ([3,1,2])। नैपसैक गेटवे—इंटरव्यूअर्स मिन coins or ways पूछते।"

Jump Game (LC 55) - LeetCode जंप गेम (LC 55) - लीटकोड

Problem: Can reach end. समस्या: एंड पहुंच सकते।

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

  • Primary: Greedy, Reachability
  • Secondary: 1D Jump
  • Frequency: High (Greedy yes/no)

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

  • Big O: O(n) time, O(1) space.
  • Edge: [0] true.
  • Self: Greedy track max reach.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Non-neg jumps? n up to 10^4? Always possible?" Quick heuristic: "Reach end with jumps? Hints greedy max reach, no DP needed." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "नॉन-नेग? n 10^4? अल्वेज पॉसिबल?" क्विक ह्यूरिस्टिक: "जंप्स से एंड रीच? हिन्ट्स ग्रीडी मैक्स रीच, नो DP।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"can jump to last index" Non-neg? n max? Zeros? Greedy Max Reach Breakdown: DP O(n^2) → Greedy O(n). Ask: Impossible false?
"nums[i] max jump" From i? End n-1? Farthest Extension Think: Chain breaks if i > max.

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

  • DP Reachability: Bool dp[n] init false, dp[0]=true; for i=0 to n-1: if dp[i] true, for j=1 to nums[i]: if i+j < n set dp[i+j]=true (reachable from i). Return dp[n-1]. O(n²) time from nested loops (worst all 1's), O(n) space—explicitly marks every reachable position, correct but slow for n=10^4.
  • BFS from Positions: Queue starting i=0 jumps=0; while queue: Dequeue pos, for next=pos+1 to pos+nums[pos]: If next==n-1 true; enqueue if not visited. But since linear, use set visited. O(n) time if careful, O(n) queue/space—explores breadth-first but overkill for 1D.
  • Greedy Farthest Reach (Optimal): maxReach=0; for i=0 to n-1: if i > maxReach return false (gap); maxReach = max(maxReach, i + nums[i]); if maxReach >= n-1 return true. O(n) time, O(1) space—single pass updates the farthest any position in current reach can go, checking no gaps.

Non-Optimized Solution (DP Reachability) नॉन-ऑप्टिमाइज्ड सॉल्यूशन (DP रीचेबिलिटी)

Javascript
// Non-Optimized (DP Reachability): Mark reachable positions
function canJump(nums) {
  // Length n
  const n = nums.length;
  // dp[i]: true if i reachable
  const dp = new Array(n).fill(false);
  // Start reachable
  dp[0] = true;
  // For each position
  for (let i = 1; i < n; i++) {
    // Check if any prior j can reach i
    for (let j = 0; j < i; j++) {
      if (dp[j] && j + nums[j] >= i) {
        dp[i] = true; // Mark reachable
        break; // No need further
      }
    }
  }
  return dp[n - 1]; // End reachable?
// Time: O(n^2) - nested loops, Space: O(n) - dp array
Why This Solution? यह सॉल्यूशन क्यों?
  • Provides a clear, visual way to track reachability by marking dp[i] true only if some previous j can jump to it, making it easy to debug and see propagation in small arrays like [2,3,1,1,4].
  • The inner loop precisely simulates all possible jumps from each reachable i, ensuring no false positives, and the break on first set optimizes a bit but keeps logic transparent.
  • Its O(n²) nature reveals the inefficiency—rechecking from every i even if later ones are covered—setting up greedy as the insight: We don't need per-position, just if the chain breaks.

Optimized Solution (Greedy Farthest Reach) ऑप्टिमाइज्ड सॉल्यूशन (ग्रीडी फर्सेस्ट रीच)

Javascript
// Optimized (Greedy Farthest Reach): Track max extension
function canJump(nums) {
  // Farthest reachable index
  let maxReach = 0;
  // Scan array
  for (let i = 0; i < nums.length; i++) {
    // If current i unreachable
    if (i > maxReach) return false; // Gap
    // Update max from this i
    maxReach = Math.max(maxReach, i + nums[i]);
    // Early exit if end covered
    if (maxReach >= nums.length - 1) return true;
  }
  return true; // Reached end
// Time: O(n) - single pass, Space: O(1) - one var
Why This Solution? यह सॉल्यूशन क्यों?
  • Runs in O(n) time with a single pass that greedily extends the max reachable as far as possible from current positions, early-exiting on gaps or success without marking anything.
  • Uses O(1) space beyond input, just one variable for maxReach, which is pivotal for 1D jump problems where DP would waste O(n)—proves greedy's power for yes/no reachability.
  • The check i > maxReach false catches unreachable spots immediately, and updating only when i <= maxReach ensures we consider all viable extensions, making it both correct and minimal computation.

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

DP O(n^2) mark reach. Greedy O(n): Max reach update. Code. DP O(n^2) मार्क रीच। ग्रीडी O(n): मैक्स रीच अपडेट। कोड।

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

"Jump Game: nums[i] is max jump from i, can you reach nums.length-1? DP way: Bool dp[n] false, dp[0]=true; for i=0 to n-1 if dp[i]: for j=1 to nums[i] if i+j < n: dp[i+j]=true (set reachable). Return dp[n-1]—this marks every spot someone can land on, O(n²) time from the inner loop (worst if all nums[i]=n-i), O(n) space, correct but quadratic for n=10^4. BFS could queue positions and explore jumps level-by-level, but still O(n) space. Greedy insight: We don't care about exact paths, just if the reachability chain breaks. So, maxReach = 0; for i=0 to n-1: if i > maxReach return false (gap, can't get here); maxReach = max(maxReach, i + nums[i]) (farthest from this i); if maxReach >= n-1 return true early. O(n) time, O(1) space—single pass, and since we process i in order, when we hit an i > maxReach, it's impossible; otherwise, update the global farthest any prior position can push. Edges: [0] true (already at end), [2,3,1,1,4] true (reach builds to 4), [3,2,1,0,4] false (maxReach=3 at i=3, but i=3 >3? Wait no, nums[3]=0 so stuck). This greedy works because jumps are non-negative—interviewers follow with min jumps." "जंप गेम: nums[i] i से मैक्स जंप, length-1 पहुंच? DP: बूल dp[n] फॉल्स, dp[0]=ट्रू; i=0 n-1 अगर dp[i]: j=1 nums[i] i+jmaxReach फॉल्स (गैप); maxReach=max(maxReach,i+nums[i]); >=n-1 early ट्रू। O(n) टाइम, O(1) स्पेस—सिंगल पास, i ऑर्डर प्रोसेस तो i>maxReach इम्पॉसिबल; else ग्लोबल फर्सेस्ट। एज: [0] ट्रू (एंड), [2,3,1,1,4] ट्रू (रीच 4), [3,2,1,0,4] फॉल्स (i=3 maxReach=3, nums[3]=0 स्टक)। नॉन-नेग जंप्स ग्रीडी—इंटरव्यूअर्स मिन जंप्स फॉलो।"

Jump Game II (LC 45) - LeetCode जंप गेम II (LC 45) - लीटकोड

Problem: Min jumps to end. समस्या: एंड मिन जंप्स।

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

  • Primary: Greedy, BFS Levels
  • Secondary: 1D Jump Min
  • Frequency: High (Greedy count)

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

  • Big O: O(n) time, O(1) space.
  • Edge: n=1 0.
  • Self: Greedy update end, jumps++ when reach current end.

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

Before diving in (15-30s): Clarify constraints & examples. Ask interviewer: "Always reachable? n up to 10^4? Min jumps?" Quick heuristic: "Min steps to end? Hints greedy ranges or BFS levels." डाइविंग से पहले (15-30s): कंस्ट्रेंट्स & एग्जाम्पल्स क्लैरिफाई। इंटरव्यूअर से पूछें: "अल्वेज रीचेबल? n 10^4? मिन जंप्स?" क्विक ह्यूरिस्टिक: "मिन स्टेप्स एंड? हिन्ट्स ग्रीडी रेंजेस या BFS लेवल्स।"

Keyword in Problem What to Check Hinted Approach/Pattern How to Think
"min jumps to last" Always possible? n max? Greedy Range Extension Breakdown: DP O(n^2) → Greedy O(n). Ask: Assume reachable.
"nums[i] max jump" Non-neg? End n-1? BFS Simulation Think: Current range farthest, ++ when end.

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

  • DP Min Jumps: dp[n] inf, dp[0]=0; for i=0 to n-1: if dp[i] < inf for j=1 to nums[i]: if i+j < n dp[i+j] = min(dp[i+j], dp[i] + 1). Return dp[n-1]. O(n²) time (inner up to n), O(n) space—computes min from every i, but redundant for far jumps.
  • BFS Levels (Queue): Queue (i=0, jumps=0); visited set; while queue: Dequeue size=queue.length, for each in level: For next=i+1 to i+nums[i]: If next==n-1 return jumps+1; enqueue if not visited. O(n) time, O(n) space—BFS where level = jumps, but queue grows.
  • Greedy Jump Ranges (Optimal): jumps=0, currentEnd=0, farthest=0; for i=0 to n-2: farthest = max(farthest, i + nums[i]); if i == currentEnd: jumps++, currentEnd = farthest, break if currentEnd >= n-1. O(n) time, O(1) space—simulates BFS levels without queue by tracking range end and max extend.

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

Javascript
// Non-Optimized (DP Min Jumps): Compute min to each position
function jump(nums) {
  // Length n
  const n = nums.length;
  // dp[i]: min jumps to i
  const dp = new Array(n).fill(Infinity);
  // Start 0 jumps
  dp[0] = 0;
  // For each position
  for (let i = 0; i < n; i++) {
    // From i, try jumps up to nums[i]
    for (let j = 1; j <= nums[i] && i + j < n; j++) {
      // Update min to target position
      dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
    }
  }
  return dp[n - 1]; // Min to end
// Time: O(n^2) - nested (worst all large jumps), Space: O(n) - dp
Why This Solution? यह सॉल्यूशन क्यों?
  • Accurately computes the minimum jumps to each position by considering all possible jumps from reachable i's, providing a full dp table you can inspect for paths or extensions like max profit.
  • The inner loop j=1 to nums[i] precisely limits jumps to the array's max step, and min update ensures the cheapest way, with inf init handling unreachable spots cleanly.
  • O(n²) exposes the bottleneck—revisiting updates from early i's that cover far—motivating greedy: Instead of per-position min, track collective range per 'jump group' to prune.

Optimized Solution (Greedy Jump Ranges) ऑप्टिमाइज्ड सॉल्यूशन (ग्रीडी जंप रेंजेस)

Javascript
// Optimized (Greedy Jump Ranges): Simulate BFS levels without queue
function jump(nums) {
  // Jumps count
  let jumps = 0;
  // Current jump end
  let currentEnd = 0;
  // Farthest in current range
  let farthest = 0;
  // Scan up to second last
  for (let i = 0; i < nums.length - 1; i++) {
    // Update farthest from this i
    farthest = Math.max(farthest, i + nums[i]);
    // Reached end of current jump range
    if (i === currentEnd) {
      jumps++; // Increment jumps
      currentEnd = farthest; // New range end
      // Early if end covered
      if (currentEnd >= nums.length - 1) break;
    }
  }
  return jumps;
// Time: O(n) - single pass, Space: O(1) - three vars
Why This Solution? यह सॉल्यूशन क्यों?
  • Processes the array in one O(n) pass, using the current range [0 to currentEnd] to find the farthest extension (farthest), then increments jumps only when exhausting that range—mimics BFS levels efficiently.
  • O(1) space with three vars (jumps, currentEnd, farthest) captures the greedy essence: Maximize coverage per jump without tracking per-position, which is optimal for this unweighted 1D graph.
  • Early break if currentEnd >= n-1 avoids unnecessary iterations, and the i <= currentEnd implicit check ensures we only consider positions in the current jump's reach, making it both correct and minimal.

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

DP O(n^2) min to each. Greedy O(n): Range farthest, ++ at end. Code. DP O(n^2) मिन टू ईच। ग्रीडी O(n): रेंज फर्सेस्ट, ++ एट एंड। कोड।

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

"Jump Game II: Min number of jumps to reach last index, where nums[i] is max from i. DP: dp[0]=0, inf else; for i=0 to n-1 if dp[i]= n-1 break. Return jumps. O(n) time, O(1) space—when we finish current jump's range (i==currentEnd), we 'pay' a jump and extend to the farthest we could have reached in that range. Edges: n=1 0 (no jump), [2,3,1,1,4] 2 (0 to 3 in jump1, 3 to4 in jump2), [3,2,1,0,4] 2 but wait nums[3]=0 so farthest=3 at i=3==currentEnd=3, jumps=2 but can't reach 4? No, at i=0 farthest=3, currentEnd=0 i=0==0 jumps=1 currentEnd=3; i=1 farthest=3+2=5? Wait nums[1]=2 i=1+2=3; i=2=1+1=3; i=3>3 false? No code to n-2=3, i=3==3 jumps=2 currentEnd=3 <4 false but wait code returns jumps but if can't? Wait, for [3,2,1,0,4] maxReach at i=0=3, i=1=1+2=3, i=2=2+1=3, i=3=3+0=3 <4, but since i=3 <=3 but farthest=3 =n-1 it breaks early, but if not, and you finish loop without, it means you couldn't extend to end, but wait, for this, when i==currentEnd=3, jumps++, but currentEnd=3 <4, but return jumps anyway—yes, incorrect for impossible, but problem assumes always possible per LC. Yes, LC 45 assumes you can reach, so no -1. Edges: [1] 0. Greedy simulates BFS without queue—interviewers pair with I." "जंप गेम II: लास्ट मिन जंप्स। DP: dp[0]=0 inf; i=0 n-1 dp[i]=n-1 ब्रेक। jumps रिटर्न। O(n) टाइम, O(1) स्पेस—करेंट जंप रेंज एंड्स (i==currentEnd) तो 'पे' जंप, नेक्स्ट फर्सेस्ट। एज: n=1 0, [2,3,1,1,4] 2 (0-3 jump1, 3-4 jump2)। LC 45 assumes reach, no -1। ग्रीडी BFS सिमुलेट no क्यू—इंटरव्यूअर्स I के साथ पेयर।"