🧩 LeetCode Hard में महारत: 7 जटिल समाधानों की व्याख्या 🔗

LeetCode Hard समस्याओं को हल करना अक्सर किसी दीवार से टकराने जैसा महसूस हो सकता है। हालाँकि, उन्हें समझने योग्य पैटर्न—जैसे डायनेमिक प्रोग्रामिंग, बैकट्रैकिंग और ग्राफ़ थ्योरी—में विभाजित करने से वे कहीं अधिक आसान हो जाती हैं।

इस पोस्ट में, मैं Go में हल की गई 7 सबसे दिलचस्प LeetCode Hard समस्याओं को साझा कर रहा हूँ। इस गाइड को यथासंभव उपयोगी बनाने के लिए, मैंने व्याख्याओं को मुख्य अंतर्ज्ञान (core intuition) और जटिलता (complexity) पर गहराई से केंद्रित किया है, जिससे समस्या के विवरण से लेकर काम करने वाले कोड तक की छलांग को समझना आसान हो जाता है।

📑 विषय-सूची 🔗


🔢 1. 60. Permutation Sequence 🔗

❓ समस्या 🔗

nn और kk दिए गए हैं, 11 से nn तक की संख्याओं का kवाँk^{\text{वाँ}} क्रमचय अनुक्रम (permutation sequence) लौटाएं। उदाहरण के लिए, यदि n=3n = 3 है, तो क्रमचय हैं: "123", "132", "213", "231", "312", "321"। यदि k=3k = 3 है, तो उत्तर "213" है।

💡 अंतर्ज्ञान (Intuition) 🔗

सभी क्रमचयों को जनरेट करने (जो बहुत धीमा होगा) के बजाय, हम फैक्टोरियल का लाभ उठाते हुए एक गणितीय दृष्टिकोण का उपयोग कर सकते हैं।

nn अंकों के लिए, कुल n!n! क्रमचय होते हैं। यदि हम पहले अंक को स्थिर (fix) कर देते हैं, तो शेष अंकों के (n−1)!(n-1)! क्रमचय होते हैं। हम यह गणना करके पहला अंक निर्धारित कर सकते हैं कि kवाँk^{\text{वाँ}} क्रमचय (n−1)!(n-1)! क्रमचयों के किस ब्लॉक में आता है। उपलब्ध अंकों की क्रमबद्ध सूची (sorted list) में हमारे अगले अंक का इंडेक्स बस (k−1)/(n−1)!(k-1) / (n-1)! होगा। एक अंक चुनने के बाद, हम kk को शेषफल k mod (n−1)!k \bmod (n-1)! में अपडेट करते हैं और रिकर्सन (recurse) करते हैं।

⏱️ जटिलता (Complexity) 🔗

💻 Go समाधान 🔗

import "fmt"

func getPermutation(n int, k int) string {
	factorial := 1
	digits := []int{}

	// Calculate factorials and populate the digits slice
	for i := 1; i <= n; i++ {
		factorial *= i
		digits = append(digits, i)
	}

	return solvePermutation(n-1, k-1, factorial/n, digits)
}

func solvePermutation(n, k, factorial int, digits []int) string {
	// Find which block of permutations 'k' falls into
	index := k / factorial
	res := fmt.Sprintf("%d", digits[index])

	if n <= 0 {
		return res
	}

	// Update k for the next level: k % factorial
	// Update factorial for the next level: factorial / n
	// Remove the selected digit from the slice
	nextK := k % factorial
	nextFactorial := factorial / n
	remainingDigits := append(digits[:index], digits[index+1:]...)

	res += solvePermutation(n-1, nextK, nextFactorial, remainingDigits)
	return res
}

🔍 2. 10. Regular Expression Matching 🔗

❓ समस्या 🔗

. (किसी भी एकल वर्ण से मेल खाता है) और * (पिछले तत्व के शून्य या अधिक से मेल खाता है) के साथ रेगुलर एक्सप्रेशन मैचिंग लागू करें। मैचिंग में संपूर्ण इनपुट स्ट्रिंग शामिल होनी चाहिए।

💡 अंतर्ज्ञान (Intuition) 🔗

