Given an int array which might contain duplicates, find the largest subset of it which form a sequence.
For example, in {5, 7, 3, 4, 9, 10, 1, 6, 15, 1, 3, 12, 2, 11} longest sequence is {1, 2, 3, 4, 5,6}.
The first thing that comes into our mind is to sort given array in O(n log n ) and look for longest consecutive elements sequence. Can we do it in Linear time?
The next solution would be using bit vector indexed by numbers from original array. It may not be justified due to incomparable solution space and original array size (although time complexity is O(n)).
Lets see how to solve this problem in O( n ) time complexity with constant space assuming the hashtable has O(1) time complexity and constant space complexity.
For each number A[i], put A[i] in hashMap<Int, List>
Also check if (A[i]+1) and (A[i]-1) exists in the Map,
If hashMap.contains((A[i]+1)) is true then append A[i] to the hashMap.get((A[i]+1));
If hashMap.contains((A[i]-1)) is true then append A[i] to the hashMap.get((A[i]-1));
And Append hashMap.get(A[i]+1) and hashMap.get(A[i]-1) to hashMap.get(A[i]);
In the end the iterate through all the keys of the hashMap and the largest List of hashMap.get(A[i]) is the longest sequence that exists in the input array.
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
public class LargestSequence {
public static void main(String[] args) {
int[] A = { 2, 3, 9, 10, 11, 4, 13, 5, 15, 6, 17, 7 };
HashSet<Integer> sequenceList = getLargestSequence(A);
Iterator<Integer> iter = sequenceList.iterator();
System.out
.println("Subset which forms the longest consecutive sequence: ");
while (iter.hasNext()) {
System.out.print(iter.next() + " ");
}
}
public static HashSet<Integer> getLargestSequence(int[] A) {
HashSet<Integer> result = new HashSet<Integer>();
if (A == null) {
return result;
}
int len = A.length;
Map<Integer, HashSet<Integer>> dataMap = new HashMap<Integer, HashSet<Integer>>();
for (int i = 0; i < len; i++) {
int less = A[i] - 1;
int more = A[i] + 1;
HashSet<Integer> list = new HashSet<Integer>();
boolean leftUpdated = false;
boolean rightUpdated = false;
if (dataMap.containsKey(less)) {
list = dataMap.get(less);
list.add(A[i]);
dataMap.put(less, list);
HashSet<Integer> keylist = dataMap.get(A[i]);
if (keylist != null) {
keylist.add(less);
keylist.addAll(list);
} else {
keylist = new HashSet<Integer>();
keylist.addAll(list);
}
dataMap.put(A[i], keylist);
leftUpdated = true;
}
if (dataMap.containsKey(more)) {
list = dataMap.get(more);
list.add(A[i]);
dataMap.put(more, list);
HashSet<Integer> keylist = dataMap.get(A[i]);
if (keylist != null) {
list.add(more);
// keylist.add(more);
keylist.addAll(list);
} else {
keylist = new HashSet<Integer>();
keylist.addAll(list);
}
dataMap.put(A[i], keylist);
rightUpdated = true;
}
if (!leftUpdated && !rightUpdated) {
list.add(A[i]);
dataMap.put(A[i], list);
}
}
Iterator<Entry<Integer, HashSet<Integer>>> it = dataMap.entrySet()
.iterator();
while (it.hasNext()) {
Map.Entry<Integer, HashSet<Integer>> pair = (Map.Entry<Integer, HashSet<Integer>>) it
.next();
if (pair.getValue().size() > result.size()) {
result = pair.getValue();
}
}
return result;
}
}
Posts
