azrarabbani
BAN USERThe following implementation construct the iterator lazily and avoid storing the data before it is accessed. so still O(1)
public class SortedIterator<K extends Comparable> implements Iterator<K> {
private int currentIdx = 0;
private K[][] sortedArrays;
private int size = 0;
private PriorityQueue<SortedNode> q = new PriorityQueue<SortedNode>((a, b) -> {return a.compareTo(b);});
public SortedIterator(K[][] sortedArrays){
this.sortedArrays = sortedArrays;
initIterator();
}
@Override
public boolean hasNext() {
return (currentIdx < size);
}
@Override
public K next() {
K item = null;
if(this.sortedArrays != null && hasNext()) {
SortedNode next = q.poll();
item = next.val;
int arrNum = next.arrNum;
if (next.nextIdx < next.size && this.sortedArrays[arrNum][next.nextIdx] != null) {
q.offer(new SortedNode(arrNum, this.sortedArrays[arrNum][next.nextIdx], next.nextIdx + 1, next.size));
}
currentIdx++;
}
return item;
}
private void initIterator() {
if(this.sortedArrays != null) {
int n = this.sortedArrays.length;
for (int i = 0; i < n; i++) { //O(n)
int m = this.sortedArrays[i].length;
if (m > 0 && this.sortedArrays[i][0] != null) {
q.offer(new SortedNode(i, this.sortedArrays[i][0], 1, m));
}
size += m;
}
}
}
public static void main(String[] args) {
Integer[][] arr = {{1 ,2, 8}, {6,9,10}, {1, 4, 5 , 12 }};
SortedIterator<Integer> it = new SortedIterator(arr);
while(it.hasNext()) {
System.out.println(it.next()+"");
}
}
private class SortedNode implements Comparable<SortedNode>{
K val;
int size;
int nextIdx;
int arrNum;
SortedNode(int arrNum, K val, int nextIdx, int size){
this.val = val;
this.nextIdx = nextIdx;
this.size = size;
this.arrNum = arrNum;
}
public int compareTo(SortedNode n){
if(n == null) return -1;
if(n.val == null && this.val == null) return 0;
if(n.val == null && this.val != null) return -1;
if(n.val != null && this.val == null) return 1;
return this.val.compareTo(n.val);
}
}
}
sorry forgot to mention the class name /dsalgoazra/dsalgorithm/src/algorithm/DP/FindMaximumTeams.java
- azrarabbani February 12, 2019check my solution at github
/dsalgoazra/dsalgorithm
it has better time complexity.
that is 5
- azrarabbani February 11, 2019The space complexity is O(1) since the priority queue will keep only 1 item of each list at a time that should be negligible as compared to O(n).
e.g. if there are 3 lists {2, 3, 7, ,6} , {1,3,5} , {8,7,9}
In this scenario: There will be 3 items in the priority queue at max at a time, which will decrease to 2 as soon as we poll the third element of the 2nd list that is
public class DetectSmallestCycleInGraph {
private int shortestCycleSize = Integer.MAX_VALUE;
private Graph.Vertex[] shortestCycle;
Graph.Vertex[] findSmallestCycleDirectedGraph(Graph g) {
for(Graph.Vertex v :g.getVertices()) {//O(V)
Stack<Graph.Vertex> vertexStack = new Stack<>();
v.setVisited(false);//marking it unvisited so it can be traversed
boolean hasCycle = hasCycleDirectedGraph(v, vertexStack);
if(hasCycle) {
if(vertexStack.size() < shortestCycleSize){
shortestCycleSize = vertexStack.size();
shortestCycle = new Graph.Vertex[shortestCycleSize];
vertexStack.toArray(shortestCycle);
}
}
}
return shortestCycle;
}
boolean hasCycleDirectedGraph(Graph.Vertex source, Stack<Graph.Vertex> adjVertex) {
if(source.isVisited()) return false;
source.setVisited(true);
adjVertex.push(source);
for(Graph.Edge adj : source.getEdges()) {//O(A) , where A is adjacent edges to source
if(adj.getTo().isVisited() && adjVertex.contains(adj.getTo())) {//contains causes O(M) where M is the number of vertices on a path from the source node
return true;
} else if(!adj.getTo().isVisited() && hasCycleDirectedGraph(adj.getTo(), adjVertex)) {
return true;
}
}
adjVertex.pop();
return false;
}
public static void main(String[] args) {
int[][] edges = {
{0, 1},
{0, 2},
{2, 1},
{3, 0},
{1, 3},//shortest cycle
{1, 4},
{4, 5},
{5, 6},
{6, 7},
{7, 1}//cycle
};
Graph g = new Graph(edges);
DetectSmallestCycleInGraph da = new DetectSmallestCycleInGraph();
Graph.Vertex[] cycle = da.findSmallestCycleDirectedGraph(g);
System.out.println("\n Shortest cycle : ");
for (Graph.Vertex v : cycle) {
System.out.print(v.getId() + " -> ");
}
}
public class CheckForSubTree<K extends Comparable> {
private static class MultiChildTreeNode<K> {
List<MultiChildTreeNode> children;
K data;
MultiChildTreeNode(K data){
this.data = data;
children = new ArrayList<>();
}
}
private boolean isSubTree(MultiChildTreeNode<K> t1, MultiChildTreeNode<K> t2){
if(t2 == null || t1 == null ) return true;
Stack<MultiChildTreeNode> n1 = new Stack<>();
n1.push(t1);//main tree traversal -> depth first search
Queue<MultiChildTreeNode> matchingQ = new LinkedList<>();//if matches found then convert main tree traversal to breadth first search and move on
Queue<MultiChildTreeNode> n2 = new LinkedList<>();//Breadth First search
n2.add(t2);
boolean found = false;
while(!n2.isEmpty() && !n1.isEmpty()){
MultiChildTreeNode<K> nn2 = n2.poll();
MultiChildTreeNode<K> nn1;
if(found && !matchingQ.isEmpty()){
nn1 = matchingQ.poll();
} else {
nn1 = n1.pop();
}
if(nn2.data.compareTo(nn1.data) != 0) { //on mismatch reset
n2 = new LinkedList<>(); //start over again
matchingQ = new LinkedList<>();
n2.add(t2);
found = false;
} else {
found = true;
for (int i = 0; i < nn2.children.size(); i++) {
n2.add(nn2.children.get(i));
}
for (int i = 0; i < nn1.children.size(); i++) {
matchingQ.add(nn1.children.get(i));
}
}
for (int i = 0; i < nn1.children.size(); i++) {//always add main tree childrenn
n1.push(nn1.children.get(i));
}
}
return found;
}
public static void main(String[] args) {
/**
* F
* / \
* I K
*/
MultiChildTreeNode<String> ff = new MultiChildTreeNode<>("F");
MultiChildTreeNode<String> iff = new MultiChildTreeNode<>("I");
ff.children.add(iff);
MultiChildTreeNode<String> kff = new MultiChildTreeNode<>("K");
ff.children.add(kff);
MultiChildTreeNode<String> t2 = ff;//Subtree to find
//Main tree
MultiChildTreeNode<String> t1 = new MultiChildTreeNode<>("A");
MultiChildTreeNode<String> b = new MultiChildTreeNode<>("B");
MultiChildTreeNode<String> c = new MultiChildTreeNode<>("C");
MultiChildTreeNode<String> d = new MultiChildTreeNode<>("D");
t1.children.add(b);
t1.children.add(c);
t1.children.add(d);
MultiChildTreeNode<String> e = new MultiChildTreeNode<>("E");
MultiChildTreeNode<String> h = new MultiChildTreeNode<>("H");
e.children.add(h);
MultiChildTreeNode<String> f = new MultiChildTreeNode<>("F");
b.children.add(f);
MultiChildTreeNode<String> i = new MultiChildTreeNode<>("I");
f.children.add(i);
MultiChildTreeNode<String> j = new MultiChildTreeNode<>("J");
f.children.add(j);
/**
* A
* / | \
* B C.. D...
* / |
*E.. F
* / \
* I J
* |
* F
* / \
* I K
*/
j.children.add(ff); //commenting out this line should give false otherwise true
MultiChildTreeNode<String> k = new MultiChildTreeNode<>("K");
MultiChildTreeNode<String> g = new MultiChildTreeNode<>("G");
b.children.add(e);
b.children.add(g);
MultiChildTreeNode<String> l = new MultiChildTreeNode<>("L");
c.children.add(k);
c.children.add(l);
MultiChildTreeNode<String> m = new MultiChildTreeNode<>("M");
MultiChildTreeNode<String> n = new MultiChildTreeNode<>("N");
MultiChildTreeNode<String> o = new MultiChildTreeNode<>("O");
d.children.add(m);
d.children.add(n);
d.children.add(o);
CheckForSubTree<String> checker = new CheckForSubTree<>();
System.out.println (checker.isSubTree(t1, t2));
}
public class SortedIterator<K extends Comparable> implements Iterator<K>{
private List<K> sortedList;
private int currentIdx = 0;
public SortedIterator(K[][] sortedArrays){
iterateListOfLists(sortedArrays);
}
@Override
public boolean hasNext() {
return (currentIdx < sortedList.size());
}
@Override
public K next() {
K item = null;
if(currentIdx < sortedList.size()){
item = sortedList.get(currentIdx);
currentIdx++;
}
return item;
}
private class SortedNode implements Comparable<SortedNode>{
K val;
int size;
int nextIdx;
int arrNum;
SortedNode(int arrNum, K val, int nextIdx, int size){
this.val = val;
this.nextIdx = nextIdx;
this.size = size;
this.arrNum = arrNum;
}
public int compareTo(SortedNode n){
if(n == null) return -1;
if(n.val == null && this.val == null) return 0;
if(n.val == null && this.val != null) return -1;
if(n.val != null && this.val == null) return 1;
return this.val.compareTo(n.val);
}
}
private List<K> iterateListOfLists(K[][] arr){
PriorityQueue<SortedNode> q = new PriorityQueue<SortedNode>((a, b) -> {return a.compareTo(b);});
int n = arr.length;
int size = 0;
for(int i=0; i < n; i++){ //O(n)
int m = arr[i].length;
if(m > 0 && arr[i][0] != null) {
q.offer(new SortedNode(i,arr[i][0],1, m));
}
size += m;
}
sortedList = new ArrayList<>(size);
while(!q.isEmpty()) { //O(n + m)
SortedNode next = q.poll();
sortedList.add(next.val);
int arrNum = next.arrNum;
if(next.nextIdx < next.size && arr[arrNum][next.nextIdx] != null) {
q.offer(new SortedNode(arrNum, arr[arrNum][next.nextIdx],next.nextIdx+1, next.size ));
}
}
return sortedList;
}
public static void main(String[] args) {
Integer[][] arr = {{1 ,2, 8}, {6,9,10}, {1, 4, 5 , 12 }};
SortedIterator<Integer> it = new SortedIterator(arr);
while(it.hasNext()) {
System.out.println(it.next()+"");
}
}
}
Not sure why someone would give a -ve vote for this solution. Explanation please?
- azrarabbani February 21, 2019