यह एक क्लासिक डायनेमिक प्रोग्रामिंग समस्या है। हम अनावश्यक गणनाओं से बचने के लिए मेमोइज़ेशन (memoization) का उपयोग कर सकते हैं।

स्ट्रिंग s और पैटर्न p के किसी भी दिए गए वर्ण संयोजन पर, यदि पैटर्न में अगला वर्ण * है, तो हमारे पास दो विकल्प होते हैं:

  1. इसे छोड़ें (Skip it): पिछले तत्व की शून्य आवृत्तियों (occurrences) का उपयोग करें।
  2. मैच करना जारी रखें: यदि वर्तमान वर्ण मेल खाते हैं, तो s से एक वर्ण का उपभोग करें लेकिन संभावित रूप से अधिक मैच करने के लिए p में * पर ही बने रहें।

⏱️ जटिलता (Complexity) 🔗

💻 Go समाधान 🔗

func isMatch(s string, p string) bool {
	sn, pn := len(s), len(p)
	memo := make([][]int, sn+1)
	for i := range memo {
		memo[i] = make([]int, pn+1)
	}
	return solveRegex(s, p, sn, pn, 0, 0, memo)
}

func solveRegex(s, p string, sn, pn, si, pi int, memo [][]int) bool {
	if memo[si][pi] == 1 { return false }
	if memo[si][pi] == 2 { return true }

	res := false
	if si == sn && pi == pn {
		res = true
	} else if pi+1 < pn && p[pi+1] == '*' {
		// Option A: Zero occurrences
		if solveRegex(s, p, sn, pn, si, pi+2, memo) {
			res = true
		// Option B: One or more occurrences (if current char matches)
		} else if si < sn && (p[pi] == '.' || p[pi] == s[si]) && solveRegex(s, p, sn, pn, si+1, pi, memo) {
			res = true
		}
	} else if si < sn && pi < pn && (p[pi] == '.' || p[pi] == s[si]) {
		// Normal character match
		res = solveRegex(s, p, sn, pn, si+1, pi+1, memo)
	}

	if res {
		memo[si][pi] = 2
	} else {
		memo[si][pi] = 1
	}
	return res
}

🌳 3. 124. Binary Tree Maximum Path Sum 🔗

❓ समस्या 🔗

एक गैर-खाली बाइनरी ट्री दिया गया है, अधिकतम पाथ योग (maximum path sum) ज्ञात करें। एक पाथ पेरेंट-चाइल्ड कनेक्शन में ऊपर या नीचे जा सकता है लेकिन उसका रूट (root) से गुजरना आवश्यक नहीं है।

💡 अंतर्ज्ञान (Intuition) 🔗

हम डेप्थ-फर्स्ट सर्च (DFS) का उपयोग करते हैं। प्रत्येक नोड पर, हम दो प्रकार के पाथ का मूल्यांकन करते हैं:

  1. विस्तार योग्य (fromRoot): वर्तमान नोड से शुरू होने वाला और उसकी किसी एक शाखा के नीचे जाने वाला अधिकतम पाथ। एक पेरेंट नोड इस पाथ का उपयोग कर सकता है।
  2. गैर-विस्तार योग्य (other): वर्तमान सबट्री के भीतर पूरी तरह से समाहित अधिकतम पाथ (उदाहरण के लिए, बाएं चाइल्ड से शुरू होकर, वर्तमान नोड तक ऊपर जाना, और दाएं चाइल्ड तक नीचे जाना)। यह पाथ “बंद (closed)” होता है और इसे किसी पेरेंट तक ऊपर की ओर विस्तारित नहीं किया जा सकता है।

हमारा ग्लोबल मैक्स (global max) हमारे द्वारा खोजे गए सभी “गैर-विस्तार योग्य” पाथों में से सबसे अधिक, या रूट का विस्तार योग्य पाथ होगा।

⏱️ जटिलता (Complexity) 🔗

💻 Go समाधान 🔗

import "math"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func maxPathSum(root *TreeNode) int {
	fromRoot, other := solveTree(root)
	if fromRoot > other {
		return fromRoot
	}
	return other
}

