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.