Supposing the number of distinct small numbers is really going to stay small and the number of entries on the array on the thousands:

# untested!

my %bitmap;
for my $ix (0..$#AoA) {
  for my $sn (@{$AoA[$ix]}) {
    vec($bitmap{$sn}, $ix, 1) = 1;
  }
}

my @nope = (2, 13, 3, 16);

my $bad = ''
for my $bit (@nope) {
  $bad ||= $bitmap{$bit};
}

my @ok = grep { !vec($bad, $_, 1) } 0..$#AoA
[download]

That should use no more than a few KB and be O(N).