[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6,"_7":8},"actionData","errors","root",{"_26":27,"_28":29,"_30":12,"_31":12,"_32":12,"_33":12,"_34":12,"_35":12,"_36":37},"routes/canvas.shared.$sharedTextdocId",{"_9":10,"_11":12},"sharedTextdoc",{"_13":14,"_15":-7,"_16":17,"_18":19,"_20":21,"_22":23,"_24":12,"_25":12},"isAuthenticated",false,"sharedTextdocId","68992986875481918d9d89d0d005f844","versionInt","title","Maximal Square – Interactive Web App","type","code/react","content","import React, { useEffect, useMemo, useRef, useState } from \"react\";\n\n// Maximal Square — DP Visual Stepper (Zero-dependency version)\n// dp[r][c] = side length of the largest all‑1s square whose bottom-right corner is (r,c)\n// Recurrence: if matrix[r][c]==1 → dp = 1 + min(up, left, diag); else 0\n// Final answer: (max dp)^2\n\nexport default function MaximalSquareApp() {\n const [rows, setRows] = useState(8);\n const [cols, setCols] = useState(12);\n const [density, setDensity] = useState(0.6); // probability of 1 when randomizing\n const [speed, setSpeed] = useState(500);\n const [index, setIndex] = useState(0);\n const [playing, setPlaying] = useState(false);\n const [showContrib, setShowContrib] = useState(true);\n const [matrix, setMatrix] = useState(() => makeBinary(8, 12, 0.6));\n\n const { steps, codeLines } = useMemo(() => buildSteps(matrix), [matrix]);\n const timer = useRef(null);\n\n useEffect(() => {\n // whenever size/density changes, regenerate and reset safely\n const next = makeBinary(rows, cols, density);\n setMatrix(next);\n setIndex(0);\n stop();\n }, [rows, cols, density]);\n\n useEffect(() => {\n if (!playing) return;\n timer.current = setInterval(() => {\n setIndex((i) => {\n if (i < steps.length - 1) return i + 1;\n setPlaying(false);\n return i;\n });\n }, Math.max(120, speed));\n return () => stop();\n }, [playing, speed, steps.length]);\n\n function stop(){ if (timer.current) { clearInterval(timer.current); timer.current = null; } }\n\n const step = steps[index] || steps[0];\n const canPrev = index > 0;\n const canNext = index < steps.length - 1;\n\n return (\n

Maximal Square — DP Visual Stepper

dp[r][c] = side length of the largest all‑1s square ending at (r,c). If matrix[r][c]==1 → dp = 1 + min(up, left, diag); else 0. Final area = (max dp)².

\n \n \n \n Density\n setDensity(Number(e.target.value))} />\n {density.toFixed(2)}\n \n \n \n setShowContrib(e.target.checked)} />\n Show contributors\n \n

\n\n

\n {/* Code panel */}\n \n

Code

\n{codeLines.map((l, i) => (\n  \n    \n      {i + 1}\n      {l.text}\n    \n  
\n))}\n

\n\n {/* DP meaning box */}\n

What does dp[r][c] mean?

It’s the side length of the largest all‑1s square whose bottom‑right corner is (r,c). If dp[r][c] = 4, there exists a 4×4 block of 1s ending at (r,c).

\n {step.focus ? (\n step.matrixAtFocus === 0 ? (\n

Cell (r={step.focus[0]}, c={step.focus[1]}) is 0 → dp = 0 (no square can end here).

\n ) : step.contribFrom ? (\n

Since matrix[r][c]=1, we take the smallest of the neighbor squares (up, left, diag) and add 1: dp = 1 + min(up, left, diag) = {step.dp[step.focus[0]][step.focus[1]]}.

\n ) : (\n

Base case (first row/col): dp = matrix (0 or 1).

\n )\n ) : (\n

Final answer: (max dp)² = {(step.bestSide || 0) ** 2}

\n )}\n\n

\n Why **min**? A square at (r,c) can only be as large as the smallest supporting neighbor (up/left/diag). That smallest side limits the square you can extend by +1 at (r,c).\n

\n\n {/* Controls */}\n

\n \n {!playing ? (\n \n ) : (\n \n )}\n \n \n

Step {index + 1} / {steps.length}

\n \n\n {/* Visuals */}\n \n

Visual

\n\n {/* Two synchronized grids */}\n

Matrix (Input 0/1)

\n {\n const copy = matrix.map(row=>row.slice());\n copy[r][c] = copy[r][c] ? 0 : 1;\n setMatrix(copy);\n setIndex(0);\n setPlaying(false);\n }}\n />\n

DP (Side length)

\n \n

\n Legend: green = dp written; arrows ↑ ← ↖ show contributors; bold green box = best square.\n

\n \n

\n );\n}\n\nfunction Card({ children, className = \"\" }) {\n return

{children}

;\n}\n\nfunction LabeledNumber({ label, value, setValue, min=1, max=20 }){\n return (\n \n {label}\n setValue(Math.max(min, Math.min(max, Number(e.target.value) || min)))} />\n \n );\n}\n\n// ===== Grids =====\nfunction MatrixGrid({ matrix, focus, onToggle }){\n const cols = matrix[0]?.length || 0;\n return (\n

