Finding contiguous ranges in arrays

Question

You are given an array of integers. You have to output the largest range so that all numbers in the range are present in the array. The numbers might be present in any order. For example, suppose that the array is

{2, 10, 3, 12, 5, 4, 11, 8, 7, 6, 15}

Here we find two (nontrivial) ranges for which all the integers in these ranges are present in the array, namely [2,8] and [10,12]. Out of these [2,8] is the longer one. So we need to output that.

When I was given this question, I was asked to do this in linear time and without using any sorting. I thought that there might be a hash-based solution, but I couldn't come up with anything.

Here's my attempt at a solution:

void printRange(int arr[])
{
    int n=sizeof(arr)/sizeof(int);
    int size=2;
    int tempans[2]; 

    int answer[2];// the range is stored in another array
    for(int i =0;i<n;i++)
    {
        if(arr[0]<arr[1])
        {
             answer[0]=arr[0];
             answer[1]=arr[1];
        }
        if(arr[1]<arr[0])
        {
            answer[0]=arr[1];
            answer[1]=arr[0];
        }

        if(arr[i] < answer[1])
            size += 1;
        else if(arr[i]>answer[1]) {
            initialize tempans to new range;
             size2=2;
        }
        else { 
            initialize tempans  to new range
        }
}

//I have to check when the count becomes equal to the diff of the range

I am stuck at this part... I can't figure out how many tempanswer[] arrays should be used.

Answer 1

I think that the following solution will work in O(n) time using O(n) space.

Begin by putting all of the entries in the array into a hash table. Next, create a second hash table which stores elements that we have "visited," which is initially empty.

Now, iterate across the array of elements one at a time. For each element, check if the element is in the visited set. If so, skip it. Otherwise, count up from that element upward. At each step, check if the current number is in the main hash table. If so, continue onward and mark the current value as part of the visited set. If not, stop. Next, repeat this procedure, except counting downward. This tells us the number of contiguous elements in the range containing this particular array value. If we keep track of the largest range found this way, we will have a solution to our problem.

The runtime complexity of this algorithm is O(n). To see this, note that we can build the hash table in the first step in O(n) time. Next, when we begin scanning to array to find the largest range, each range scanned takes time proportional to the length of that range. Since the total sum of the lengths of the ranges is the number of elements in the original array, and since we never scan the same range twice (because we mark each number that we visit), this second step takes O(n) time as well, for a net runtime of O(n).

EDIT: If you're curious, I have a Java implementation of this algorithm, along with a much more detailed analysis of why it works and why it has the correct runtime. It also explores a few edge cases that aren't apparent in the initial description of the algorithm (for example, how to handle integer overflow).

Hope this helps!

Answer 2

The solution could use BitSet:

public static void detect(int []ns) {
    BitSet bs = new BitSet();
    for (int i = 0; i < ns.length; i++) {
        bs.set(ns[i]);
    }
    int begin = 0;
    int setpos = -1;
    while((setpos = bs.nextSetBit(begin)) >= 0) {
        begin = bs.nextClearBit(setpos);
        System.out.print("[" + setpos + " , " + (begin - 1) + "]");
    }
}

Sample I/O:

detect(new int[] {2,10, 3, 12, 5,4, 11, 8, 7, 6, 15} );

[2,8] [10,12] [15,15]

Answer 3

Here is the solution in Java:

public class Solution {  
    public int longestConsecutive(int[] num) {  
        int longest = 0;  
        Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();  
        for(int i = 0; i< num.length; i++){  
            map.put(num[i], false);  
        }  

        int l, k;  
        for(int i = 0;i < num.length;i++){  

            if(map.containsKey(num[i]-1) || map.get(num[i])) continue;  
            map.put(num[i], true);  
            l = 0; k = num[i];  
            while (map.containsKey(k)){  
                l++;  
                k++;  
            }  
            if(longest < l) longest = l;  

        }  
        return longest;  
    }  
}  

Other approaches here.

Answer 4

A Haskell implementation of Grigor Gevorgyan's solution, from another who didn't get a chance to post before the question was marked as a duplicate...(simply updates the hash and the longest range so far, while traversing the list)

import qualified Data.HashTable.IO as H
import Control.Monad.Random

f list = do 
  h <- H.new :: IO (H.BasicHashTable Int Int)
  g list (0,[]) h where
    g []     best h = return best
    g (x:xs) best h = do 
      m <- H.lookup h x
      case m of
        Just _     -> g xs best h
        otherwise  -> do 
          (xValue,newRange) <- test
          H.insert h x xValue
          g xs (maximum [best,newRange]) h
       where 
         test = do
           m1 <- H.lookup h (x-1)
           m2 <- H.lookup h (x+1)
           case m1 of
             Just x1 -> case m2 of
                          Just x2 -> do H.insert h (x-1) x2
                                        H.insert h (x+1) x1
                                        return (x,(x2 - x1 + 1,[x1,x2]))
                          Nothing -> do H.insert h (x-1) x
                                        return (x1,(x - x1 + 1,[x,x1]))
             Nothing -> case m2 of
                          Just x2 -> do H.insert h (x+1) x
                                        return (x2,(x2 - x + 1,[x,x2]))
                          Nothing -> do return (x,(1,[x]))

rnd :: (RandomGen g) => Rand g Int
rnd = getRandomR (-100,100)

main = do
  values <- evalRandIO (sequence (replicate (1000000) rnd))
  f values >>= print

Output:

*Main> main
(10,[40,49])
(5.30 secs, 1132898932 bytes)

Answer 5

I read a lot of solutions on multiple platforms to this problem and one got my attention, as it solves the problem very elegantly and it is easy to follow.

The backbone of this method is to create a set/hash which takes O(n) time and from there every access to the set/hash will be O(1). As the O-Notation omit's constant terms, this Algorithm still can be described overall as O(n)

def longestConsecutive(self, nums):
    nums = set(nums)                    # Create Hash O(1)   
    best = 0
    for x in nums:                   
        if x - 1 not in nums:           # Optimization
            y = x + 1                   # Get possible next number
            while y in nums:            # If the next number is in set/hash
                y += 1                  # keep counting
            best = max(best, y - x)     # counting done, update best
    return best

It's straight forward if you ran over it with simple numbers. The Optimization step is just a short-circuit to make sure you start counting, when that specific number is the beginning of a sequence.

All Credits to Stefan Pochmann.

Answer 6

The above answer by template will work but you don't need a hash table. Hashing could take a long time depending on what algorithm you use. You can ask the interviewer if there's a max number the integer can be, then create an array of that size. Call it exist[] Then scan through arr and mark exist[i] = 1; Then iterate through exist[] keeping track of 4 variables, size of current largest range, and the beginning of the current largest range, size of current range, and beginning of current range. When you see exist[i] = 0, compare the current range values vs largest range values and update the largest range values if needed.

If there's no max value then you might have to go with the hashing method.

Answer 7

Actually considering that we're only sorting integers and therefore a comparision sort is NOT necessary, you can just sort the array using a Radix- or BucketSort and then iterate through it.

Simple and certainly not what the interviewee wanted to hear, but correct nonetheless ;)

Answer 8

Very short solution using Javascript sparse array feature:

O(n) time using O(n) additional space.

var arr = [2, 10, 3, 12, 5, 4, 11, 8, 7, 6, 15];

var a = [];
var count = 0, max_count = 0;

for (var i=0; i < arr.length; i++) a[arr[i]] = true;
for (i = 0; i < a.length; i++) {
    count = (a[i]) ? count + 1 : 0;
    max_count = Math.max(max_count, count);
    }

console.log(max_count); // 7

Answer 9

A quick way to do it (PHP) :

$tab = array(14,12,1,5,7,3,4,10,11,8);
asort($tab);
$tab = array_values($tab);
$tab_contiguous = array();
$i=0;
foreach ($tab as $key => $val) {
    $tab_contiguous[$i][] = $tab[$key];
    if (isset($tab[$key+1])) {
        if($tab[$key] + 1 != $tab[$key+1])
            $i++;
    }
}
echo(json_encode($tab_contiguous));