view release on metacpan or  search on metacpan

lib/Algorithm/SlidingWindow/Dynamic.pm  view on Meta::CPAN

B<Important:> This algorithm assumes that all input values are non-negative.
If negative values are present, a different approach is required.

  use Algorithm::SlidingWindow::Dynamic;

  sub shortest_subarray_at_least_k {
      my ($nums, $k) = @_;

      my $w   = Algorithm::SlidingWindow::Dynamic->new;
      my $sum = 0;
      my $best;

      for my $x (@$nums) {
          die "negative values not supported" if $x < 0;

          $w->push($x);
          $sum += $x;

          while ($w->size > 0 && $sum >= $k) {
              my $len = $w->size;
              $best = $len if !defined($best) || $len < $best;

              my $removed = $w->shift;
              $sum -= $removed;
          }
      }

      return defined($best) ? $best : -1;
  }

  print shortest_subarray_at_least_k([2, 3, 1, 2, 4, 3], 7), "\n";  # prints 2

=head2 Fixed-Length Rolling Window Using slide()

  my $w = Algorithm::SlidingWindow::Dynamic->new;

  $w->push(10);
  $w->push(20);

t/02-examples-shortest-subarray.t  view on Meta::CPAN

use warnings;

use Test::More;
use Algorithm::SlidingWindow::Dynamic;

sub shortest_subarray_at_least_k {
    my ($nums, $k) = @_;

    my $w   = Algorithm::SlidingWindow::Dynamic->new;
    my $sum = 0;
    my $best;

    for my $x (@$nums) {
        die "negative values not supported" if $x < 0;

        $w->push($x);
        $sum += $x;

        while ($w->size > 0 && $sum >= $k) {
            my $len = $w->size;
            $best = $len if !defined($best) || $len < $best;

            my $removed = $w->shift;
            $sum -= $removed;
        }
    }

    return defined($best) ? $best : -1;
}

is(
    shortest_subarray_at_least_k([2, 3, 1, 2, 4, 3], 7),
    2,
    'shortest subarray example from POD'
);

is(
    shortest_subarray_at_least_k([1, 1, 1, 1], 10),