Faits : A. Le 12 janvier 2013, A._ circulait sur l'autoroute A2 en direction de Bâle sur un tronçon limité à 80 km/h, à une vitesse de 150 km/h, soit, après déduction de la marge de tolérance, avec un excès de vitesse de 64 km/h. Par décision du 3 décembre 2013, le Département de l'intérieur du canton de Soleure a retiré le permis de conduire de A._ pour une durée de 24 mois du 3 mars 2014 au 2 mars 2016, retrait confirmé sur recours par le Tribunal administratif du canton de Soleure par décision du 16 février 2015. Le 17 février 2018, A._ a conduit sous l'influence de l'alcool (0.44 mg/l) et, le 28 avril 2018, il a commis un excès de vitesse de 27 km/h hors localité. Par courrier du 19 juillet 2018, le service cantonal des automobiles et de la navigation (ci-après: SCAN) a constaté que la décision de retrait de permis de conduire prononcée le 3 décembre 2013 et confirmée le 16 février 2015 n'avait pas été exécutée en raison de changement de domicile. Il a octroyé un délai de trois mois à l'intéressé pour déposer son permis. A défaut, la mesure devait être exécutée du 19 octobre 2018 au 18 octobre 2020. Par décision du 20 juillet 2018, le SCAN a retiré le permis de conduire à A._ pour une durée de quatre mois pour conduite sous l'influence de l'alcool (0.44 mg/l) et excès de vitesse de 27 km/h hors localité, précisant que la mesure entrerait d'office en vigueur à l'échéance de l'exécution du retrait de 24 mois, soit au plus tard du 19 octobre 2020 jusqu'au 18 février 2021. Le 13 mars 2019, le Département du développement territorial et de l'environnement (ci-après: DDTE) a, sur recours, confirmé la décision. B. A._ a recouru devant la Cour de droit public du Tribunal cantonal de Neuchâtel qui, par décision 31 octobre 2019, a rejeté le recours avec suite de frais et dépens. Laissant la question de la recevabilité ouverte, la cour a souligné que A._ ne pouvait pas se prévaloir de son domicile en Allemagne pour prétendre que la mesure de retrait de permis avait été exécutée, qu'il ne contestait pas que les infractions commises en février et avril 2018 pouvaient être respectivement qualifiées d'infraction grave et moyennement grave et que, dès lors, le retrait de permis prononcé pour une durée de quatre mois n'était pas excessif, ce d'autant plus que le retrait de permis de 24 mois n'avait pas été pris en considération, faute de quoi la durée du retrait eût été supérieure aux quatre mois infligés par le SCAN. C. Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral, principalement, d'annuler l'arrêt entrepris et de renoncer à tout retrait de permis; subsidiairement, il conclut à l'annulation de l'arrêt attaqué et au renvoi de la cause au Tribunal cantonal pour nouvelle décision dans le sens des considérants. Il sollicite également l'octroi de l'effet suspensif. Le Tribunal cantonal a conclu au rejet du recours ainsi que le Département de la justice, de la sécurité et de la culture. Invité à se déterminer, le SCAN a précisé dans sa détermination que la décision du 20 juillet 2018 s'applique aussi sur un territoire étranger tant que le recourant n'a pas procédé à l'échange de son permis de conduire suisse contre un dito étranger, de sorte que la période durant laquelle il n'a pas conduit en Suisse ne saurait valoir exécution du retrait de permis. Par ordonnance du 29 janvier 2020, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif.