/*============================================================ Kadane's Algorithm — Complete MDX Guide ============================================================ Interactive components embedded as inline JSX. Requires: React, MDX runtime, a syntax highlighter (e.g. prism-react-renderer). ============================================================*/ "use strict"; const React = arguments[0].React; const { useState, useEffect, useRef, useMemo, useCallback, useReducer } = React; const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0]; const metadata = { title: "Kadane's Algorithm (Maximum Subarray)", tier: "Tier 0 — Foundations", prerequisites: ["Time & Space Complexity", "Prefix Sum Techniques"], requiredBy: ["Sliding Window (Tier 1)", "Dynamic Programming (Tier 4)"], complexity: { time: "O(n)", space: "O(1)" } }; const KadaneStepper = () => { const [nums, setNums] = React.useState([-2, 1, -3, 4, -1, 2, 1, -5, 4]); const [step, setStep] = React.useState(0); const simulate = arr => { const s = []; let meh = arr[0], msf = arr[0], subStart = 0, subEnd = 0; s.push({ i: 0, meh, msf, subStart: 0, subEnd: 0, decision: "Initialize with first element", extendVal: null, freshVal: null, detail: `Start at index 0. Both maxEndingHere and maxSoFar = ${arr[0]}. Best subarray so far is just [${arr[0]}].` }); for (let i = 1; i < arr.length; i++) { const extendVal = meh + arr[i]; const freshVal = arr[i]; let decision, detail; if (freshVal > extendVal) { meh = freshVal; decision = `Start fresh (${freshVal} > ${extendVal})`; subStart = i; subEnd = i; detail = `nums[${i}] = ${arr[i]}. Extend would give ${extendVal}, starting fresh gives ${freshVal}. The old running sum was negative — it's dragging us down. New subarray begins here.`; } else { meh = extendVal; decision = `Extend (${extendVal} ≥ ${freshVal})`; subEnd = i; detail = `nums[${i}] = ${arr[i]}. Extend gives ${extendVal}, starting fresh gives ${freshVal}. Extending is better — the running sum still helps.`; } const oldMsf = msf; if (meh > msf) { msf = meh; detail += ` New global max! ${msf} beats old ${oldMsf}.`; } else { detail += ` maxSoFar stays ${msf}.`; } s.push({ i, meh, msf, subStart, subEnd, decision, extendVal, freshVal, detail }); } s.push({ i: -1, meh, msf, subStart, subEnd, decision: "Done!", extendVal: null, freshVal: null, detail: `Answer: ${msf}. The maximum subarray is [${arr.slice(subStart, subEnd + 1).join(", ")}] from index ${subStart} to ${subEnd}.` }); return s; }; const steps = React.useMemo(() => simulate(nums), [nums]); const s = steps[step]; const loadArr = arr => { setNums(arr); setStep(0); }; return _jsxs("div", { style: { margin: "2rem 0", padding: "1.5rem", border: "1px solid #e5e7eb", borderRadius: 12, background: "#fafafa" }, children: [_jsxs("div", { style: { fontSize: 13, color: "#6b7280", marginBottom: 8, display: "flex", gap: 16, flexWrap: "wrap" }, children: [_jsx("span", { children: "🟣 Current index" }), _jsx("span", { children: "🟢 Current best subarray" })] }), _jsx("div", { style: { display: "flex", gap: 8, margin: "16px 0", flexWrap: "wrap" }, children: nums.map((n, j) => { const isActive = j === s.i; const inSub = j >= s.subStart && j <= s.subEnd; let bg = "#fff", border = "1px solid #d1d5db"; if (inSub && isActive) { bg = "#6ee7b1"; border = "2px solid #059669"; } else if (isActive) { bg = "#c4b5fd"; border = "2px solid #7c3aed"; } else if (inSub) { bg = "#d1fae5"; border = "1px solid #059669"; } return _jsxs("div", { style: { width: 52, height: 52, display: "flex", alignItems: "center", justifyContent: "center", borderRadius: 8, border, background: bg, fontWeight: 600, fontSize: 15, position: "relative", transition: "all 0.3s" }, children: [_jsx("span", { style: { position: "absolute", top: -16, fontSize: 11, color: "#9ca3af", fontWeight: 400 }, children: j }), n] }, j); }) }), _jsxs("div", { style: { display: "flex", gap: 12, flexWrap: "wrap", margin: "12px 0" }, children: [_jsxs("span", { style: { padding: "6px 12px", borderRadius: 6, background: "#f3f4f6", fontSize: 13 }, children: [_jsx("strong", { children: "maxEndingHere" }), " = ", s.meh] }), _jsxs("span", { style: { padding: "6px 12px", borderRadius: 6, background: "#ede9fe", fontSize: 13 }, children: [_jsx("strong", { children: "maxSoFar" }), " = ", s.msf] }), _jsx("span", { style: { padding: "6px 12px", borderRadius: 6, background: "#fef3c7", fontSize: 13, color: "#92400e" }, children: s.decision })] }), _jsx("div", { style: { fontSize: 13, lineHeight: 1.7, color: "#4b5563", minHeight: 60, margin: "8px 0" }, children: s.detail }), _jsxs("div", { style: { display: "flex", gap: 8, alignItems: "center", marginTop: 16 }, children: [_jsx("button", { onClick: () => setStep(Math.max(0, step - 1)), disabled: step === 0, style: { padding: "6px 16px", borderRadius: 6, border: "1px solid #d1d5db", background: "#fff", cursor: step === 0 ? "not-allowed" : "pointer", opacity: step === 0 ? 0.5 : 1 }, children: "← Previous" }), _jsxs("span", { style: { fontSize: 13, color: "#6b7280", minWidth: 80, textAlign: "center" }, children: ["Step ", step + 1, " / ", steps.length] }), _jsx("button", { onClick: () => setStep(Math.min(steps.length - 1, step + 1)), disabled: step === steps.length - 1, style: { padding: "6px 16px", borderRadius: 6, border: "1px solid #d1d5db", background: "#fff", cursor: step === steps.length - 1 ? "not-allowed" : "pointer", opacity: step === steps.length - 1 ? 0.5 : 1 }, children: "Next →" }), _jsx("button", { onClick: () => setStep(0), style: { marginLeft: "auto", padding: "6px 16px", borderRadius: 6, border: "1px solid #d1d5db", background: "#fff", cursor: "pointer" }, children: "Reset" })] }), _jsxs("div", { style: { marginTop: 16 }, children: [_jsx("span", { style: { fontSize: 13, color: "#6b7280" }, children: "Try different arrays:" }), _jsx("div", { style: { display: "flex", gap: 8, marginTop: 6, flexWrap: "wrap" }, children: [{ label: "[-2,1,-3,4,-1,2,1,-5,4]", arr: [-2, 1, -3, 4, -1, 2, 1, -5, 4] }, { label: "Positive heavy", arr: [5, 4, -1, 7, 8] }, { label: "All negative", arr: [-3, -2, -5, -1, -4] }, { label: "Single element", arr: [1] }, { label: "Zeros mixed", arr: [0, -3, 5, 0, -2, 3] }].map(({label, arr}) => _jsx("button", { onClick: () => loadArr(arr), style: { padding: "4px 12px", borderRadius: 6, border: "1px solid #d1d5db", background: "#fff", fontSize: 12, cursor: "pointer" }, children: label }, label)) })] })] }); }; const EdgeCaseTester = () => { const [input, setInput] = React.useState("-3, -2, -5, -1, -4"); const [result, setResult] = React.useState(null); const run = () => { try { const arr = input.split(",").map(s => parseInt(s.trim(), 10)).filter(n => !isNaN(n)); if (arr.length === 0) { setResult({ error: "Enter at least one number." }); return; } const trace = []; let meh = arr[0], msf = arr[0], subStart = 0, subEnd = 0; trace.push({ i: 0, val: arr[0], meh, msf, action: "init" }); for (let i = 1; i < arr.length; i++) { const extendVal = meh + arr[i], freshVal = arr[i]; let action; if (freshVal > extendVal) { meh = freshVal; subStart = i; subEnd = i; action = "restart"; } else { meh = extendVal; subEnd = i; action = "extend"; } if (meh > msf) msf = meh; trace.push({ i, val: arr[i], meh, msf, action }); } setResult({ answer: msf, subarray: arr.slice(subStart, subEnd + 1), range: [subStart, subEnd], trace }); } catch { setResult({ error: "Invalid input. Use comma-separated integers." }); } }; return _jsxs("div", { style: { margin: "2rem 0", padding: "1.5rem", border: "1px solid #e5e7eb", borderRadius: 12, background: "#fafafa" }, children: [_jsx("div", { style: { fontWeight: 600, marginBottom: 8 }, children: "Edge Case Tester" }), _jsxs("div", { style: { display: "flex", gap: 8, marginBottom: 12 }, children: [_jsx("input", { value: input, onChange: e => setInput(e.target.value), placeholder: "e.g. -2, 1, -3, 4, -1, 2, 1, -5, 4", style: { flex: 1, padding: "8px 12px", borderRadius: 6, border: "1px solid #d1d5db", fontSize: 14 } }), _jsx("button", { onClick: run, style: { padding: "8px 16px", borderRadius: 6, background: "#7c3aed", color: "#fff", border: "none", cursor: "pointer", fontWeight: 500 }, children: "Run" })] }), _jsx("div", { style: { display: "flex", gap: 8, flexWrap: "wrap", marginBottom: 12 }, children: [{ label: "All negative", val: "-3, -2, -5, -1, -4" }, { label: "All positive", val: "1, 2, 3, 4, 5" }, { label: "Single element", val: "42" }, { label: "Has zeros", val: "0, -3, 5, 0, -2, 3" }, { label: "Classic", val: "-2, 1, -3, 4, -1, 2, 1, -5, 4" }].map(({label, val}) => _jsx("button", { onClick: () => { setInput(val); setResult(null); }, style: { padding: "3px 10px", borderRadius: 6, border: "1px solid #d1d5db", background: "#fff", fontSize: 12, cursor: "pointer" }, children: label }, label)) }), result && !result.error && _jsxs("div", { children: [_jsxs("div", { style: { fontSize: 14, marginBottom: 8 }, children: [_jsx("strong", { children: "Answer:" }), " ", result.answer, " | ", _jsx("strong", { children: "Subarray:" }), " [", result.subarray.join(", "), "] | ", _jsx("strong", { children: "Indices:" }), " ", result.range[0], "–", result.range[1]] }), _jsx("div", { style: { overflowX: "auto" }, children: _jsxs("table", { style: { width: "100%", fontSize: 13, borderCollapse: "collapse" }, children: [_jsx("thead", { children: _jsxs("tr", { style: { borderBottom: "2px solid #e5e7eb", textAlign: "left" }, children: [_jsx("th", { style: { padding: "6px 8px" }, children: "i" }), _jsx("th", { style: { padding: "6px 8px" }, children: "nums[i]" }), _jsx("th", { style: { padding: "6px 8px" }, children: "Action" }), _jsx("th", { style: { padding: "6px 8px" }, children: "maxEndingHere" }), _jsx("th", { style: { padding: "6px 8px" }, children: "maxSoFar" })] }) }), _jsx("tbody", { children: result.trace.map(t => _jsxs("tr", { style: { borderBottom: "1px solid #f3f4f6" }, children: [_jsx("td", { style: { padding: "4px 8px" }, children: t.i }), _jsx("td", { style: { padding: "4px 8px", fontWeight: 600 }, children: t.val }), _jsx("td", { style: { padding: "4px 8px" }, children: _jsx("span", { style: { padding: "2px 8px", borderRadius: 4, fontSize: 12, background: t.action === "restart" ? "#fef3c7" : t.action === "init" ? "#f3f4f6" : "#d1fae5", color: t.action === "restart" ? "#92400e" : t.action === "init" ? "#6b7280" : "#065f46" }, children: t.action }) }), _jsx("td", { style: { padding: "4px 8px" }, children: t.meh }), _jsx("td", { style: { padding: "4px 8px", fontWeight: t.msf === result.answer ? 700 : 400, color: t.msf === result.answer ? "#7c3aed" : "inherit" }, children: t.msf })] }, t.i)) })] }) })] }), result?.error && _jsx("div", { style: { color: "#dc2626", fontSize: 13 }, children: result.error })] }); }; const EvolutionMap = () => { const [active, setActive] = React.useState(null); const nodes = [{ id: "classic", label: "Classic max subarray", x: 0, y: 0, lc: "LC 53", diff: "Medium", color: "#d1fae5" }, { id: "indices", label: "With indices", x: 1, y: 0, lc: "Template B", diff: "Medium", color: "#d1fae5" }, { id: "stock", label: "Buy/Sell stock", x: 2, y: 0, lc: "LC 121", diff: "Easy", color: "#dbeafe" }, { id: "product", label: "Max product (track min too)", x: 0, y: 1, lc: "LC 152", diff: "Medium-Hard", color: "#fef3c7" }, { id: "multi", label: "Multiple transactions", x: 2, y: 1, lc: "LC 122", diff: "Medium", color: "#fef3c7" }, { id: "circular", label: "Circular (total − min trick)", x: 0, y: 2, lc: "LC 918", diff: "Hard", color: "#fce7f3" }, { id: "disjoint", label: "Two disjoint subarrays", x: 0, y: 3, lc: "LC 1031", diff: "Hard", color: "#fce7f3" }]; const info = { classic: "Pure Kadane's. The foundation for everything else.", indices: "Same algorithm, but also track where the subarray starts and ends via tempStart.", stock: "Kadane's on the diff array, or equivalently track minPrice and compute profit at each step.", product: "Must track BOTH max and min products because negative × negative = positive.", multi: "Greedy: sum all positive diffs. Each ascending run is a transaction.", circular: "Two Kadane's passes: one for max, one for min. maxCircular = totalSum − minSubarray.", disjoint: "Prefix Kadane's + Suffix Kadane's. At each split point, combine the two bests." }; return _jsxs("div", { style: { margin: "2rem 0", padding: "1.5rem", border: "1px solid #e5e7eb", borderRadius: 12, background: "#fafafa" }, children: [_jsx("div", { style: { fontWeight: 600, marginBottom: 12 }, children: "Evolution map — click any variant" }), _jsx("div", { style: { display: "grid", gridTemplateColumns: "repeat(3, 1fr)", gap: 12 }, children: nodes.map(n => _jsxs("div", { onClick: () => setActive(active === n.id ? null : n.id), style: { gridColumn: n.x + 1, gridRow: n.y + 1, padding: "10px 14px", borderRadius: 8, border: active === n.id ? "2px solid #7c3aed" : "1px solid #d1d5db", background: n.color, cursor: "pointer", transition: "all 0.2s" }, children: [_jsx("div", { style: { fontWeight: 600, fontSize: 13 }, children: n.label }), _jsxs("div", { style: { fontSize: 11, color: "#6b7280", marginTop: 2 }, children: [n.lc, " · ", n.diff] })] }, n.id)) }), active && _jsxs("div", { style: { marginTop: 12, padding: "10px 14px", borderRadius: 8, background: "#ede9fe", fontSize: 13, lineHeight: 1.6 }, children: [_jsxs("strong", { children: [nodes.find(n => n.id === active)?.label, ":"] }), " ", info[active]] })] }); }; function _createMdxContent(props) { const _components = { a: "a", blockquote: "blockquote", code: "code", em: "em", figure: "figure", h1: "h1", h2: "h2", h3: "h3", hr: "hr", li: "li", ol: "ol", p: "p", pre: "pre", span: "span", strong: "strong", table: "table", tbody: "tbody", td: "td", th: "th", thead: "thead", tr: "tr", ul: "ul", ...props.components }; return _jsxs(_Fragment, { children: ["\n", "\n", _jsxs(_components.h1, { id: "kadanes-algorithm-maximum-subarray", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#kadanes-algorithm-maximum-subarray", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Kadane's Algorithm (Maximum Subarray)"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Tier 0 — Foundations" }), " | Prerequisites: Time & Space Complexity, Prefix Sum Techniques | Required by: Sliding Window (Tier 1), Dynamic Programming (Tier 4)"] }), "\n"] }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h2, { id: "1-intuition-first-no-jargon", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#1-intuition-first-no-jargon", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "1. Intuition First (No Jargon)"] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "The core idea:" }), " At each position, you make a binary decision: either extend the current subarray by including this element, or start a brand new subarray from this element. The decision is simple — whichever gives a larger sum. Track the global maximum across all these decisions."] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Real-world analogy:" }), " You're reviewing daily P&L for a trading desk. Each day has a profit or loss. You want to find the most profitable consecutive streak. At each day, you ask: \"Am I better off continuing my current streak (which might have had some bad days but still nets positive), or cutting my losses and starting fresh from today?\" If the accumulated streak is negative, it's dragging you down — start fresh. If it's still positive, keep riding it. That's Kadane's."] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "WHY this pattern exists:" }), " Finding the maximum sum contiguous subarray seems like it needs O(n²) to check all subarrays. Kadane's collapses this to O(n) with a key insight: you never need to consider a subarray that starts from a prefix with negative sum, because dropping that prefix always helps. This is the simplest and most elegant example of dynamic programming — a single variable carrying the optimal state forward."] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "The mental shift:" }), " You're not searching subarrays. You're making a local decision at each step: extend or restart. The globally optimal subarray emerges from these local decisions. This \"locally optimal → globally optimal\" property is what makes it work."] }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h2, { id: "2-pattern-recognition", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#2-pattern-recognition", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "2. Pattern Recognition"] }), "\n", _jsxs(_components.h3, { id: "when-to-use", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#when-to-use", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "When to use"] }), "\n", _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { children: "Signal" }), _jsx(_components.th, { children: "Example" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { children: "\"Maximum sum subarray\" (no size constraint)" }), _jsx(_components.td, { children: "Classic Kadane's" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "\"Maximum sum subarray\" (with negatives)" }), _jsx(_components.td, { children: "Sliding window breaks → Kadane's" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "\"Maximum product subarray\"" }), _jsx(_components.td, { children: "Modified Kadane's tracking min AND max" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "\"Maximum circular subarray sum\"" }), _jsx(_components.td, { children: "Kadane's + total sum trick" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "\"Best time to buy and sell stock\"" }), _jsx(_components.td, { children: "Kadane's on the diff array (daily price changes)" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Any \"contiguous subarray optimization\" where the answer can extend or restart" }), _jsx(_components.td, { children: "Kadane's family" })] })] })] }), "\n", _jsxs(_components.h3, { id: "common-keywords-in-problem-statements", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#common-keywords-in-problem-statements", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Common keywords in problem statements"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "\"maximum sum subarray\"" }), "\n", _jsx(_components.li, { children: "\"contiguous\", \"consecutive\"" }), "\n", _jsx(_components.li, { children: "\"maximum/minimum sum\"" }), "\n", _jsx(_components.li, { children: "\"best\", \"optimal\" streak/range" }), "\n", _jsx(_components.li, { children: "Problems that mention arrays with negative numbers and ask for subarray optimization" }), "\n"] }), "\n", _jsxs(_components.h3, { id: "10-second-identification-rule", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#10-second-identification-rule", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "10-Second Identification Rule"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsx(_components.p, { children: _jsx(_components.strong, { children: "Is it asking for the maximum (or minimum) sum contiguous subarray, with no constraint on size, and the array has negative numbers?" }) }), "\n", _jsx(_components.p, { children: "If YES → Kadane's. Period. O(n) time, O(1) space." }), "\n", _jsx(_components.p, { children: "If there's a size constraint (exactly k, or at most k) → Sliding Window, not Kadane's.\nIf you need the count or existence of subarrays with exact sum → Prefix Sum + HashMap.\nIf the array is all positive → The whole array is the answer (or use sliding window for a constraint)." }), "\n"] }), "\n", _jsxs(_components.h3, { id: "kadanes-vs-sliding-window-vs-prefix-sum", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#kadanes-vs-sliding-window-vs-prefix-sum", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Kadane's vs Sliding Window vs Prefix Sum"] }), "\n", _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, {}), _jsx(_components.th, { children: "Kadane's" }), _jsx(_components.th, { children: "Sliding Window" }), _jsx(_components.th, { children: "Prefix Sum + HashMap" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { children: _jsx(_components.strong, { children: "Problem" }) }), _jsx(_components.td, { children: "Max sum subarray" }), _jsx(_components.td, { children: "Optimal length subarray with constraint" }), _jsx(_components.td, { children: "Count/find subarrays with exact sum" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: _jsx(_components.strong, { children: "Negatives" }) }), _jsx(_components.td, { children: "Handles them" }), _jsx(_components.td, { children: "Breaks (sum-based)" }), _jsx(_components.td, { children: "Handles them" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: _jsx(_components.strong, { children: "Size constraint" }) }), _jsx(_components.td, { children: "None" }), _jsx(_components.td, { children: "Yes" }), _jsx(_components.td, { children: "No" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: _jsx(_components.strong, { children: "Complexity" }) }), _jsx(_components.td, { children: "O(n) time, O(1) space" }), _jsx(_components.td, { children: "O(n) time, O(1) space" }), _jsx(_components.td, { children: "O(n) time, O(n) space" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: _jsx(_components.strong, { children: "Returns" }) }), _jsx(_components.td, { children: "One optimal value" }), _jsx(_components.td, { children: "One optimal length/value" }), _jsx(_components.td, { children: "Count or existence" })] })] })] }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h2, { id: "3-core-algorithm--template", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#3-core-algorithm--template", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "3. Core Algorithm / Template"] }), "\n", _jsxs(_components.h3, { id: "template-a-classic-kadanes-maximum-subarray-sum", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#template-a-classic-kadanes-maximum-subarray-sum", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Template A: Classic Kadane's (Maximum Subarray Sum)"] }), "\n", _jsx(_components.figure, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.pre, { tabIndex: "0", "data-language": "csharp", "data-theme": "github-light", children: _jsxs(_components.code, { "data-language": "csharp", "data-theme": "github-light", children: [_jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#6A737D" }, children: "// Returns the maximum sum of any contiguous subarray" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#6A737D" }, children: "// Handles negative numbers, works in O(n) time, O(1) space" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: "public" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " MaxSubArray" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "(" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "int" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "[] " }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "nums" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ")" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: "{" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " maxEndingHere" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: "0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "]; " }), _jsx(_components.span, { style: { color: "#6A737D" }, children: "// best subarray ending at current position" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " maxSoFar" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: "0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "]; " }), _jsx(_components.span, { style: { color: "#6A737D" }, children: "// global best" })] }), "\n", _jsx(_components.span, { "data-line": "" }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " for" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " (" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " i" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: " 1" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "; i " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "<" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums.Length; i" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "++" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ")" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: " {" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#6A737D" }, children: " // Decision: extend current subarray or start fresh" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " maxEndingHere " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " Math." }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "Max" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "(nums[i], maxEndingHere " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "+" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[i]);" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " maxSoFar " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " Math." }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "Max" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "(maxSoFar, maxEndingHere);" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "" }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " return" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " maxSoFar;" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: "}" }) })] }) }) }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Mental model:" }), " At each index i:"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "maxEndingHere" }) }) }) }), " = max sum subarray that ENDS at position i"] }), "\n", _jsxs(_components.li, { children: ["Decision: ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "max(nums[i], maxEndingHere + nums[i])" }) }) }) }), " = \"start fresh\" vs \"extend\""] }), "\n", _jsxs(_components.li, { children: ["If ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "maxEndingHere" }) }) }) }), " was negative before adding ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "nums[i]" }) }) }) }), ", starting fresh is better"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "maxSoFar" }) }) }) }), " tracks the global maximum across all positions"] }), "\n"] }), "\n", "\n", _jsxs(_components.h3, { id: "interactive-step-through-kadanes-algorithm", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#interactive-step-through-kadanes-algorithm", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Interactive: Step through Kadane's algorithm"] }), "\n", _jsxs(_components.p, { children: ["Click ", _jsx(_components.strong, { children: "Next" }), " to walk through each step. Watch how ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "maxEndingHere" }) }) }) }), " decides to extend or restart at every index:"] }), "\n", _jsx(KadaneStepper, {}), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h3, { id: "template-b-kadanes-with-subarray-indices", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#template-b-kadanes-with-subarray-indices", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Template B: Kadane's with Subarray Indices"] }), "\n", _jsx(_components.figure, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.pre, { tabIndex: "0", "data-language": "csharp", "data-theme": "github-light", children: _jsxs(_components.code, { "data-language": "csharp", "data-theme": "github-light", children: [_jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#6A737D" }, children: "// Returns the maximum sum AND the start/end indices of the subarray" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: "public" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " (" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " sum" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ", " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " start" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ", " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " end" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ") " }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "MaxSubArrayWithIndices" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "(" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "int" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "[] " }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "nums" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ")" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: "{" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " maxEndingHere" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: "0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "];" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " maxSoFar" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: "0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "];" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " tempStart" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: " 0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "; " }), _jsx(_components.span, { style: { color: "#6A737D" }, children: "// potential start of current subarray" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " start" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: " 0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ", " }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "end" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: " 0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ";" })] }), "\n", _jsx(_components.span, { "data-line": "" }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " for" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " (" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " i" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: " 1" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "; i " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "<" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums.Length; i" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "++" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ")" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: " {" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " if" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " (nums[i] " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: ">" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " maxEndingHere " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "+" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[i])" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: " {" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#6A737D" }, children: " // Starting fresh — new subarray begins at i" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " maxEndingHere " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[i];" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " tempStart " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " i;" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#D73A49" }, children: " else" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: " {" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#6A737D" }, children: " // Extending — keep the current start" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " maxEndingHere " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "+=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[i];" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "" }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " if" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " (maxEndingHere " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: ">" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " maxSoFar)" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: " {" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " maxSoFar " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " maxEndingHere;" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " start " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " tempStart;" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " end " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " i;" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "" }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " return" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " (maxSoFar, start, end);" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: "}" }) })] }) }) }), "\n", _jsxs(_components.h3, { id: "template-c-maximum-product-subarray-modified-kadanes", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#template-c-maximum-product-subarray-modified-kadanes", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Template C: Maximum Product Subarray (Modified Kadane's)"] }), "\n", _jsx(_components.figure, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.pre, { tabIndex: "0", "data-language": "csharp", "data-theme": "github-light", children: _jsxs(_components.code, { "data-language": "csharp", "data-theme": "github-light", children: [_jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#6A737D" }, children: "// Maximum product subarray — track both max AND min" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#6A737D" }, children: "// because a negative × negative can become the largest positive" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: "public" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " MaxProduct" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "(" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "int" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "[] " }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "nums" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ")" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: "{" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " maxProd" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: "0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "];" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " minProd" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: "0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "]; " }), _jsx(_components.span, { style: { color: "#6A737D" }, children: "// track minimum because negative × negative = positive" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " result" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: "0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "];" })] }), "\n", _jsx(_components.span, { "data-line": "" }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " for" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " (" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " i" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: " 1" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "; i " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "<" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums.Length; i" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "++" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ")" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: " {" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#6A737D" }, children: " // If nums[i] is negative, max and min swap roles" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " if" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " (nums[i] " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "<" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: " 0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ")" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " (maxProd, minProd) " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " (minProd, maxProd);" })] }), "\n", _jsx(_components.span, { "data-line": "" }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " maxProd " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " Math." }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "Max" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "(nums[i], maxProd " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "*" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[i]);" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " minProd " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " Math." }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "Min" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "(nums[i], minProd " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "*" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[i]);" })] }), "\n", _jsx(_components.span, { "data-line": "" }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " result " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " Math." }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "Max" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "(result, maxProd);" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "" }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " return" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " result;" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: "}" }) })] }) }) }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Key insight for product variant:" }), " Negatives flip max and min. A large negative product × another negative = large positive. So you must track both the maximum AND minimum product ending at each position."] }), "\n", _jsxs(_components.h3, { id: "template-d-maximum-circular-subarray-sum", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#template-d-maximum-circular-subarray-sum", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Template D: Maximum Circular Subarray Sum"] }), "\n", _jsx(_components.figure, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.pre, { tabIndex: "0", "data-language": "csharp", "data-theme": "github-light", children: _jsxs(_components.code, { "data-language": "csharp", "data-theme": "github-light", children: [_jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#6A737D" }, children: "// Maximum subarray sum in a circular array" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#6A737D" }, children: "// Answer is either:" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#6A737D" }, children: "// (a) normal max subarray (doesn't wrap), OR" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#6A737D" }, children: "// (b) total sum - minimum subarray (wraps around — exclude the min in the middle)" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: "public" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " MaxSubarraySumCircular" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "(" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "int" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "[] " }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "nums" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ")" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: "{" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " totalSum" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: " 0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " maxEndingHere" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: "0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "], " }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "maxSoFar" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: "0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "];" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " minEndingHere" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: "0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "], " }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "minSoFar" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: "0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "];" })] }), "\n", _jsx(_components.span, { "data-line": "" }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " totalSum " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: "0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "];" })] }), "\n", _jsx(_components.span, { "data-line": "" }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " for" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " (" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " i" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: " 1" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "; i " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "<" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums.Length; i" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "++" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ")" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: " {" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " totalSum " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "+=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[i];" })] }), "\n", _jsx(_components.span, { "data-line": "" }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#6A737D" }, children: " // Standard Kadane's for max" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " maxEndingHere " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " Math." }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "Max" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "(nums[i], maxEndingHere " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "+" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[i]);" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " maxSoFar " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " Math." }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "Max" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "(maxSoFar, maxEndingHere);" })] }), "\n", _jsx(_components.span, { "data-line": "" }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#6A737D" }, children: " // Kadane's for min (inverted)" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " minEndingHere " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " Math." }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "Min" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "(nums[i], minEndingHere " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "+" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " nums[i]);" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " minSoFar " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " Math." }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "Min" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "(minSoFar, minEndingHere);" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: " }" }) }), "\n", _jsx(_components.span, { "data-line": "" }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#6A737D" }, children: " // Edge case: all elements negative → minSoFar = totalSum → circular sum = 0 (invalid)" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " if" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " (maxSoFar " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "<" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: " 0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ") " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "return" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " maxSoFar;" })] }), "\n", _jsx(_components.span, { "data-line": "" }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " return" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " Math." }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "Max" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "(maxSoFar, totalSum " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "-" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " minSoFar);" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: "}" }) })] }) }) }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Why the circular trick works:" }), " A wrapping subarray is everything EXCEPT a non-wrapping subarray in the middle. So max circular sum = totalSum - min non-wrapping subarray. Take the better of wrapping and non-wrapping."] }), "\n", _jsxs(_components.h3, { id: "the-dp-perspective-what-kadanes-really-is", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#the-dp-perspective-what-kadanes-really-is", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "The DP perspective (what Kadane's really is)"] }), "\n", _jsx(_components.figure, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.pre, { tabIndex: "0", "data-language": "plaintext", "data-theme": "github-light", children: _jsxs(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: [_jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "Define: dp[i] = maximum sum of subarray ending at index i" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, {}) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "Recurrence:" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " dp[i] = max(nums[i], dp[i-1] + nums[i])" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, {}) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " Translation: either start fresh at i, or extend from i-1" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, {}) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "Answer: max(dp[0], dp[1], ..., dp[n-1])" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, {}) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "Space optimization: dp[i] only depends on dp[i-1]" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " → Replace array with single variable: maxEndingHere" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, {}) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "This IS Kadane's algorithm. It's 1D DP with O(1) space." }) })] }) }) }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h2, { id: "4-complexity-deep-dive", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#4-complexity-deep-dive", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "4. Complexity Deep Dive"] }), "\n", _jsxs(_components.h3, { id: "time-complexity", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#time-complexity", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Time Complexity"] }), "\n", _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { children: "Variant" }), _jsx(_components.th, { children: "Time" }), _jsx(_components.th, { children: "Why" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Classic Kadane's" }), _jsx(_components.td, { children: "O(n)" }), _jsx(_components.td, { children: "Single pass, O(1) work per element" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "With indices" }), _jsx(_components.td, { children: "O(n)" }), _jsx(_components.td, { children: "Same pass, extra bookkeeping" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Maximum product" }), _jsx(_components.td, { children: "O(n)" }), _jsx(_components.td, { children: "Same pass, two extra variables" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Circular" }), _jsx(_components.td, { children: "O(n)" }), _jsx(_components.td, { children: "Two Kadane's passes (or one combined)" })] })] })] }), "\n", _jsxs(_components.h3, { id: "space-complexity", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#space-complexity", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Space Complexity"] }), "\n", _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { children: "Variant" }), _jsx(_components.th, { children: "Space" }), _jsx(_components.th, { children: "Notes" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { children: "All variants" }), _jsx(_components.td, { children: "O(1)" }), _jsx(_components.td, { children: "Only tracking a few variables" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "DP formulation before optimization" }), _jsx(_components.td, { children: "O(n)" }), _jsx(_components.td, { children: "The dp array" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "After space optimization" }), _jsx(_components.td, { children: "O(1)" }), _jsx(_components.td, { children: "dp[i] only needs dp[i-1]" })] })] })] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "This is the gold standard:" }), " O(n) time, O(1) space, for a problem that appears to need O(n²)."] }), "\n", _jsxs(_components.h3, { id: "historical-context-and-trade-offs", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#historical-context-and-trade-offs", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Historical context and trade-offs"] }), "\n", _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { children: "Approach" }), _jsx(_components.th, { children: "Time" }), _jsx(_components.th, { children: "Space" }), _jsx(_components.th, { children: "Notes" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Brute force (all subarrays)" }), _jsx(_components.td, { children: "O(n²) or O(n³)" }), _jsx(_components.td, { children: "O(1)" }), _jsx(_components.td, { children: "Check all subarrays" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Prefix sum optimization" }), _jsx(_components.td, { children: "O(n²)" }), _jsx(_components.td, { children: "O(n)" }), _jsx(_components.td, { children: "Range sums in O(1) but still enumerate" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Divide and conquer" }), _jsx(_components.td, { children: "O(n log n)" }), _jsx(_components.td, { children: "O(log n)" }), _jsx(_components.td, { children: "Split, solve halves, combine crossing" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Kadane's" }), _jsx(_components.td, { children: "O(n)" }), _jsx(_components.td, { children: "O(1)" }), _jsx(_components.td, { children: "Optimal — can't do better (must read input)" })] })] })] }), "\n", _jsxs(_components.h3, { id: "when-this-approach-breaks", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#when-this-approach-breaks", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "When this approach breaks"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Size constraint:" }), " \"Max sum subarray of exactly size k\" → Kadane's doesn't restrict size. Use sliding window."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Exact target sum:" }), " \"Subarray with sum exactly k\" → Kadane's finds the max, not a specific target. Use prefix sum + HashMap."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Multiple disjoint subarrays:" }), " \"Pick two non-overlapping subarrays maximizing total sum\" → Kadane's finds one. Need prefix/suffix Kadane's arrays."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "All positives:" }), " The answer is trivially the entire array. Kadane's still works but it's overkill."] }), "\n"] }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h2, { id: "5-edge-cases--pitfalls", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#5-edge-cases--pitfalls", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "5. Edge Cases & Pitfalls"] }), "\n", _jsxs(_components.h3, { id: "common-senior-level-mistakes", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#common-senior-level-mistakes", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Common senior-level mistakes"] }), "\n", _jsxs(_components.ol, { children: ["\n", _jsxs(_components.li, { children: ["\n", _jsxs(_components.p, { children: [_jsxs(_components.strong, { children: ["Initializing ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "maxEndingHere = 0" }) }) }) }), " instead of ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "nums[0]" }) }) }) }), "."] }), " If all elements are negative, ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "maxEndingHere = 0" }) }) }) }), " gives the wrong answer (0, from an empty subarray). The problem asks for the maximum of NON-EMPTY subarrays. Initialize with ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "nums[0]" }) }) }) }), " and start the loop at index 1."] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["\n", _jsxs(_components.p, { children: [_jsxs(_components.strong, { children: ["Initializing ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "maxSoFar = 0" }) }) }) }), "."] }), " Same bug. If all elements are negative, ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "maxSoFar = 0" }) }) }) }), " is wrong. Initialize with ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "nums[0]" }) }) }) }), "."] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Confusing Kadane's with sliding window." }), " \"Maximum sum subarray of size k\" is NOT Kadane's. Kadane's has no size constraint. The sliding window template handles fixed-size windows."] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Forgetting the edge case in circular variant." }), " When ALL elements are negative, ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "totalSum - minSoFar = 0" }) }) }) }), " (the \"wrapping subarray\" is empty). But empty subarrays aren't allowed. The check ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "if (maxSoFar < 0) return maxSoFar;" }) }) }) }), " handles this."] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Not tracking both max and min for product variant." }), " The product version MUST track the minimum product because ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "negative × negative = positive" }) }) }) }), ". Forgetting the min variable makes the algorithm fail on inputs like ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "[-2, 3, -4]" }) }) }) }), " (answer: 24 = -2 × 3 × -4)."] }), "\n"] }), "\n"] }), "\n", "\n", _jsxs(_components.h3, { id: "try-it-yourself-test-edge-cases", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#try-it-yourself-test-edge-cases", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Try it yourself: test edge cases"] }), "\n", _jsx(_components.p, { children: "Enter any array to see the full execution trace. Try the \"All negative\" preset to see why initializing to 0 is wrong:" }), "\n", _jsx(EdgeCaseTester, {}), "\n", _jsxs(_components.h3, { id: "boundary-conditions", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#boundary-conditions", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Boundary conditions"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "Single element → return that element" }), "\n", _jsx(_components.li, { children: "All negative → return the largest (least negative) element" }), "\n", _jsx(_components.li, { children: "All positive → return the sum of the entire array" }), "\n", _jsx(_components.li, { children: "Contains zero → for product variant, zeros reset both max and min to 0" }), "\n", _jsx(_components.li, { children: "Very large values → check for integer overflow in sum/product" }), "\n"] }), "\n", _jsxs(_components.h3, { id: "debugging-heuristics", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#debugging-heuristics", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Debugging heuristics"] }), "\n", _jsxs(_components.ol, { children: ["\n", _jsxs(_components.li, { children: ["Print ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "maxEndingHere" }) }) }) }), " and ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "maxSoFar" }) }) }) }), " at each step"] }), "\n", _jsxs(_components.li, { children: ["The \"restart\" decision: ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "maxEndingHere" }) }) }) }), " should jump to ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "nums[i]" }) }) }) }), " when ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "maxEndingHere + nums[i] < nums[i]" }) }) }) }), ", i.e., when ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "maxEndingHere < 0" }) }) }) })] }), "\n", _jsx(_components.li, { children: "For product: check that negative inputs cause proper max/min swaps" }), "\n"] }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h2, { id: "6-variations-pattern-stretching", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#6-variations-pattern-stretching", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "6. Variations (Pattern Stretching)"] }), "\n", _jsxs(_components.h3, { id: "easy-classic-maximum-subarray-sum", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#easy-classic-maximum-subarray-sum", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Easy: Classic maximum subarray sum"] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Maximum Subarray (LC 53)." }), " Pure Template A. Single pass, track running maximum."] }), "\n", _jsxs(_components.h3, { id: "medium-maximum-subarray-with-indices", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#medium-maximum-subarray-with-indices", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Medium: Maximum subarray with indices"] }), "\n", _jsx(_components.p, { children: "Return the actual subarray, not just the sum. Template B — track start/end indices alongside the max." }), "\n", _jsxs(_components.h3, { id: "medium-best-time-to-buy-and-sell-stock", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#medium-best-time-to-buy-and-sell-stock", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Medium: Best time to buy and sell stock"] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Best Time to Buy and Sell Stock (LC 121)." }), " Equivalent to Kadane's on the ", _jsx(_components.em, { children: "diff array" }), " (daily price changes). Or simpler: track the minimum price seen so far, and the maximum profit from selling at today's price."] }), "\n", _jsx(_components.figure, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.pre, { tabIndex: "0", "data-language": "csharp", "data-theme": "github-light", children: _jsxs(_components.code, { "data-language": "csharp", "data-theme": "github-light", children: [_jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: "public" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " MaxProfit" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "(" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "int" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "[] " }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "prices" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ")" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: "{" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " minPrice" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " prices[" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: "0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "];" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " maxProfit" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: " 0" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ";" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " for" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " (" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "int" }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: " i" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: " =" }), _jsx(_components.span, { style: { color: "#005CC5" }, children: " 1" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "; i " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "<" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " prices.Length; i" }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "++" }), _jsx(_components.span, { style: { color: "#24292E" }, children: ")" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: " {" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " maxProfit " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " Math." }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "Max" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "(maxProfit, prices[i] " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "-" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " minPrice);" })] }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#24292E" }, children: " minPrice " }), _jsx(_components.span, { style: { color: "#D73A49" }, children: "=" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " Math." }), _jsx(_components.span, { style: { color: "#6F42C1" }, children: "Min" }), _jsx(_components.span, { style: { color: "#24292E" }, children: "(minPrice, prices[i]);" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: " }" }) }), "\n", _jsxs(_components.span, { "data-line": "", children: [_jsx(_components.span, { style: { color: "#D73A49" }, children: " return" }), _jsx(_components.span, { style: { color: "#24292E" }, children: " maxProfit;" })] }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { style: { color: "#24292E" }, children: "}" }) })] }) }) }), "\n", _jsxs(_components.h3, { id: "medium-hard-maximum-product-subarray", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#medium-hard-maximum-product-subarray", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Medium-Hard: Maximum product subarray"] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Maximum Product Subarray (LC 152)." }), " Template C. Track both max and min products because negatives flip the ordering. Zeros reset both."] }), "\n", _jsxs(_components.h3, { id: "hard-maximum-circular-subarray-sum", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#hard-maximum-circular-subarray-sum", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Hard: Maximum circular subarray sum"] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Maximum Sum Circular Subarray (LC 918)." }), " Template D. The non-wrapping case is standard Kadane's. The wrapping case: max circular = totalSum - minSubarraySum. Take the better of both. Handle all-negatives edge case."] }), "\n", _jsxs(_components.h3, { id: "hard-maximum-sum-of-two-non-overlapping-subarrays", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#hard-maximum-sum-of-two-non-overlapping-subarrays", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Hard: Maximum sum of two non-overlapping subarrays"] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Maximum Sum of Two Non-Overlapping Subarrays (LC 1031)." }), " Precompute prefix Kadane's (best subarray in prefix [0..i]) and suffix Kadane's (best subarray in suffix [i..n-1]). For each split point, combine."] }), "\n", "\n", _jsxs(_components.h3, { id: "evolution-map", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#evolution-map", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Evolution map"] }), "\n", _jsx(_components.figure, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.pre, { tabIndex: "0", "data-language": "plaintext", "data-theme": "github-light", children: _jsxs(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: [_jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "Classic max subarray → With indices → Buy/Sell stock (min tracking variant)" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " ↓ ↓" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " Max product (track min too) Multiple transactions (greedy/DP)" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " ↓" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " Circular (total - min trick)" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " ↓" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " Two disjoint subarrays (prefix + suffix Kadane's)" }) })] }) }) }), "\n", _jsx(EvolutionMap, {}), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h2, { id: "7-interview-level-problems", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#7-interview-level-problems", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "7. Interview-Level Problems"] }), "\n", _jsxs(_components.h3, { id: "problem-1-medium-maximum-subarray-lc-53", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#problem-1-medium-maximum-subarray-lc-53", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Problem 1 (Medium): Maximum Subarray (LC 53)"] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Summary:" }), " Given an integer array ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "nums" }) }) }) }), ", find the subarray with the largest sum and return its sum."] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Expected approach:" }), " Kadane's algorithm. At each position, decide: extend current subarray or start fresh. Track global maximum."] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Key insight:" }), " The decision ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "maxEndingHere = max(nums[i], maxEndingHere + nums[i])" }) }) }) }), " is equivalent to: \"if the best subarray ending at i-1 had negative sum, drop it and start over.\" This is the core of Kadane's. In interviews, explicitly state this as a DP formulation: \"dp[i] = max sum subarray ending at i. Recurrence: dp[i] = max(nums[i], dp[i-1] + nums[i]). Space-optimized to O(1).\""] }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h3, { id: "problem-2-medium-hard-maximum-product-subarray-lc-152", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#problem-2-medium-hard-maximum-product-subarray-lc-152", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Problem 2 (Medium-Hard): Maximum Product Subarray (LC 152)"] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Summary:" }), " Given an integer array ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "nums" }) }) }) }), ", find the contiguous subarray that has the largest product, and return the product."] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Expected approach:" }), " Modified Kadane's tracking both maximum and minimum product at each position. Before updating, check if ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "nums[i]" }) }) }) }), " is negative — if so, swap max and min (because multiplying a negative by the min gives the max)."] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Key insight:" }), " The product variant breaks the standard Kadane's invariant because negatives flip signs. The fix — tracking both max AND min — is a pattern that appears in any \"optimize over a function with sign flips.\" Zeros reset everything to 0 (or 1, depending on how you frame it). Interviewers specifically test whether you remember to track the minimum."] }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h3, { id: "problem-3-hard-maximum-sum-circular-subarray-lc-918", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#problem-3-hard-maximum-sum-circular-subarray-lc-918", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Problem 3 (Hard): Maximum Sum Circular Subarray (LC 918)"] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Summary:" }), " Given a circular integer array ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "nums" }) }) }) }), ", find the maximum possible sum of a non-empty subarray."] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Expected approach:" }), " Run standard Kadane's for max subarray (non-wrapping case). Run inverted Kadane's for min subarray (wrapping case: max_circular = totalSum - minSubarray). Answer is ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "max(maxKadane, totalSum - minKadane)" }) }) }) }), ". Special case: if all elements are negative, the circular case gives 0 (empty subarray), which is invalid → return maxKadane."] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Key insight:" }), " The circular decomposition — a wrapping subarray's complement is a non-wrapping subarray — is the non-obvious insight. Once you see it, the problem reduces to two Kadane's runs. The all-negatives edge case is the trap: ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "totalSum - minSoFar = 0" }) }) }) }), ", but empty subarrays aren't allowed. Interviewers test exactly this case."] }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h2, { id: "8-staff-level-thinking", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#8-staff-level-thinking", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "8. Staff-Level Thinking"] }), "\n", _jsxs(_components.h3, { id: "trade-offs-between-approaches", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#trade-offs-between-approaches", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Trade-offs between approaches"] }), "\n", _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { children: "Approach" }), _jsx(_components.th, { children: "When to use" }), _jsx(_components.th, { children: "Why not always" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Kadane's" }), _jsx(_components.td, { children: "Max/min sum subarray, no constraints" }), _jsx(_components.td, { children: "Only finds one optimal value; can't count, can't target specific sum" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Prefix Sum + HashMap" }), _jsx(_components.td, { children: "Count subarrays with exact sum k" }), _jsx(_components.td, { children: "O(n) space; more complex to implement" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Sliding Window" }), _jsx(_components.td, { children: "Min/max length with sum constraint, positives only" }), _jsx(_components.td, { children: "Breaks with negatives" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Divide & Conquer" }), _jsx(_components.td, { children: "Educational / follow-up question" }), _jsx(_components.td, { children: "O(n log n) — strictly worse than Kadane's" })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: "Brute Force" }), _jsx(_components.td, { children: "n ≤ 100, as a verification tool" }), _jsx(_components.td, { children: "O(n²) or O(n³) — doesn't scale" })] })] })] }), "\n", _jsxs(_components.h3, { id: "scalability-considerations", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#scalability-considerations", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "Scalability considerations"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "Kadane's is the theoretical lower bound for this problem — O(n) time, O(1) space. You can't do better because you must read every element at least once." }), "\n", _jsx(_components.li, { children: "In streaming contexts, Kadane's works on unbounded streams: process each element as it arrives, never needing to revisit. This makes it suitable for real-time analytics on data pipelines." }), "\n", _jsx(_components.li, { children: "For the \"sliding window maximum\" variant (max subarray of exactly size k), Kadane's doesn't apply — but the sliding window version is also O(n). Different tool, same complexity." }), "\n"] }), "\n", _jsxs(_components.h3, { id: "when-not-to-use-kadanes", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#when-not-to-use-kadanes", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "When NOT to use Kadane's"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "You need all subarrays with a property, not just the best one." }), " Kadane's finds THE max. For counting or enumerating, you need prefix sum or DP."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "There's a size constraint." }), " Kadane's doesn't restrict subarray size. Fixed-size → sliding window. Variable size with constraint → sliding window or binary search."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "You need the second-best, or top-K subarrays." }), " Kadane's only tracks the global optimum. Extending to top-K requires fundamentally different approaches."] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "Multi-dimensional arrays." }), " Kadane's is 1D. For 2D max subarray sum, you fix two row boundaries (O(n)) and apply Kadane's to column sums → O(n²m) or O(nm²)."] }), "\n"] }), "\n", _jsxs(_components.h3, { id: "how-to-explain-this-in-interviews", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#how-to-explain-this-in-interviews", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "How to explain this in interviews"] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Opening (10 seconds):" }), " \"This is the maximum subarray problem — solved optimally by Kadane's algorithm. O(n) time, O(1) space.\""] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "DP framing (15 seconds):" }), " \"I'll think of it as DP where ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "dp[i]" }) }) }) }), " is the max sum subarray ending at index i. The recurrence is ", _jsx(_components.span, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "dp[i] = max(nums[i], dp[i-1] + nums[i])" }) }) }) }), ". Since dp[i] only depends on dp[i-1], I can space-optimize to a single variable.\""] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "Decision explanation (10 seconds):" }), " \"At each position, I either extend the current subarray or start a new one. I extend if the running sum is non-negative — it's worth carrying forward. I restart if the running sum is negative — it would drag down anything I attach to it.\""] }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h2, { id: "9-real-world-mapping", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#9-real-world-mapping", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "9. Real-World Mapping"] }), "\n", _jsxs(_components.table, { children: [_jsx(_components.thead, { children: _jsxs(_components.tr, { children: [_jsx(_components.th, { children: "Production scenario" }), _jsx(_components.th, { children: "Kadane's analog" })] }) }), _jsxs(_components.tbody, { children: [_jsxs(_components.tr, { children: [_jsx(_components.td, { children: _jsx(_components.strong, { children: "Trading P&L analysis" }) }), _jsx(_components.td, { children: "Maximum profit streak = max subarray sum on daily P&L. Used in quantitative finance for strategy evaluation." })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: _jsx(_components.strong, { children: "User engagement" }) }), _jsx(_components.td, { children: "Longest \"hot streak\" of positive session deltas. If engagement dips, start counting from the next positive day." })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: _jsx(_components.strong, { children: "Network throughput" }) }), _jsx(_components.td, { children: "Find the time window with maximum data transferred. Kadane's on throughput samples with overhead (negative) periods." })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: _jsx(_components.strong, { children: "Load testing analysis" }) }), _jsx(_components.td, { children: "Find the burst window where the system handled maximum aggregate load. Each sample = requests processed - requests dropped." })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: _jsx(_components.strong, { children: "eSports tournament scoring" }) }), _jsx(_components.td, { children: "Maximum scoring streak for a player across rounds (some rounds may have negative point swings)." })] }), _jsxs(_components.tr, { children: [_jsx(_components.td, { children: _jsx(_components.strong, { children: "Marketing campaign ROI" }) }), _jsx(_components.td, { children: "Find the best consecutive period of campaign performance. Daily ROI can be negative; Kadane's finds the best run." })] })] })] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "System design relevance:" }), " Kadane's itself rarely appears directly in system design. But the PRINCIPLE — \"maintain a running optimal state, make local decisions that compose into a global optimum\" — is the foundation of greedy algorithms, which appear everywhere in scheduling, resource allocation, and optimization. Understanding Kadane's as the simplest DP → greedy bridge is the deeper takeaway."] }), "\n", _jsx(_components.hr, {}), "\n", _jsxs(_components.h2, { id: "10-10-second-recall-cheat-sheet", children: [_jsx(_components.a, { className: "heading-anchor", "aria-hidden": "true", tabIndex: "-1", href: "#10-10-second-recall-cheat-sheet", children: _jsx(_components.span, { className: "heading-anchor-symbol", children: "#" }) }), "10. 10-Second Recall Cheat Sheet"] }), "\n", _jsx(_components.figure, { "data-rehype-pretty-code-figure": "", children: _jsx(_components.pre, { tabIndex: "0", "data-language": "plaintext", "data-theme": "github-light", children: _jsxs(_components.code, { "data-language": "plaintext", "data-theme": "github-light", children: [_jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "CORE ALGORITHM:" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " maxEndingHere = max(nums[i], maxEndingHere + nums[i])" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " maxSoFar = max(maxSoFar, maxEndingHere)" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " Translation: extend or restart, track global best" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, {}) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "INITIALIZATION (CRITICAL):" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " maxEndingHere = nums[0] (NOT 0)" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " maxSoFar = nums[0] (NOT 0)" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " Loop from i = 1 (NOT i = 0)" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, {}) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "VARIANTS:" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " Max sum subarray → Classic Kadane's" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " Max product subarray → Track BOTH max AND min (negatives flip)" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " Circular max subarray → max(Kadane_max, totalSum - Kadane_min)" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " Buy/Sell stock → Track minPrice, compute maxProfit at each step" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " Two non-overlapping → Prefix Kadane's + Suffix Kadane's" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, {}) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "KADANE'S vs SLIDING WINDOW:" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " No size constraint + negatives → Kadane's" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " Size constraint (fixed k) → Sliding Window" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " Length optimization + positives → Sliding Window" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, {}) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "DP FORMULATION:" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " dp[i] = max(nums[i], dp[i-1] + nums[i])" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " answer = max(dp[0..n-1])" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " Space: dp[i] only needs dp[i-1] → O(1)" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, {}) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: "PITFALLS:" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " - Init maxSoFar = 0 → wrong when all negative" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " - Confusing with sliding window (Kadane's has NO size constraint)" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " - Product variant: must track min product too" }) }), "\n", _jsx(_components.span, { "data-line": "", children: _jsx(_components.span, { children: " - Circular variant: all negatives → totalSum - minSoFar = 0 → return maxSoFar instead" }) })] }) }) }), "\n", _jsx(_components.hr, {}), "\n", _jsx(_components.p, { children: _jsx(_components.em, { children: "Cross-references: Prefix Sum (Tier 0) — alternative for \"sum = k\" problems; O(n) space vs Kadane's O(1). Sliding Window (Tier 1) — handles size constraints that Kadane's can't. Dynamic Programming (Tier 4) — Kadane's IS 1D DP space-optimized; the \"extend or restart\" recurrence is the simplest DP pattern. Greedy (Tier 3) — Kadane's is a greedy-flavored DP; the local decision is globally optimal." }) })] }); } function MDXContent(props = {}) { const {wrapper: MDXLayout} = props.components || ({}); return MDXLayout ? _jsx(MDXLayout, { ...props, children: _jsx(_createMdxContent, { ...props }) }) : _createMdxContent(props); } return { metadata, KadaneStepper, EdgeCaseTester, EvolutionMap, default: MDXContent };