# 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] + 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, 4]`
Then `max_span = v[-1] - v + 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… 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 - L + 1) for L in span_dict.values()]
return max(spans)
``````

No worries, @Slavina, at least you tried the problem. That’s 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 will result in an out of bounds error.

You almost made me doubt myself for a moment there 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?