Here's a quick-and-dirty way to find gaps by counting the number of dates you know, then advancing from the first one, recording gaps until you've seen all the known dates there are to see. It assumes no leading zeros in months, and handles the edge cases of being handed an empty list, or a list with one date in it. Note the bruce-force determination of the initial date in the range.

sub find_gaps {
    my $dates = shift;
    my $ndates = scalar keys %$dates;
    my @missing = ();

    return \@missing if $ndates == 0;

    # Determine the first date in the range
    my $year = substr((sort keys %$dates)[0],0,4);
    my $month = 1;
    while ( ! exists $$dates{ "$year-$month" } ) {
        do {$month = 1; ++$year} if ++$month > 12;
    }
    --$ndates;

    # Look for gaps until we've seen each date in the range
    while ( $ndates ) {
        do { $month = 1; ++$year } if ++$month > 12;
        if ( exists $$dates{"$year-$month"} ) {
            --$ndates;
        } else {
            push @missing, "$year-$month";
        }
    }

    return \@missing;
}
[download]