Hey @npatel
Welcome to the Freshworks developer community 
As per Freshdesk API documentation, the company_id can be provided only if the contact is associated with multiple companies, please refer to the screenshot below
.
multiple companies for a contact can be enabled by following the steps in the link below.
Seems like a contact is associated with only one company by default, maybe this could the root cause for your issue.
Hope this helps!
Stay safe