dd
BAN USERA different approach: (space utilization: O(n), Time Complexity: O(n))
1) Make a binary search tree or any balanced tree out of the values in given array
2) Get the output of in-order of that tree (to get a sorted array)
3) Find max interval from this sorted array in O(n)
public class MaxRange {
private BST<Integer> bst = new BST<Integer>();
private int[] x;
private Pair<Integer, Integer> ans;
public MaxRange(int[] y) {
x = new int[y.size()];
for (int i = 0; i < x.size(); i++) {
x[i] = y[i];
}
ans = getAnswer();
ans.printPair();
}
private Pair<Integer, Integer> getAnswer() {
for (int i : x) {
bst.add(i);
}
int counter=0;
for (int i : bst.inorder()) {
x[counter++] = i;
}
int start = 0;
int end = 0;
int max = 0;
int i = 0;
while (i < x.size()) {
for (int count = 0, j = i + 1; x[j] = x[j-1] + 1; j++, count++;) {}
if (max < count) {
max = count;
start = i;
end = j;
}
i = j + 1;
}
return new Pair<Integer, Integer>(start, end);
}
private class Pair<Key, Key> {
private Key start, end;
public Pair(Key k1, Key k2) {
this.start = k1;
this.end = k2;
}
public void printPair() {
StdOut.println("["+this.start+","+this.end+"]");
}
}
public static void main(String[] args) {
int[] y = {1,7,4,6,3,10,2};
MaxRange m1 = new MaxRange(y);
}
}
}
- dd August 28, 20131) Remove each element from BST-2 and add it to BST-1. So the space which was being used for BST-2 is free now.
2) Remove each element from BST-1 and make a balanced tree (Red-Black/AVL) out of it.
In this way extra space won't be utilized. The space will be utilized only after making that space free from the other tree.
Time Complexity = O(log(m+n))
Please give suggestions.
What will be the complexity for this solution?
- dd October 16, 2014