Given a finite non-degenerate set-theoretic solution $(X,r)$ of the Yang-Baxter equation and a field $K$, the structure $K$-algebra of $(X,r)$ is $A=A(K,X,r)=Klangle Xmid xy=uv mbox{ whenever }r(x,y)=(u,v)rangle$. Note that $A=oplus_{ngeq 0} A_n$ is a graded algebra, where $A_n$ is the linear span of all the elements $x_1cdots x_n$, for $x_1,dots ,x_nin X$. One of the known results asserts that the maximal possible value of $dim (A_2)$ corresponds to involutive solutions and implies several deep and important properties of $A(K,X,r)$. Following recent ideas of Gateva-Ivanova cite{GI2018}, we focus on the minimal possible values of the dimension of $A_2$. We determine lower bounds and completely classify solutions $(X,r)$ for which these bounds are attained in the general case and also in the square-free case. This is done in terms of the so called derived solution, introduced by Soloviev and closely related with racks and quandles. Several problems posed in cite{GI2018} are solved.