In this paper, a sensor placement approach to improve the leak location in water distribution networks is proposed when the leak signature space (LSS) method is used. The sensor placement problem is formulated as an integer optimization problem where the criterion to be minimized is the number of overlapping signature domains computed from the original LSS representation. First, a semi-exhaustive search approach based on a lazy evaluation mechanism ensures optimal placement in the case of low complexity scenarios. For more complex cases, a stochastic optimization process is proposed, based on either the genetic algorithms (GAs) or particle swarm optimization (PSO). Experiments on two different networks are used to evaluate the performance of the resolution methods, as well as the efficiency achieved in the leak location when using the sensor placement results.