Let $A$ be an $n\times n$ random matrix whose entries are i.i.d. with mean $0$ and variance $1$. We present a deterministic polynomial time algorithm which, with probability at least $1-2\exp(-Ω(εn))$ in the choice of $A$, finds an $εn \times εn$ sub-matrix such that zeroing it out results in $\widetilde{A}$ with \[\|\widetilde{A}\| = O\left(\sqrt{n/ε}\right).\] Our result is optimal up to a constant factor and improves previous results of Rebrova and Vershynin, and Rebrova. We also prove an analogous result for $A$ a symmetric $n\times n$ random matrix whose upper-diagonal entries are i.i.d. with mean $0$ and variance $1$.