Faits : A. Le 19 mars 2008, B.X._ et A.X._ ont acquis deux biens-fonds figurant au cadastre de la commune de Y._. Sur une parcelle se trouvait une villa mitoyenne et une piscine, sur l'autre un cabanon de jardin. Le prix de vente se montait à 730'000 fr. Par courrier du 14 avril 2008, le conservateur du registre foncier a informé la notaire ayant instrumenté la vente que selon le plan d'aménagement du territoire, l'un des biens-fonds était en zone d'utilité publique, alors que l'autre l'était partiellement et que la commune de Y._ disposait d'un droit de préemption légal en cas de transfert de ces immeubles. La commune de Y._ a renoncé à faire usage de ce droit. B. Le 12 février 2009, les époux X._ ont formulé des prétentions financières auprès du Conseil communal de Y._ à hauteur de 164'244 fr. 40 pour le remboursement du préjudice subit en raison de l'absence de mention au registre foncier de l'affectation des parcelles en zone d'utilité publique. Selon eux, la commune était légalement tenue de procéder à cette mention. Ils ont parallèlement ouvert action civile contre le vendeur et la notaire. Le 12 mai 2009, niant l'existence d'un acte illicite et d'un lien de causalité, la commune a refusé d'entrer en matière sur les prétentions des époux X._. Par acte du 12 août 2009, ces derniers ont ouvert action en dommages-intérêts à l'encontre de la commune devant le Tribunal administratif de la République et canton de Neuchâtel (actuellement la Cour de droit public du Tribunal cantonal de la République et canton de Neuchâtel; ci-après: le Tribunal cantonal). Le Tribunal cantonal a suspendu la procédure jusqu'à droit connu dans la contestation de droit civil ouverte contre le vendeur et la notaire. Par arrêt du 20 mai 2014, la Ire Cour de droit civil du Tribunal fédéral a partiellement admis le recours en matière civile interjeté contre l'arrêt de la Cour d'appel civil du Tribunal cantonal (arrêt 4A_619/2013 du 20 mai 2014). Le Tribunal fédéral a annulé l'arrêt précité, rejeté la demande en paiement contre la notaire et, pour le surplus, renvoyé la cause à la Cour d'appel civil du Tribunal cantonal pour qu'elle rende une nouvelle décision. Le Tribunal cantonal a repris la procédure d'action de droit administratif ouverte contre la commune de Y._ le 7 octobre 2014. Par arrêt du 9 janvier 2015, il a rejeté la demande des époux X._. Il a jugé que l'omission de la commune de faire inscrire son droit de préemption au registre foncier ne constituait pas un acte illicite. Il n'a par conséquent pas examiné les autres conditions de la responsabilité. C. Agissant par la voie du recours en matière de droit public, B.X._ et A.X._ demandent en substance au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du 9 janvier 2015 du Tribunal cantonal et de renvoyer la cause à celui-ci pour nouvelle décision dans le sens des considérants. Ils se plaignent de constatation inexacte des faits et d'application arbitraire du droit cantonal. Le Tribunal cantonal et la commune de Y._ concluent tous deux au rejet du recours.