func solveTree(root *TreeNode) (int, int) {
	if root == nil {
		return math.MinInt, math.MinInt
	}

	left, otherLeft := solveTree(root.Left)
	right, otherRight := solveTree(root.Right)

	// Extendable path (can only pick one branch or stop at node)
	currentFromRoot := max([]int{
		root.Val,
		sum([]int{root.Val, left}),
		sum([]int{root.Val, right}),
	})

	// Closed path (can arch over the current node, or be completely inside a child)
	currentOther := max([]int{
		left, right, otherLeft, otherRight,
		sum([]int{root.Val, left, right}),
	})

	return currentFromRoot, currentOther
}

func max(s []int) int {
	res := math.MinInt
	for _, v := range s {
		if v > res { res = v }
	}
	return res
}

func sum(s []int) int {
	res := 0
	for _, v := range s {
		if v == math.MinInt { return math.MinInt }
		res += v
	}
	return res
}

🧮 4. 37. Sudoku Solver 🔗

❓ समस्या 🔗

9x9 सुडोकू पहेली को हल करने के लिए एक प्रोग्राम लिखें। आपको मानक सुडोकू नियमों (पंक्तियों, स्तंभों और 3x3 सब-बॉक्स) को संतुष्ट करना होगा।

💡 अंतर्ज्ञान (Intuition) 🔗

इसके लिए एक बैकट्रैकिंग (backtracking) एल्गोरिदम की आवश्यकता होती है। इसे कुशल बनाने और LeetCode पर Time Limit Exceeded (TLE) त्रुटियों से बचने के लिए, हम एक ह्यूरिस्टिक (heuristic) का उपयोग करके खोज को अनुकूलित करते हैं: हमेशा सबसे कम संभावित वैध संख्याओं वाले खाली सेल को पहले भरने का प्रयास करें। हम तुरंत यह जाँचने के लिए बूलियन ऐरे का उपयोग करते हैं कि कोई संख्या किसी पंक्ति, स्तंभ या 3x3 बॉक्स में उपलब्ध है या नहीं।

⏱️ जटिलता (Complexity) 🔗

💻 Go समाधान 🔗

func solveSudoku(board [][]byte) {
	var rows, cols [9][9]bool
	var boxes [3][3][9]bool

	// Populate initial state
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if board[i][j] != '.' {
				idx := board[i][j] - '1'
				rows[i][idx], cols[j][idx], boxes[i/3][j/3][idx] = true, true, true
			}
		}
	}
	backtrackSudoku(board, &rows, &cols, &boxes)
}

func backtrackSudoku(board [][]byte, rows, cols *[9][9]bool, boxes *[3][3][9]bool) bool {
	bestI, bestJ := -1, -1
	minOptions := 10 // Start higher than the max possible options (9)

	// Heuristic: Find the cell with the fewest valid options
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			if board[i][j] == '.' {
				options := 0
				for val := 0; val < 9; val++ {
					if !rows[i][val] && !cols[j][val] && !boxes[i/3][j/3][val] {
						options++
					}
				}
				if options < minOptions {
					minOptions = options
					bestI, bestJ = i, j
				}
			}
		}
	}

	// Base case: No empty cells left
	if bestI == -1 { return true }

	// Try placing valid numbers in the chosen optimal cell
	for val := 0; val < 9; val++ {
		if !rows[bestI][val] && !cols[bestJ][val] && !boxes[bestI/3][bestJ/3][val] {
			board[bestI][bestJ] = byte(val + '1')
			rows[bestI][val], cols[bestJ][val], boxes[bestI/3][bestJ/3][val] = true, true, true

			if backtrackSudoku(board, rows, cols, boxes) {
				return true
			}

			// Backtrack
			board[bestI][bestJ] = '.'
			rows[bestI][val], cols[bestJ][val], boxes[bestI/3][bestJ/3][val] = false, false, false
		}
	}
	return false
}

🎓 5. 1494. Parallel Courses II 🔗

❓ समस्या 🔗

आपको एक पूर्णांक nn दिया गया है, जो दर्शाता है कि 11 से nn तक लेबल किए गए nn कोर्स हैं। आपको एक ऐरे relations भी दिया गया है जहाँ relations[i] = [prevCourse, nextCourse], जो एक पूर्व-आवश्यकता (prerequisite) संबंध का प्रतिनिधित्व करता है। एक सेमेस्टर में, आप अधिकतम kk कोर्स ले सकते हैं। सभी कोर्स लेने के लिए आवश्यक न्यूनतम सेमेस्टर की संख्या लौटाएं।

💡 अंतर्ज्ञान (Intuition) 🔗

चूँकि nn छोटा है (n≤15n \leq 15), हम बिटमास्क के साथ संयुक्त ब्रेड्थ-फर्स्ट सर्च (BFS) का उपयोग कर सकते हैं। एक बिटमास्क उन कोर्सों की स्थिति का प्रतिनिधित्व करता है जिन्हें हमने पूरा कर लिया है। प्रत्येक सेमेस्टर में, हम सभी उपलब्ध कोर्सों (जिनकी पूर्व-आवश्यकताएं पूरी तरह से पूरी हो चुकी हैं) की पहचान करते हैं। यदि उपलब्ध कोर्स kk से अधिक हैं, तो हमें सबमास्क गणना (submask enumeration) का उपयोग करके आकार kk के सभी संभावित संयोजनों के माध्यम से इटरेट करना होगा। हम समान संयोजनों पर दोबारा जाने से रोकने के लिए visited ऐरे का उपयोग करते हैं।

⏱️ जटिलता (Complexity) 🔗

💻 Go समाधान 🔗

func minNumberOfSemesters(n int, relations [][]int, k int) int {
	// prerequisites[i] is a bitmask of courses that must be taken before course i
	prerequisites := make([]int, n)
	for _, relation := range relations {
		prevCourse := relation[0] - 1
		nextCourse := relation[1] - 1
		prerequisites[nextCourse] |= 1 << prevCourse
	}

	// states and costs act as a BFS queue
	states := []int{0}
	costs := []int{0}
	added := map[int]bool{0: true}

	for cur := 0; ; cur++ {
		state := states[cur]
		cost := costs[cur]

		// Base case: All courses have been taken
		if state == (1<<n)-1 {
			return cost
		}

		// Find all courses available to take this semester
		courses := []int{}
		next := state
		for course := 0; course < n; course++ {
			bit := 1 << course
			if (state&bit) == 0 && (prerequisites[course]|state) == state {
				courses = append(courses, course)
				next |= bit
			}
		}

		add := func(next int) {
			if added[next] {
				return
			}
			added[next] = true
			states = append(states, next)
			costs = append(costs, cost+1)
		}

		// If we can take all available courses in one semester, do so
		if len(courses) <= k {
			add(next)
			continue
		}

		// Otherwise, explore all combinations of size k
		var addStates func(next, k, from int)
		addStates = func(next, k, from int) {
			if k == 0 {
				add(next)
				return
			}
			for i := from; i < len(courses); i++ {
				addStates(next|(1<<courses[i]), k-1, i+1)
			}
		}
		addStates(state, k, 0)
	}
}

📐 6. 363. Max Sum of Rectangle No Larger Than K 🔗

❓ समस्या 🔗

एक m×nm \times n मैट्रिक्स और एक पूर्णांक kk दिया गया है, मैट्रिक्स में किसी आयत का अधिकतम योग लौटाएं ताकि उसका योग kk से बड़ा न हो।

💡 अंतर्ज्ञान (Intuition) 🔗

हम बाएं और दाएं स्तंभ की सीमाओं को स्थिर करके 2D मैट्रिक्स को 1D ऐरे में संपीड़ित (compress) कर सकते हैं। एक बार जब हमारे पास उन स्तंभों के बीच पंक्ति के योग का प्रतिनिधित्व करने वाला 1D ऐरे आ जाता है, तो समस्या सबऐरे योग ≤k\leq k खोजने तक सीमित हो जाती है। प्रीफिक्स योगों की एक क्रमबद्ध सूची बनाए रखकर (बाइनरी सर्च ट्री या सरल सॉर्टेड ऐरे इंसर्शन का उपयोग करके), हम कुशलतापूर्वक सबसे छोटे प्रीफिक्स योग को क्वेरी कर सकते हैं जो current_prefix - past_prefix <= k को संतुष्ट करता है, या O(1)O(1) समय में किसी भी सब-रेक्टेंगल को क्वेरी करने के लिए 2D प्रीफिक्स सम टेबल की पूर्व-गणना (precompute) कर सकते हैं।

⏱️ जटिलता (Complexity) 🔗

