I think that you cannot solve this problem easily working incrementally as you do. Moreover, your specs are a bit unclean, because you're asking for animal names, but you want to print out more info. What if HIPPO appears also in Indiana, but only one time? Would Indiana be printed (because it contains an animal that matches the specs) or wouldn't it (because the animal appears only one time)?

I usually find it cleaner to transform the data in something that is straightforward to analyse later, possibly using more logic passes. In this case, I see two distinct problems:

• detection: you have to tell which animals match your rules
• presentation: you have to print the way you like.

For the detection part, I'd use a hash of hashes in which the first index is the animal name, and the second is the name of the state. The elements would be the names of the zoos:

use strict;
use warnings;
use Data::Dumper;

my %bighash = (

 'Arizona'=> {
              'ZOO_1' => [ '5','HIPPO', ['some arr'],['some arr']],
              'ZOO_2' => [ '10','HIPPO',['some arr'],['some arr']],
              'ZOO_3' => [ '2', 'PUMA', ['some arr'],['some arr']],
              'ZOO_5' => [ '1', 'PUMA', ['some arr'],['some arr']],
            },
'Indiana' => {
             'ZOO_9' => [ '25', 'ZEBRA', ['some arr'],['some arr']],
             'ZOO_5' => [ '13', 'MONKEY',['some arr'],['some arr']],
             'ZOO_6' => [ '23', 'ZEBRA', ['some arr'],['some arr']],
             },
'Nevada' => {
             'ZOO_3' => [ '3', 'HIPPO', ['some arr'],['some arr']],
             'ZOO_7' => [ '11', 'HIPPO',['some arr'],['some arr']],
             'ZOO_4' => [ '21', 'LION', ['some arr'],['some arr']],
             'ZOO_12' => [ '13', 'MONKEY',['some arr'],['some arr']],
         },
      );

my %animals;
foreach my $state (keys %bighash) {
   foreach my $zoo (keys %{$bighash{$state}}) {
      my $animal = $bighash{$state}{$zoo}[1];
      push @{$animals{$animal}{$state}}, $zoo;
   }
}

# Now traverse %animals to find "pervasive" animals
my %pervasive_animals;
foreach my $animal (keys %animals) {
   foreach my $state (keys %{$animals{$animal}}) {
      if (@{$animals{$animal}{$state}} > 1) { # Occurs in more zoos
         $pervasive_animals{$animal}{$state} = $animals{$animal}{$stat
+e};
      }
   }
   # Now verify the state requirement
   delete $pervasive_animals{$animal}
      unless keys %{$pervasive_animals{$animal}} > 1;
}
print Dumper(\%pervasive_animals);

__END__

$VAR1 = {
          'HIPPO' => {
                       'Nevada' => [
                                     'ZOO_7',
                                     'ZOO_3'
                                   ],
                       'Arizona' => [
                                      'ZOO_1',
                                      'ZOO_2'
                                    ]
                     }
        };
[download]

Now %pervasive_animals holds all the animals that match the spec, together with the states and zoos where you can find them.

The presentation part is left as an exercise :) BTW, you have an error in the input data, one of the HIPPOs contains a final "0" (zero digit) instead of the big "O" (letter).