Alex Antonov
BAN USERI understood the problem exactly as Sylvain Reboux:
"next higher node" is "first node that is higher than the current node when traversing further down the linked list"
Ex: if 3->2->4->1->6
then 3 and 2 point to 4, 4 and 1 point to 6.
That problem can be solved in O(n) time and with O(1) space (that is in-place). My idea is:
1) Find the end of the list.
2) Iterate the nodes from the last to the first.
3) For every 'current' node compare it with the 'current->next' node.
a) if 'current->next' is greater than 'current' then 'current->higher' pointer should point to 'current->next'
b) otherwise compare 'current' with 'current->next->higher' then with 'current->next->higher->higher' and so on. Eventually we will find the node that is higher than 'current' node.
To iterate in backward direction we can use a trick. We can populate the higher pointers of each node with pointer to a previous node. That is we effectively create a doubly-linked list. Then we rewrite the higher pointers when we iterate the list in backward direction.
It can be shown that each node will be checked twice at most (by the steps 2 and 3). So the time complexity is O(n).
My implementation:
struct Node {
int val;
Node* next;
Node* high;
};
void Solve(Node* head) {
if (!head || !head->next)
return;
Node* cur = head;
Node* prev = nullptr;
// The trick: find the end of the list and convert the list
// to a doubly-linked list at the same time.
while (cur) {
cur->high = prev;
prev = cur;
cur = cur->next;
}
// Now iterate the list in backward direction and rewrite high
// pointers
cur = prev;
prev = cur->high;
cur->high = nullptr;
cur = prev;
prev = cur->high;
while (cur) {
if (cur->next->val > cur->val)
cur->high = cur->next;
else {
Node* high = cur->next->high;
// that loop will touch each node of list twice in total at most,
// so the time complexity is O(n)
while (high && high->val <= cur->val)
high = high->high;
cur->high = high;
}
cur = prev;
if (cur)
prev = cur->high;
}
}
As I understand the requirement to use "some better DS" implies to achieve O(1) space complexity instead of O(Length(P)) in KMP.
As the problem statement tells nothing about time complexity, the O(n*Length(P)) complexity in worst case should be acceptable. We can use a naive search. It will satisfy the both of the requirements: O(1) space complexity and access to only one char of stream at a time.
The trick here will be to use a prefix of the pattern instead of re-reading the previous characters from the stream, when we know that several first characters of the pattern match a part of the stream. That will help to satisfy the second requirement (access only one char of stream at a time).
This is my solution. (I've not tested it, so it may contains errors):
- Alex Antonov July 08, 2014