💻 Go समाधान 🔗

import "math"

func maxSumSubmatrix(matrix [][]int, k int) int {
	n := len(matrix)
	m := len(matrix[0])
	res := math.MinInt
	sums := make([][]int, n)
	for i := 0; i < n; i++ {
		sums[i] = make([]int, m)
	}

	// Precompute 2D prefix sums
	sums[0][0] = matrix[0][0]
	for i := 1; i < n; i++ {
		sums[i][0] = matrix[i][0] + sums[i-1][0]
	}
	for j := 1; j < m; j++ {
		sums[0][j] = matrix[0][j] + sums[0][j-1]
	}
	for i := 1; i < n; i++ {
		for j := 1; j < m; j++ {
			sums[i][j] = matrix[i][j] + sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1]
		}
	}

	// Evaluate all possible subrectangles using inclusion-exclusion
	for starti := 0; starti < n; starti++ {
		for startj := 0; startj < m; startj++ {
			for endi := starti; endi < n; endi++ {
				for endj := startj; endj < m; endj++ {
					sum := sums[endi][endj]
					if starti > 0 {
						sum -= sums[starti-1][endj]
					}
					if startj > 0 {
						sum -= sums[endi][startj-1]
					}
					if starti > 0 && startj > 0 {
						sum += sums[starti-1][startj-1]
					}
					if sum <= k && sum > res {
						res = sum
					}
				}
			}
		}
	}
	return res
}

🔗 7. 685. Redundant Connection II 🔗

❓ समस्या 🔗

एक निर्देशित ग्राफ़ (directed graph) में, रूट नोड को छोड़कर प्रत्येक नोड का ठीक एक पेरेंट होता है, और रूट नोड का कोई पेरेंट नहीं होता है। एक अतिरिक्त निर्देशित किनारा (directed edge) जोड़ा गया है। वह किनारा खोजें जिसे हटाया जा सकता है ताकि परिणामी ग्राफ़ एक वैध रूटेड ट्री बन जाए। यदि कई उत्तर हैं, तो इनपुट में सबसे अंत में आने वाला उत्तर लौटाएं।

💡 अंतर्ज्ञान (Intuition) 🔗

चूँकि यह एक निर्देशित ग्राफ़ है, इसलिए जोड़ा गया किनारा दो में से एक समस्या (या दोनों) पैदा करता है:

  1. एक नोड के दो पेरेंट हो जाते हैं।
  2. एक चक्र (cycle) बन जाता है।

हम सबसे पहले यह देखने के लिए स्कैन करते हैं कि क्या किसी नोड के दो पेरेंट हैं। यदि ऐसा है, तो अनावश्यक किनारा उस नोड की ओर इशारा करने वाले दो किनारों में से एक होना चाहिए। अन्यथा, अतिरिक्त किनारा एक निर्देशित चक्र बनाता है। हम विपरीत इनपुट क्रम में उम्मीदवार किनारों का परीक्षण कर सकते हैं और DFS (या यूनियन-फाइंड) के माध्यम से सत्यापित कर सकते हैं कि क्या उम्मीदवार किनारे को हटाने से एक वैध रूटेड ट्री बचता है जहाँ सभी NN नोड्स बिना किसी चक्र के रूट से पहुँचे जा सकते हैं।

⏱️ जटिलता (Complexity) 🔗

💻 Go समाधान 🔗

func findRedundantDirectedConnection(edges [][]int) []int {
	n := len(edges)
	parents := map[int][]int{}
	outs := map[int][]int{}
	for _, edge := range edges {
		src := edge[0] - 1
		dst := edge[1] - 1
		parents[dst] = append(parents[dst], src)
		outs[src] = append(outs[src], dst)
	}

	roots := map[int]bool{}
	bad := -1
	for i := 0; i < n; i++ {
		if len(parents[i]) == 0 {
			roots[i] = true
		}
		if len(parents[i]) > 1 {
			bad = i
		}
	}

	if len(roots) == 0 {
		for i := 0; i < n; i++ {
			if check(n, outs, i, -1, -1, map[int]bool{}) {
				roots[i] = true
			}
		}
	}

	if len(roots) > 1 {
		for i := len(edges) - 1; i >= 0; i-- {
			edge := edges[i]
			src := edge[0] - 1
			dst := edge[1] - 1
			if roots[dst] {
				return []int{src + 1, dst + 1}
			}
		}
	}

	for root := range roots {
		if len(parents[root]) > 0 {
			return []int{parents[root][0] + 1, root + 1}
		}
		for from := len(parents[bad]) - 1; from >= 0; from-- {
			if check(n, outs, root, parents[bad][from], bad, map[int]bool{}) {
				return []int{parents[bad][from] + 1, bad + 1}
			}
		}
	}
	return []int{-1, -1}
}