\n {matrix.map((row, r) => row.map((bit, c) => {\n const isFocus = !!(focus && focus[0] === r && focus[1] === c);\n return (\n

onToggle(r,c)}\n className={\"relative h-12 min-w-[2.75rem] border border-slate-300 flex items-center justify-center cursor-pointer select-none \" +\n (bit ? \"bg-white\" : \"bg-slate-100\") + (isFocus ? \" ring-2 ring-emerald-500\" : \"\")}\n title={`matrix[${r}][${c}]=${bit}`}\n >\n {bit}\n

\n );\n }))}\n

\n );\n}\n\nfunction DPGrid({ values, focus, contribFrom, focusSquareSide, bestSquare }){\n const cols = values[0]?.length || 0;\n const cell = 48; // px square cell for overlay math\n\n return (\n

\n {values.map((row, r) => row.map((v, c) => {\n const isFocus = !!(focus && focus[0] === r && focus[1] === c);\n const showUp = contribFrom && contribFrom.up && isFocus;\n const showLeft = contribFrom && contribFrom.left && isFocus;\n const showDiag = contribFrom && contribFrom.diag && isFocus;\n return (\n

\n {v || ''}\n {showUp &&

↑

}\n {showLeft &&

←

}\n {showDiag &&

↖

}\n

\n );\n }))}\n\n {/* Focus overlay: shade the dp square ending at (r,c) */}\n {focus && focusSquareSide > 0 && (\n

\n )}\n\n {/* Best overall square overlay */}\n {bestSquare && bestSquare.side > 0 && (\n

\n )}\n

\n );\n}\n\n// ===== Build steps =====\nfunction buildSteps(matrix){\n const m = matrix.length, n = matrix[0].length;\n const L_INIT = \"L1\", L_BASEC = \"L2\", L_BASER = \"L3\", L_BODY = \"L4\", L_ANSWER = \"L5\";\n\n const steps = [];\n const dp = Array.from({ length: m }, () => Array(n).fill(0));\n let best = 0;\n let bestSquare = null; // {top,left,side}\n const snap = (line, title, note, focus=null, contribFrom=null, matrixAtFocus=null) => {\n steps.push({ line, title, note, dp: dp.map(r=>r.slice()), focus, contribFrom, bestSide: best, bestSquare, matrixAtFocus });\n };\n\n // Init\n snap(L_INIT, \"Initialize DP table\", `Create a ${m}×${n} table of 0s.`);\n\n // left col\n for (let r=0; r best) { best = dp[r][0]; bestSquare = best ? { top: r - best + 1, left: 0, side: best } : null; }\n snap(L_BASEC, \"First column base\", `dp[${r}][0] = matrix[${r}][0] = ${matrix[r][0]}`,[r,0], null, matrix[r][0]);\n }\n\n // top row\n for (let c=0; c best) { best = dp[0][c]; bestSquare = best ? { top: 0, left: c - best + 1, side: best } : null; }\n snap(L_BASER, \"Top row base\", `dp[0][${c}] = matrix[0][${c}] = ${matrix[0][c]}`,[0,c], null, matrix[0][c]);\n }\n\n // inner\n for (let r=1; r best) {\n best = dp[r][c];\n bestSquare = { top: r - best + 1, left: c - best + 1, side: best };\n }\n snap(L_BODY, \"Recurrence\", `dp[${r}][${c}] = 1 + min(${up}, ${left}, ${diag}) = ${dp[r][c]}`,[r,c], { up:[r-1,c], left:[r,c-1], diag:[r-1,c-1] }, 1);\n }\n }\n\n // answer\n snap(L_ANSWER, \"Return answer\", `Answer area = best^2 = ${best*best}`);\n\n const codeLines = [\n { id: L_INIT, text: \"dp = [[0 for _ in range(n)] for _ in range(m)]\" },\n { id: L_BASEC, text: \"for r in 0..m-1: dp[r][0] = matrix[r][0]; update best\" },\n { id: L_BASER, text: \"for c in 0..n-1: dp[0][c] = matrix[0][c]; update best\" },\n { id: L_BODY, text: \"if matrix[r][c]==0: dp=0 else dp=1+min(up,left,diag); update best/bestSquare\" },\n { id: L_ANSWER, text: \"return best*best\" },\n ];\n\n return { steps, codeLines };\n}\n\n// ===== Utils =====\nfunction makeBinary(r, c, density){\n return Array.from({length:r}, ()=> Array.from({length:c}, ()=> Math.random() < density ? 1 : 0));\n}\n\n// Tailwind-lite button styling injection\nif (typeof document !== 'undefined'){\n const style = document.createElement('style');\n style.innerHTML = `.btn{display:inline-flex;align-items:center;gap:.5rem;border-radius:1rem;border:1px solid rgb(226,232,240);padding:.5rem .75rem;background:white;box-shadow:0 1px 0 rgba(15,23,42,0.04);} .btn:disabled{opacity:.5;cursor:not-allowed}`;\n document.head.appendChild(style);\n}\n","access","public","isModerationBlocked","isAnonifyApiKeyDetected","dd",{"_38":39,"_40":41},"disablePrefetch",true,"shouldPrefetchAccount","shouldPrefetchUser","shouldPrefetchSystemHints","promoteCss","disableSSR","stripModulepreloadImports","statsigGateEvaluationsPromise",["P",37],"traceId","10061056058186848892","traceTime",1777661621493]