Python Challenge 2 - maxSpan

maxSpan problem

In this not-too-hard, not-too-easy option, you’ll tackle arrays and the appearance of values. Take your time with this one — efficiency isn’t a priority.

Consider the leftmost and righmost appearances of some value in an array.
We’ll say that the “span” is the number of elements between the two inclusive.
A single value has a span of 1. Returns the largest span found in the given
array. (Efficiency is not a priority.)

maxSpan([1, 2, 1, 1, 3]) → 4
maxSpan([1, 4, 2, 1, 4, 1, 4]) → 6
maxSpan([1, 4, 2, 1, 4, 4, 4]) → 6

Specific example:

maxSpan([1, 2, 3, 4, 5]) = 1

Occurs from a single element 1 at index 0
Occurs from a single element 2 at index 1
Occurs from a single element 3 at index 2
Occurs from a single element 4 at index 3
Occurs from a single element 5 at index 4

maxSpan([1, 2, 1, 1, 3]) = 4

Occurs from 1 at index 0 to 1 at index 3

maxSpan([1, 4, 2, 1, 4, 1, 4]) = 6

Occurs from 1 at index 0 to 1 at index 5
Occurs from 4 at index 1 to 4 at index 6

maxSpan([1, 4, 2, 1, 4, 4, 4]) = 6

Occurs from 4 at index 1 to 4 at index 6

Solution will be posted next week.

You are very confused, errors in the explanation of the problem.

maxSpan([1, 2, 1, 1, 3]) → 4
maxSpan([1, 4, 2, 1, 4, 1, 4]) → 6
maxSpan([1, 4, 2, 1, 4, 4, 4]) → 6

When setting the problem for 2 and 3 data sets, the answer is 6.

Next, in your explanation for the same data sets, answer 4

maxSpan([1, 4, 2, 1, 4, 1, 4]) = 4

Occurs from 1 at index 0 to 1 at index 3

maxSpan([1, 4, 2, 1, 4, 4, 4]) = 4

Occurs from 4 at index 1 to 4 at index 4

In your explanation, you take not the maximum range between two identical elements, but the maximum between two adjacent identical elements.

My decision:

def maxSpan(data_list):
    index_dict = {}
    for i, number in enumerate(data_list):
        if number not in index_dict:
            index_dict[number] = []
        index_dict[number].append(i)
    max_span = 1
    for elem in index_dict:
        current_span = index_dict[elem][-1] - index_dict[elem][0] + 1
        if current_span > max_span:
            max_span = current_span
    return max_span
1 Like

Nice catch. The specific explanation/example is my solution. That’s an easy fix.

Alright, I have update the specific example to reflected the correct answer and explanation. Thanks @moriturus7.

Here’s the solution for max Span: maxSpan.py

The solution preprocess the indices of all numbers and build a hash table/dictionary in order to compute each unique number span in O(1).

Preprocess the list l to store a dictionary of each unique value with its indices. This helps to optimize the computation of number of elements between the same value. Suppose element 1 occurs at index 1 and index 4.
v is the dictionary of list of indices. v[1] = [1, 4]
Then max_span = v[1][-1] - v[1][0] + 1 = 4, where -1 refers to last index

Cons: Space Complexity O(n) to build the hash table/dictionary
Pros: Improvement in time complexity to O(n) from O(n^2) using brute force

I’m bit late doing these challenges… :slight_smile: Lots of fun and learning though so please keep 'em coming!

def max_span(A):
    span_dict = {}
    for i in range(len(A)):
        if A[i] not in span_dict:
            span_dict[A[i]] = [i, i]
        else:
            span_dict[A[i]][-1] = i

    spans = [(L[1] - L[0] + 1) for L in span_dict.values()]
    return max(spans)

No worries, @Slavina, at least you tried the problem. That’s :100: for effort regardless of when you attempted the problem.

The above code may result in an error given a span of a single value.
L[1] will result in an out of bounds error.

You almost made me doubt myself for a moment there :upside_down_face:
However, this part of the code makes it so that len(L) = 2 no matter what:

if A[i] not in span_dict:
            span_dict[A[i]] = [i, i]

For instance, the span_dict for the input maxSpan([1, 4, 2, 1, 4, 1, 4]) (where the element 2 occurs only once) looks like this:

span_dict = {1: [0, 5], 4: [1, 6], 2: [2, 2]}

Ah. You can overturn the emoji.

You can compute the maximum on the fly to further improve the solution in terms of speed. Then it will be a one pass solution. Otherwise, it should be good.

max function time complexity:

  • average case is O(n)
  • worse case is O(n^2) assuming using quick select.
1 Like

Hey Slavina, I you solution a coding and got a “max() arg is an empty sequence” - could you help me out?