Ensemble of clustering methods is recently shown to perform better than conventional clustering methods. One of the drawback of the ensemble is, its computational requirements can be very large and hence may not be suitable for large data sets. The paper presents an ensemble of leaders clustering methods where the entire ensemble requires only a single scan of the data set. Further, the component leaders complement each other while deriving individual partitions. A heuristic based consensus method to combine the individual partitions is presented and is compared with a well known consensus method called co-association based consensus. Experimentally the proposed methods are shown to perform well.