Here’s the problem statement:
Given an array of integers, find the end points of the longest range of values present in the array. Note the elements in the range need not necessarily be placed adjacent/in order in the input array.
For example:
The array: [4, 20, 5, 6, 21, 22, 7, 8, 41, 9]
Output: [6] where the range is [4, 5, 6, 7, 8, 9]
Let’s dive into the solution:
Approach 1:
Sort the array first. Sorting will place all the elements that lie in a range in consecutive positions. Now traverse through the array using a for loop while counting the length of numbers that fall in a range and updating the max length when required.
Time complexity: O(NlogN) is time taken to sort the array and O(N) is the time taken to traverse through it. Therefore the overall time complexity is O(NlogN)
Space complexity: O(1) because we do not use any extra space.
Approach 2:
Let’s see if we can do better than O(NlogN) this time by using up some space.
This approach in its way of expanding left and right of elements is similar to the Free Items problem.
- Maintain a HashMap to mark the elements visited. Initially map every element in the array to false.
- Loop through the array using a for loop.
- At every array element array[i] that is not visited yet, expand to the left of it on the number line as long as the expansion numbers are present in the input array i.e. if array[i] = 4, expand to 3,2,1…. as long as the numbers are present in array and keep counting the length of elements so far in the range. Also mark the elements in the array as visited by mapping them to true in the HashMap.
- Similarly, at every array element array[i] expand to the right of it on the number line as long as the expansion numbers are present in the input array i.e. if array[i] = 4, expand to 5,6,7…. as long as the numbers are present in array and keep counting the length of elements so far in the range. Also mark the elements in the array visited by mapping them to true in the HashMap.
- Update maxLength if needed.
- Increment i and repeat the above steps if the element has not been visited earlier.
Note that we use a HashMap instead of just adding array elements in a HashSet while expanding to the left/right of an element because we also need to be able to check if the expanded (incremented/decremented) value is present in the given array and whether or not it has been visited before which does not seem possible using only a single HashSet.
Time complexity: O(N)
Time complexity: O(N): to store the HashMap
Here’s the code for this solution in Java:
public int[] maximumRange(int[] array) {
HashMap<Integer, Boolean> map = new HashMap<>();
int beg, end, maxLen, left, right;
beg = end = -1;
maxLen = 0;
for(int n: array)
map.put(n, false);
for(int i=0;i<array.length;i++) {
left = array[i];
while(map.containsKey(left-1) && !map.get(left-1)) {
map.put(left-1, true);
left--;
}
right = array[i];
while(map.containsKey(right+1) && !map.get(right+1)) {
map.put(right+1, true);
right++;
}
if((right-left+1)>maxLen) {
maxLen = right-left+1;
beg = left;
end = right;
}
}
return new int[]{beg, end};
}
Please do let me know if you find this article useful. Also, it’ll be great if you’d provide some feedback. To reach out, please leave a comment in the Contact section. Thanks! Happy Coding! 🙂
The Code Scribbbler 