A cumbersome operation in physics, numerical analysis and linear algebra, optimization, and machine learning, is inverting large full-rank matrices. In this paper, we propose a coded computing approach for recovering matrix inverse approximations. We first present an approximate matrix inversion algorithm that does not require a matrix factorization but uses a black-box least squares optimization solver as a subroutine to give an estimate of the inverse of real full-rank matrices. We then present a distributed framework for which our algorithm can be implemented and show how we can leverage from sparsest-balanced MDS generator matrices to devise inverse coded computing schemes. We focus on balanced Reed-Solomon codes, which are optimal in terms of computational load; and communication from the workers to the master server. We also discuss how our algorithms can be used to compute the pseudoinverse of a full-rank matrix and how the communication can be secured from eavesdroppers.