Techniques are disclosed herein for erasing non-volatile memory cells. The memory cells are erased using a trial erase pulse. A suitable magnitude for a second pulse is determined based on the magnitude of the trial erase pulse and data collected about the threshold voltage distribution after the trial erase. The second erase pulse is used to erase the memory cells. In one implementation, the threshold voltages of the memory cells are not verified after the second erase. Soft programming after the second erase may be performed. The magnitude of the soft programming pulse may be determined based on the trial erase pulse. In one implementation, the memory cells'threshold voltages are not verified after the soft programming. Limiting the number of erase pulses and soft programming pulses saves time and power. Determining an appropriate magnitude for the second erase pulse minimizes or eliminates over-erasing.