How do I find the missing element between two linked lists in O (n)?
I have two single lists of integers. One of them is a subset of the other (the order of the numbers is different). What's the best way (in terms of performance) to find a number that contains the first list and the second doesn't?
My thought is first sorting them (using merge sort) and then just comparing item by item. Thus it is required O(nlogn+mlogm+n)
, but a better O(n)
soltuion should exist.
source to share
This is an O (n) solution in both time and space.
Logics
Suppose the original Linked List is of size N, we will call it the LL1
second linked list as LL2
.
=> Prepare Hasmap
size N, key
will be numbers
at LL1
and value
will be frequency atLL2
HashMap<Integer,Integer> map= new HashMap<Integer,Integer>();
=> Start moving LL1
and set frequency to 0 for all numbers. By the time all the values in are LL1
repeated, you have all the numbers present in HashMap
with frequency = 0
map.put(key, 0);
=> Now start looping through LL2
, select the numbers using them as a key and increase the value by 1
.
By the time all the values in LL2
are iterated, you have all the common numbers present in LL1
and LL1
inside HashMap
, havingfrequency > 0
map.put(key, map.get(key) + 1);
=> . Now start moving around Hasmap
, looking for value = 0
when you find, print key
, since this number is only present in LL1
, not inLL2
for (map.Entry<Integer,Integer> entry : map.entrySet())
{
if(entry.getValue() == 0)
System.out.println(entry.getKey());//This is a loner
}
2 iterations and O (n) memory with O (n) time.
source to share
HashSet is the best data structure to use in this case. With this code, you can achieve your results in O (n). Let me know if you have more conditions, I can suggest something.
public class LinkedList {
private ListNode head;
public ListNode getHead() {
return head;
}
}
public class ListNode {
public int value;
public ListNode next;
ListNode(int value) {
this.value = value;
}
}
public class UtilClass{
public static int checkLists(LinkedList list1, LinkedList list){
ListNode head = myList2.getHead();
HashSet<Integer> hashSet = new HashSet<Integer>();
while(head!=null){
hashSet.add(head.value);
head = head.next;
}
head = myList.getHead();
while(head!=null){
boolean b = hashSet.add(head.value);
if(b == true) return head.value;
head = head.next;
}
return -1111;
}
}
source to share
You can use removeAll method. All you have to do is create a method that takes two lists, one of which is the original and the other of the subscriptions, and then returns a list of missing items:
List getMissing(List original, List sub){
original.removeAll(sub);
return original;
}
This is done in quadratic time.
If you really want to make it work in linear time, O (n), then you need to write your own class that wraps your inputs in such a way that there is a flag for each input that controls whether it was added to the sublist. You can also create a class that makes it easy to add and remove items while monitoring the contents of both lists.
source to share
Let N = m + n.
- Add lists. Since they are linked by lists, it is cheap O (1).
- Sort O (N log N) - ArrayList might be better.
- Go through the list and without finding the sequential pair {x, x}, you found the missing one, O (N), since the second list is a subset.
So O (N. log N) .
Since the lists are not ordered, any speedup consists of something like sorting, and it's worth it. So O (N.log N) is great.
If you want O (N) you can do it like this (simplified by using positive numbers):
BitSet present = new BitSet(Integer.MAX_VALUE);
for (int value : sublist)
present.set(value);
for (int value : list)
if (!present.isSet(value)) {
System.out.println("Missing: " + value);
break;
}
It trades memory over time. Of course this answer cannot be accepted as memory is 2 MAX_VALUE , which also initializes / clears the time spent .
Possible <O (N log N) solutions
The most reasonable answer would be to (quasi) sort both lists together. And during sorting, it finds a missing element. Something like selecting a chaotic "median" element and offsetting the shift indices to split lists, split and win.
If the list sizes differ by 1
Then you only have to do the sums for each list, and the difference is the missing value: O (N). Works with overflow.
source to share