Learn Portuguese (Portugal): Foi na rapariga da máscara que eu esbarrei. - It was the girl with the mask that I bumped into.

This is the core of a prepositional cleft sentence. The verb at the end, esbarrar, requires the preposition em (to bump into). When we emphasize who we bumped into using foi ... que (it was ... that), the preposition em must move to the front and attach to the emphasized noun. Since it is a rapariga, em + a becomes na.

Why does the sentence use da máscara instead of com a máscara to mean with the mask?

In English we say the girl with the mask, but Portuguese frequently uses de (here, de + a = da) to describe physical attributes, clothing, or accessories someone is wearing. You will often see this instead of com, such as o homem de óculos (the man with glasses).

Is it possible to structure this without fronting the preposition?

You cannot leave a dangling preposition at the end of a sentence in Portuguese. However, another correct way to say this is to attach the preposition to the relative pronoun instead of the emphasized noun: Foi a rapariga da máscara em que eu esbarrei (or em quem). Moving the preposition all the way to the front, as in this sentence, is very natural and common.

Does the verb esbarrar always require the preposition ?