How to permanently change the hostname on Ubuntu

I tried many ways and the hostname kept getting reset back to the previous value. Turns out there are two steps to changing the hostname permanently on Ubunut.

Firstly, update preserve_hostname in /etc/cloud/cloud.cfg

preserve_hostname: true

Secondly use hostnamectl to change the hostname

sudo hostnamectl set-hostname new-host-name

Now when we reboot, the hostname will stay as new-host-name