I agree with those saying 60-90 minutes before departure, perhaps two hours if you're flying during a long holiday.

30-45 minutes is cutting it too short for comfort, in my opinion -- and I usually have priority security and emigration access departing NRT so I wouldn't get caught up in the usual queues there. 30-45 minutes is especially tight if your flight is departing from the 40s gates, which take some time to get to.