Queue can be defined as a priority queue where priority decreases with
time. Hence an element inserted later has lower priority and goes to back
of queue. (FIFO)
Stack can be defined as a priority queue where priority increases with
time.Hence an element inserted later has higher priority and
If the matrix is 4-connected, we can use the same matrix.
now we have to find the total number of connected components of a graph.
consider
1 1 1 0 0 1 1 0 1
0 1 1 1 0 0 1 0 0
1 1 0 1 0 1 1 1 0
0 0 0 0 0 0 0 0 1
we can use bfs/dfs to mark the nodes as visited and thus total
Sign each word such that two words having same signature are anagrams of
each other.
The signature for every word can be :- given word in lexicographically
sorted order.
Keep a trie data structure to store all the signatures.
Now every leaf node points to a list having all the words which are
For this we simple need to check if the left subtree and right subtree are
mirror images of each other.
bool isSymmetric(Node root)
{
if(isMirror( root-left, root-right )
return true;
return false;
}
The mirror utility can be implemented as :-
bool isMirror(Node a,Node b)
{
if(!a !b )
Root of a graph can be any node whose in-degree is zero. i.e. there are no
nodes pointing to that node.
It can be found by using O( |V| ) space and O( |E| ) time .
Now we can choose any node whose in-degree is zero if present.
or choose any random node
and itf DFS-tree is the desired tree.
I think adjacency list can be implemented by vector of vector.
vector vectorint Nodes;
The size of vector Nodes is total no of nodes.
Every element of the vector will store all its adjacent edges.
Nodes[i] is a vector containing all the edges adjacent to node i.
So, we can copy the graph easily.
I think a better approach can be :- using suffix array.
Suffix array is an array data structure which stores all suffixes of the
input string, sorted in lexicographical order.
Now we need to consider that substring which is repeated m times.
Now since all the suffixes starting with same
We can consider the 2-d matrix as a heap(also called Young Tableau).
We just need to heapify(Youngify) it k-1times,then the element at 0,0
will be kth smallest element.
This means we need to remove the k-1 smallest elements from matrix and
still maintaining its Row-Col sorted property.
we need to find the amount of water stored on every bar of the histogram.
For this, we need to find two values :-
v1 :- the highest bar to the left - O(n)
v2:- the highest bar to the right - O(n)
amount of the water stored on the current bar is
Res= ( minimum of the two values(v1,v2) -
