According to one embodiment, a semiconductor memory device includes a plurality of blocks in a memory cell, each of the blocks acting as an erasure unit of data, the block including a plurality of pages, each of the pages including a plurality of memory cell transistors, each of the memory cell transistors being configured to be an erasure state or a first retention state based on a threshold voltage of the memory cell transistor, and a controller searching data in the block with respect to, writing a first flag denoting effective into a prescribed page of the block with the erasure state, and writing the first flag denoting non-effective into a prescribed page of the block with the first retention state, reading out the prescribed page of the block with the first retention state, and determining that the block is writable when the first flag denotes effective.