In this paper, an approach is presented for determining the required storage capacity of a warehouse with leased public space. Storage assignment policies considered are randomized and class-based storage assignment policies. An analytic model for each of the storage policies is formulated with the objective of minimizing the cost of owned storage space and leased space while satisfying a desired service level of protection against space shortages. Cost functions used in the models are piecewise liear with fixed costs. For the models, algorithms are developed to generate optimal solutions. The approach is applied to the systems where the standard economic-order-quantity inventory model is used for all items being stored in the warehouse.