# Largest Range in an Array

# Problem:

Given an array of integers, return the largest range, inclusive, of integers that are all included in the array.

For example, given the array `[9, 6, 1, 3, 8, 10, 12, 11]`

, return `(8, 12)`

since 8, 9, 10, 11, and 12 are all in the array.

# Approach:

You should start by asking relevant questions, and scoping the problem:

- What should the return type be? I am assuming the return type is a formatted string
`"(lower_bound,upper_bound)"`

, e.g.`"(8,12)"`

in the example above. Most interviewers let you choose your own return type - How should we handle empty lists? I am assuming empty list returns
`"()"`

. Even here, most interviewers let you choose a suitable default - How about repeated integers in the list? Let’s assume a repeated number is only counted once, so, the longest range in
`[8, 8, 8, 9, 1, 2, 3]`

is`[1, 2, 3]`

even though`8`

appears three times.

We should be quickly able design the simplest, and slightly inefficient algorithm: A list of consecutive integers hints at sorting the array. We can keep an extra set of variables/counters to keep tracks of the largest consecutive subset of this sorted array.

- A
`count`

variable to keep track of the current count of the largest sub-array - A
`max_count`

variable to store the length of the longest sub-array found so far. `l_bound`

and`u_bound`

integers to keep track of lower and upper bound of the longest sub-array.

Pay a close attention to how you initialize and update these variables — it’s extremely important to get these updates right. And NEVER implement your own sorting! Use `std::sort`

as your friend.

# Efficient Algorithm:

What is the complexity of the algorithm above? The complexity is dominated by that of `std::sort`

- the rest of the loop is a single pass through the sorted array. The total complexity is therefore `O(NlogN)`

, where `N`

is the size of the array.

Can we do better? It turns out we can. This problem is interesting because a seemingly unrelated graph algorithm is useful for efficiently solving it.

The key here is to avoid explicitly constructing the graph, but instead using a `std::unordered_map`

and a constant time lookup to check whether neighbors of node `i`

exist in the array. Just like the previous algorithm, we will also need to maintain the auxiliary variables like `count`

and `max_count`

, and efficiently update them. Here is a re-implementation of `find_range`

with BFS:

# Testing:

Like always, we are going to use Gunit testing framework for writing tests. Let’s start with a few simple test cases: An empty list, and a list with a single element.

A little advanced example includes a two element list with consecutive elements or the example given in the problem statement

Finally, an excellent candidate will also create a randomized test, generating a random array from 1 to n.

*Originally published at **https://cppcodingzen.com** on August 29, 2020.*