enriquevr
BAN USER1) put the last item of s in t, in order to do so do (keep track of the number elements of t, those shouldn't be moved)
1.1) move all items from s to t
1.2) pop the top element of t (was last item of s) and store it in v
1.3) return all the items of t and put them in s
1.4) push v in t
1.5) at this point t has the last item of s at its top
2) repeat step 1) as many times as the initial size of s, the idea is that in each step t will grow and s will shrink
3) at the end s will be empty and t will be a copy of s, then move all from t to s, that will reverse s
The time complexity is O(n^2), not sure the if there's a better way to do it
public class StackReversing {
public static <T> Deque<T> reverse(Deque<T> s) {
reverse(s, new ArrayDeque<T>(s.size()));
return s;
}
private static <T> void reverse(Deque<T> s, Deque<T> t) {
for(int i = 0, n = s.size(); i < n; i++) {
putLastItemOnTopOf(s, t);
}
pushAll(t,s);
}
private static <T> void putLastItemOnTopOf(Deque<T> from, Deque<T> to) {
int size = to.size();
pushAll(from, to);
T v = to.pop();
pushAll(to, from, to.size() - size);
to.push(v);
}
private static <T> void pushAll(Deque<T> from, Deque<T> to) {
pushAll(from, to, from.size());
}
private static <T> void pushAll(Deque<T> from, Deque<T> to, int size) {
while (size-- > 0) {
to.push(from.pop());
}
}
}
"If N is huge and the depth of the tree is K, such that K nodes can fit in memory but N nodes can not than the above solution will not work."
agree
"Also note, that time complexity O(N) with space complexity O(N) gives you a total complexity of O(N^2). "
I disagree, perhaps I'm missunderstanding but you can't multiply time complexity by space complexity, it's different things
"traversing the tree K times, each time printing a single depth, is much simpler. "
if we traverse printing a single depth using BSF, we get up-bottom level order, so this doesn't solve the issue, I'm curious to know if there is something that does "backwards BSF" without a helper structure such as the stack,
also note that BSF does O(N) and K = F(N) = Log N, where the base is the number of childs per node
so what you propose is O(K^2*N) = (Log N * Log N * N) therefore O(N) < O(K^2*N)
therefore O(K^2*N) is much worse than O(N)
do BSF, for each level create a linked list and put it in a stack,
then for each element on the stack print out the list, when printing check if next. next == null, if so, terminate the print loop
time complexity = time to build the stack of linked lists + time to pop lists and print them out
time complexity = traverse time + time to pop lists and print them out
traverse time = O(N)
time to pop lists and print them out = O(N)
time complexity = 2 * O(N) = O(N)
space complexity = O(N)
how about a modified version of a count sort where n is the number of records, and a is the array, if we assume that 0 <= a[0:n] <= m, we allocate a new array b of size m that stores the sorted array, and a Hash Set of capacity m that stores an ADT called Solution,
The Solution ADT is a pair of integers, a and b, the idea is that a + b <= k, and more solutions can be from the fact that all Solution(a, 0...b) and Solution(0...b) are also solutions
At the end we will have a Set of Solutions
pseudocode:
for i in 0...n {
b[a[i]] += 1;
if(b[a[i]]) > 0 {
solutions.add(new Solution(b[a[i]], k - b[a[i]]));
}
}
solutions = expandSolutions(solutions);
space complexity would be O(2m)
time complexity would be O(n + expandSolutions) = O(n + k^2)
if k is <<< n then the whole thing could run in O(n)
shouldn't we get a pair of ints for start, and another pair for end?
- enriquevr March 04, 2014