Largest Range in an Array


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


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

  1. How should we handle empty lists? I am assuming empty list returns "()". Even here, most interviewers let you choose a suitable default
  2. 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.
  1. A max_count variable to store the length of the longest sub-array found so far.
  2. l_bound and u_bound integers to keep track of lower and upper bound of the longest sub-array.

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.


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.

Solutions to programming interview questions at some of the top companies in the world: