Given an int array which might contain duplicates, find the largest subset of it which form a sequence.
Eg. {1,6,10,4,7,9,5}
then ans is 4,5,6,7
Sorting is an obvious solution. Can this be done in O(n) time
Approach:
A = {1,6,10,4,7,9,5}
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.
Input Array for the below code:
A = {2, 3, 9, 10, 11, 4, 13, 5, 15, 6, 17, 7};
Output:
subset which forms the longest consecutive sequence:
2 3 4 5 6 7
wrong result is coming for {3,4,5,1,8,3,2,6,10,7}
ReplyDeleteplease check.
This comment has been removed by the author.
DeleteThis comment has been removed by the author.
ReplyDeletepackage com.snapdeal.test;
ReplyDeleteimport java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
public class TestClass {
static Map> dataMap = new HashMap>();
//static int [] A = {3,4,5,1,8,2,6,10,7};
static int [] A = {2, 3, 9, 10, 11, 4, 13, 15, 8, 4, 6, 17, 7, 9};
public static void main(String[] args) {
HashSet sequenceList = getLargestSequence(A);
Iterator iter = sequenceList.iterator();
System.out.println("Subset which forms the longest consecutive sequence: ");
while (iter.hasNext()) {
System.out.print(iter.next() + " ");
}
System.out.println();
//System.out.println("Done!");
}
public static HashSet getLargestSequence(int [] A) {
HashSet result = new HashSet();
if (A == null) {
return result;
}
int len = A.length;
for (int i=0; i list = new HashSet();
boolean leftUpdated = false;
boolean rightUpdated = false;
if (dataMap.containsKey(less)) {
addLess(A[i]);
leftUpdated = true;
}
if (dataMap.containsKey(more)) {
addMore(A[i]);
rightUpdated = true;
}
if (!leftUpdated && !rightUpdated) {
list.add(A[i]);
dataMap.put(A[i], list);
}
System.out.println("A[i]="+ A[i] + " " + "dataMap=" + dataMap);
}
System.out.println("dataMap=" + dataMap);
Iterator>> it = dataMap.entrySet().iterator();
while (it.hasNext()) {
Map.Entry> pair = (Map.Entry>)it.next();
if (pair.getValue().size() > result.size()) {
result = pair.getValue();
}
}
return result;
}
static boolean addMore(int num){
boolean rightUpdated = false;
if ( ! dataMap.containsKey(num + 1)) {
return false;
}
addMore(num + 1);
HashSet list = new HashSet();
// int num = A[i];
int more = num + 1;
while(dataMap.containsKey(more)) {
list = dataMap.get(more);
list.add(num);
dataMap.put(more, list);
HashSet keylist = dataMap.get(num);
if (keylist != null) {
list.add(more);
//keylist.add(more);
keylist.addAll(list);
} else {
keylist = new HashSet();
keylist.addAll(list);
}
dataMap.put(num, keylist);
num = more;
more = num - 1;
rightUpdated = true;
}
return rightUpdated;
}
static boolean addLess(int num){
boolean leftUpdated = false;
if ( ! dataMap.containsKey(num - 1)) {
return false;
}
addLess(num - 1);
HashSet list = new HashSet();
// int num = A[i];
int less = num - 1;
while(dataMap.containsKey(less)) {
list = dataMap.get(less);
list.add(num);
dataMap.put(less, list);
HashSet keylist = dataMap.get(num);
if (keylist != null) {
keylist.add(less);
keylist.addAll(list);
} else {
keylist = new HashSet();
keylist.addAll(list);
}
dataMap.put(num, keylist);
num = less;
less = num - 1;
leftUpdated = true;
}
return leftUpdated;
}
}