func check(n int, outs map[int][]int, from, badfrom, badto int, visited map[int]bool) bool {
	if visited[from] {
		return false
	}
	visited[from] = true
	if len(visited) == n {
		return true
	}
	for _, to := range outs[from] {
		if from == badfrom && to == badto {
			continue
		}
		if check(n, outs, to, badfrom, badto, visited) {
			return true
		}
	}
	return false
}

क्या आपको यह विश्लेषण पसंद आया? LeetCode Hard समस्याओं के लिए धैर्य की आवश्यकता होती है, लेकिन अंतर्निहित पैटर्न का अध्ययन करने से यह प्रक्रिया दोहराने योग्य बन जाती है। निर्माण करते रहें, अभ्यास करते रहें, और आपके साक्षात्कारों के लिए शुभकामनाएँ!


📚 मेरी निःशुल्क ई-बुक डाउनलोड करें 🔗

काउए की जीवनशैली का क्यूरेटेड ऑफ़लाइन संस्करण प्राप्त करें—🍏 स्वास्थ्य, 💰 धन, ❤️ प्रेम और 🧘 अर्थ को बेहतर बनाने के लिए एक व्यावहारिक मार्गदर्शिका।

काउए की जीवनशैली

काउए की जीवनशैली

📬 न्यूज़लेटर की सदस्यता लें 🔗

जब भी मैं बेहतर जीवन जीने पर नए निबंध, पुस्तक सारांश और व्यावहारिक गाइड प्रकाशित करूँ, तो सूचना प्राप्त करें। कोई स्पैम नहीं—कभी भी सदस्यता समाप्त करें।


💬 टिप्पणियाँ और चर्चा 🔗

क्या आपका कोई प्रश्न, दृष्टिकोण या सुझाव है? नीचे अपने विचार साझा करें। टिप्पणियाँ GitHub Discussions (विज्ञापन-मुक्त और स्पैम-मुक्त) द्वारा संचालित हैं—टिप्पणी करने या प्रतिक्रिया देने के लिए नीचे Sign in with GitHub पर क्लिक करें (निःशुल्क GitHub खाता बनाने में एक मिनट से भी कम समय लगता है)।



अंतिम अपडेट: 11 अक्टू॰ 2026.

अस्वीकरण (DISCLAIMER): इस साइट की सामग्री केवल सूचनात्मक और शैक्षिक उद्देश्यों के लिए है और यह चिकित्सा, मनोवैज्ञानिक, वित्तीय, निवेश, कर या कानूनी सलाह का गठन नहीं करती है। यहाँ प्रस्तुत विचार, संकलन और राय पूरी तरह से मेरे अपने हैं और मेरे नियोक्ता का प्रतिनिधित्व नहीं करते हैं। पुस्तकों, व्याख्यानों और लेखों के सारांश स्वतंत्र शैक्षिक टिप्पणियाँ हैं और उनके संबंधित लेखकों की बौद्धिक संपदा बने रहते हैं। संपादन, स्वरूपण और संश्लेषण में सहायता के लिए AI उपकरणों का उपयोग किया जा सकता है; यद्यपि सटीकता सुनिश्चित करने का हर संभव प्रयास किया जाता है, फिर भी त्रुटियाँ हो सकती हैं। गोपनीयता (PRIVACY): यह साइट वैकल्पिक न्यूज़लेटर सदस्यता (follow.it), टिप्पणियों (giscus / GitHub Discussions) और एम्बेडेड मीडिया (YouTube) के लिए तृतीय-पक्ष सेवाओं का उपयोग करती है, जो अपनी संबंधित गोपनीयता नीतियों के अनुसार आगंतुकों के IP पते और कुकीज़ को संसाधित कर सकती हैं।