Actually the name "Malik" means MASTER not king. There is certainly a difference as a Master is greater than a mere king. According to the rules of Arabic, when "Malik" is used in a lower form, as a mere word, its intensity or power is greatly diminished making it mean king, which again is less than a Master.
Malik is considered a correct Romanization of 3 different Arabic words. These include: * (ملك) Malik (also Malek or Melik), an Arabic word and title, meaning "king", "monarch", and "sovereign". Notably not used as a given first name, but rather as a title. * (مالك) Mālik (also Maalik), an Arabic word and name, meaning "owner", "proprietor", "proprietary", "possessor", and "holder". It is the the most common among the three to be used as a first name for a person, and its use as a name dates back to ancient times. * (مليك) Malīk (also Maleek), can mean either of the two words above. Although mostly not used as a given first name. For this reason, the meaning of "owner, possessor" is more correct as the name's meaning.
How I do believe this is typically an Arabic name, I believe that it can also be used as a European name, it has a very strong sound to it, like many Germanic names for example. The name Malakai is said to be English, then how is Malik Arabic? I think it sounds like a strong name for a strong person in my opinion.