When should you replace K-Means with a different clustering algorithm?

You replace K-Means when clusters are non-spherical, density varies, or data contains noise and outliers.

K-Means assumes convex, equally sized clusters. If these assumptions fail, algorithms like DBSCAN (density-based), GMM (probabilistic), or spectral clustering (graph-based) are better suited.