The Degree of Difficulty is the Difficulty of the Degree

Wherein we whittle and shape and trim, shape and trim, shape and trim, obsessively to the n-th degree: “What’s the frequency, Kenneth?” The frequency is coming from inside the house! The frequency is you! (points menacingly)

THE WEEKLY CHALLENGE – PERL & RAKU #189 Task 2

---

“buy genuine degree certificate without exam online”

— allexamscertificates.com

---

Array Degree

Submitted by: Mohammad S Anwar

You are given an array of 2 or more non-negative integers.

Write a script to find out the smallest slice, i.e. contiguous subarray of the original array, having the degree of the given array.

The degree of an array is the maximum frequency of an element in the array.

Example 1

Input: @array = (1, 3, 3, 2)
Output: (3, 3)

The degree of the given array is 2.

The possible subarrays having the degree 2 are as below:

(3, 3)
(1, 3, 3)
(3, 3, 2)
(1, 3, 3, 2)

And the smallest of all is (3, 3).

Example 2

Input: @array = (1, 2, 1, 3)
Output: (1, 2, 1)

Example 3

Input: @array = (1, 3, 2, 1, 2)
Output: (2, 1, 2)

Example 4

Input: @array = (1, 1, 2, 3, 2)
Output: (1, 1)

Example 5

Input: @array = (2, 1, 2, 1, 1)
Output: (1, 2, 1, 1)

ANALYSIS

Right off the bat, we could solve this through an exhaustive search. Starting at the first index, we create a slice with and endpoint at the second and determine its degree. Then we extend the slice one position and repeat the process. Initializing our original 2-element slice and its degree as running maximums, we will replace these under two possible conditions: either the degree found is blatently higher than the current maximum, or if the degree is the same but the length shorter. Eventually after we examine all slices we will have captured the shortest slice of the highest degree. This technique as stated will find the first of multiple otherwise-equal options. If we change the second criterium for replacement to “less than or equal to” we will capture the last occurrence.

This is all well and good but isn’t very efficient, as we need to examine every possible slice before making the final determination. On the other hand we do avoid having to precompute the degree of the array beforehand. But this is small solace against our fundamentally quadratic complexity.

What do we gain, then, if we do precompute the degree? Well, for one we can stop extending a slice once we have reached our target degree. There’s no point in adding additional elements when we know the next number will never be our target, as this extended slice will never be minimal.

This is a good line of thinking.

So from this we can infer that the last element in our minimal slice will be that number that raises the slice to the proper degree. Once we have that any additional numbers will simply add length, and the slice is already the shortest it can be.

Or is it?

The same logic can be extended to the first incidence of what we shall call the degree-integer. Any elements before that element will also pointlessly extend the slice, adding length to no good end. If we could somehow cull these elements — everything before the first incidence — then we would have properly minimized the slice.

We can deduce, then, that the shortest slice will begin with the degree-number and also end with it. Very interesting.

When we initially determine the degree we can note the integer with the highest frequency, or integers if there are more than one with equal counts. Then, when iterating across the elements, if the slice does not start with one of those numbers we can immediately jump to the next position. Then, we extend the slice until we have counted the correct number of occurences. This sounds much more efficient!

And it is! But wait there’s more! When we first make our pass over the array we can gather all the information we need as we go, namely the first occurrence and last occurrence of each integer. Then once we find the number or numbers that define the degree we will already know the slice boundaries that start and end with these values, and the length will be in the span between the two, inclusive. Let the shortest span win! ^{_{Offer Void In Nebraska}}

METHOD

We will make a single pass over the input array, hashing the data three ways as we go: incrementing a frequency counter for each integer, logging its position to the last-sighting hash, and, only if it has never been seen before, logging its position in the initial-occurrence hash. And while we’re at it we can keep a running tab on the maximum degree.

When we finish the pass, we can find the list of numbers with the highest frequency with a grep filter. Then, for each of these integers we can construct a new key in a fourth hash that points to the computed length, keeping a tally of the minimum value as we go. A second filter based on this minimum will give us our minimal degree-integers, and we can then output the slices defined by the low and high bounds we’ve previously gathered.

PERL 5 SOLUTION

We’ll just make a subroutine that, given an array reports the input array data, the degree found and a list of one or more minimal array slices found.

sub degree_slice ( @arr ) {
    my (%bag, %first, %last);
    my $max = 0;
    for (0..$#arr) {
        ++$bag{ $arr[$_] } > $max and $max = $bag{$arr[$_]};
        $first{ $arr[$_] } = $_ if not defined $first{$arr[$_]};
        $last{  $arr[$_] } = $_;
    }

    my @deg_int = grep { $bag{$_} == $max } keys %bag;
    my $min = @arr;
    my %lengths;
    
    for (0..$#deg_int) {
        $lengths{ $deg_int[$_] } = $last{ $deg_int[$_] } 
                                      - $first{ $deg_int[$_] } + 1;
        $min > $lengths{ $deg_int[$_] } and $min = $lengths{ $deg_int[$_] };
    }
    my @minimum_degree_integers = grep { $lengths{ $_ } == $min } 
                                        @deg_int;

    say "input:  @arr";
    say "degree: $max";
    say "minimal slice(s):";
    for (@minimum_degree_integers) {
        my @slice = @arr[ $first{$_} .. $last{$_} ];
        say "   @slice";
    }
}