Largest Range in an Array

Problem:

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:

  1. 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
  2. How should we handle empty lists? I am assuming empty list returns "()". Even here, most interviewers let you choose a suitable default
  3. 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.

  1. A count variable to keep track of the current count of the largest sub-array
  2. A max_count variable to store the length of the longest sub-array found so far.
  3. 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:

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:

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.

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

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store