zlib1g is not a linux command/executable binary. zlib1g is a library and zlib1g-dev are headers for c/c++. You need to add linker flag -lz when compiling so it will include zlib.

The same issue happened to me on Focal, a pretty bare install from the default:

# apt install zlib1g-dev                                                                    
Reading package lists... Done                                                                                                          
Building dependency tree                                                                                                               
Reading state information... Done                                                                                                      
Some packages could not be installed. This may mean that you have                                                                      
requested an impossible situation or if you are using the unstable                                                                     
distribution that some required packages have not yet been created                                                                     
or been moved out of Incoming.                                                                                                         
The following information may help to resolve the situation:                                                                           
                                                                                                                                       
The following packages have unmet dependencies.                                                                                        
 zlib1g-dev : Depends: zlib1g (= 1:1.2.11.dfsg-2ubuntu1) but 1:1.2.11.dfsg-2ubuntu1.2 is to be installed

To get zlib1g-dev to install it was necessary to downgrade zlib1g, which tbh is ridiculous for something in the main repo:

# apt install zlib1g=1:1.2.11.dfsg-2ubuntu1

A similar issue happened when trying to install openssh-server after first post-install boot.