Non-invasively focusing light into strongly scattering media, such as biological tissue, is highly desirable but challenging. Recently, wavefront shaping technologies guided by ultrasonic encoding or photoacoustic sensing have been developed to address this limitation. So far, these methods provide only acoustic diffraction-limited optical focusing. Here, we introduce nonlinear photoacoustic wavefront shaping (PAWS), which achieves optical diffraction-limited (i.e. single-speckle-grain) focusing in scattering media. We develop an efficient dual-pulse excitation approach to generate strong nonlinear photoacoustic (PA) signals based on the Grueneisen memory effect. These nonlinear PA signals are used as feedback to guide iterative wavefront optimization. By maximizing the amplitude of the nonlinear PA signal, light is effectively focused to a single optical speckle grain. Experimental results demonstrate a clear optical focus on the scale of 5-7 micrometers, which is ~10 times smaller than the acoustic focus in linear dimension, with an enhancement factor of ~6000 in peak fluence. This technology has the potential to provide highly confined strong optical focus deep in tissue for microsurgery of Parkinsons disease and epilepsy or single-neuron imaging and optogenetic activation.