It is best to book as far in advance as possible, for example directly after you buy your flights. There is a hard limit on the amount of cars that can be rented, and this scarcity can drive prices up especially close in time to our most popular events such as the Ironman Triathlon (mid October) and the Merrie Monarch festival (mid to late April).
Make sure to book a fully refundable fare and check again a few months before your trip to make sure you got the best deal.