Problem solving with programming: Finding the longest consecutive subset
public static int longestRange(int[] arr) {
/* Begin by creating a hash table that holds all of the array
* elements.
*/
Set<Integer> values = new HashSet<Integer>();
for (int value: arr)
values.add(value);
/* Keep track of the longest range we've seen so far. Initially,
* this is the empty range.
*/
int longest = 0;
/* Scan across the array, searching for the longest range of values
* contained in that array.
*/
for (int value: arr) {
/* To avoid unnecessary work, don't process this element if
* we already did. To mark that it has been processed, we
* remove the element. Since Java's Set#remove function
* returns whether the element was removed successfully, we
* can combine the test/remove operation into one.
*/
if (!values.remove(value)) continue;
/* Track how many total elements are in the range containing
* the current element. Initially this is one, because the
* range contains this element.
*/
int rangeLength = 1;
/* See how many elements are greater than the current value
* and contained in the range. To avoid integer overflow,
* at each step we track whether the element we're about to
* probe is greater than the current element; on an overflow,
* this will be false.
*/
for (int i = 1; value + i > value; ++i) {
/* Again, combine the test/remove operation into
* one.
*/
if (!values.remove(value + i)) break;
++rangeLength;
}
/* Using similar logic, see how many elements in the range
* are smaller than the current value.
*/
for (int i = 1; value - i < value; ++i) {
if (!values.remove(value - i)) break;
++rangeLength;
}
/* Update the length of the longest range we've seen so far. */
if (longest < rangeLength) longest = rangeLength;
}
/* Hand back the length of the longest range we encountered. */
return longest;
}
Read full article from Problem solving with programming: Finding the longest consecutive subset
Given an array of positive and negative numbers(distinct), How do we find the length of the longest consecutive subset?
For example consider the below array
{3, 6, 1, 2, 5, 7, 8}
It contains {5,6,7,8} as the longest consecutive subset. So the answer is 4.
Method based on sorting:
Method based on Hash map:
- Initially we store all the elements to the map with visited flag as false.
- For each element do the following
- If it is not visited earlier
- Mark the element as visited
- Initiate a sequence of length 1
- Try to extend this sequence backward by marking the elements visited
- Try to extend this sequence forward by marking the elements visited
- Update the maximum sequence length
http://www.keithschwarz.com/interesting/code/?dir=longest-rangepublic static int getMaxConsecutiveSubset(int[] array){HashMap<Integer,Boolean> hMap = new HashMap<Integer, Boolean>();int maxLength = 0;int seqLength = 0;int i;//insert all the elements into the map with visible flag init to falsefor( i = 0; i < array.length; i++ ){hMap.put(array[i],false);}for( i = 0; i < array.length; i++ ){if( !hMap.get(array[i]) ){hMap.put(array[i],true);seqLength = 1;int prev = array[i]-1;while( hMap.containsKey(prev) ){hMap.put(prev,true);seqLength++;prev--;}int next = array[i]+1;while( hMap.containsKey(next) ){hMap.put(next,true);seqLength++;next++;}maxLength = Math.max(maxLength,seqLength);}}return maxLength;}public static int getMaxConsecutiveSubset1(int[] array){if( array.length == 0 )return 0;Arrays.sort(array);int i;int maxLength = 0;int currentLength = 1;for( i = 1; i < array.length; i++ ){if( array[i] == array[i-1]+1 ){currentLength++;}else{maxLength = Math.max(currentLength, maxLength);currentLength = 1;}}maxLength = Math.max(currentLength, maxLength);return maxLength;}}
public static int longestRange(int[] arr) {
/* Begin by creating a hash table that holds all of the array
* elements.
*/
Set<Integer> values = new HashSet<Integer>();
for (int value: arr)
values.add(value);
/* Keep track of the longest range we've seen so far. Initially,
* this is the empty range.
*/
int longest = 0;
/* Scan across the array, searching for the longest range of values
* contained in that array.
*/
for (int value: arr) {
/* To avoid unnecessary work, don't process this element if
* we already did. To mark that it has been processed, we
* remove the element. Since Java's Set#remove function
* returns whether the element was removed successfully, we
* can combine the test/remove operation into one.
*/
if (!values.remove(value)) continue;
/* Track how many total elements are in the range containing
* the current element. Initially this is one, because the
* range contains this element.
*/
int rangeLength = 1;
/* See how many elements are greater than the current value
* and contained in the range. To avoid integer overflow,
* at each step we track whether the element we're about to
* probe is greater than the current element; on an overflow,
* this will be false.
*/
for (int i = 1; value + i > value; ++i) {
/* Again, combine the test/remove operation into
* one.
*/
if (!values.remove(value + i)) break;
++rangeLength;
}
/* Using similar logic, see how many elements in the range
* are smaller than the current value.
*/
for (int i = 1; value - i < value; ++i) {
if (!values.remove(value - i)) break;
++rangeLength;
}
/* Update the length of the longest range we've seen so far. */
if (longest < rangeLength) longest = rangeLength;
}
/* Hand back the length of the longest range we encountered. */
return longest;
}
Read full article from Problem solving with programming: Finding the longest consecutive subset
