Dice el Diccionario panhispánico de dudas: «dar(se) cuenta. Esta locución verbal va siempre seguida de un complemento precedido de la preposición de. […] Debe evitarse, en el habla esmerada, la supresión de la preposición de cuando el complemento es una oración subordinada introducida por la conjunción que».

Lo adecuado, pues, es «me di cuenta de que era tarde».