rohith2506

// http://www.geeksforgeeks.org/next-greater-element/
// simple stack logic.

int nge(int a[]){
  vector<int> nge;
  stack<int> stk;
  stk.push(a[0]);
  for(int i=1; i<n; i++){
    int next = a[i];
    while( !stk.empty()){

rohith2506

// Converting bst to sorted DLL
// go in in order and and keep track of previous node and make it previous to current node and current node next to this node.
void bsttodll(node *root, node **head){
  if(root == NULL) return ;
  static node *prev = NULL;
  bsttodll(root->left, head);
  if(prev == NULL) *head = root;
  else {
    root -> previous = prev;
    prev -> next = previous;

rohith2506

// diameter of binary tree
// consider a root --> diameter of a tree = max(if path goes through that root, if path does not go through that root)
// so diamter = max(lh+rh+1, max(ld,rd));

int diameter(node *t){
  if(t != NULL){
    int lh = height(t -> left);
    int rh = height(t -> right);
    
    int ld = diameter(t -> left);

rohith2506

// Use parititon method of quick sort 

void quick_sort(vector<int> v){
  int i=-1;
  for(int j=0; j<n; j++){
    if(a[j] < 0){
      i++;
      swap(a[i],a[j]);
    }
  }

rohith2506

// Using deque
void max_slid_window(vector<int> v){
  deque<int> q;
  for(int i=0; i<k; i++){
    while(!q.empty() && v[i] >= v[q.back()])
      q.pop_back();
    q.push_back(i);
  }
  
  for(int i=k+1; i<n; i++){

rohith2506

// THIS IS IMPORTANT. 
// Using this method from leetcode.
// Let's say A[i], B[j]
// if A[i] < B[j] then kth element will be between i to n and 0 to j. so we dont need to check between 0 to i-1 and j+1 to n
// if A[i] > b[j] then kth element will be between 0 to i and j+1 to n. so we dont need to check between i+1 to n and 0 to j
// if A[j] > B[j] && A[j] < B[j+1] return A[j]
// if B[j] > A[j] && B[j] < A[j+1] return B[j]

So, Algorithm goes like this.

rohith2506

// Median of two sorted arrays.
// http://www.geeksforgeeks.org/median-of-two-sorted-arrays/
void median(A,B,n){
  int m1 = median(A);
  int m2 = median(B);
    
  if(n == 0) return ;
  if(n == 1) return (A[0] + B[0])/2;
  if(n == 2) return max(A[0], B[0]) + min(A[1], B[1])/2;
  

rohith2506

// Merge two sorted arrays
// http://www.geeksforgeeks.org/merge-one-array-of-size-n-into-another-one-of-size-mn/
// Time complexity: 0(m+n)

void merge(A, B){
  int k=0;
  for(int i=m; i<m+n; i++)A[i] = B[k];
  k=0;
  i=0;j=m;
  while(k < (m+n)){

rohith2506

// For eg: 396 --> i=0 => and j = 2 swap(3,6) ==> 693 ==> sort(1..n) => 6 [93] => 639 (this is the required number)
int ngd(n){
  if number is sorted in ascedning order just swap last two digits
  if number is sorted in descending order impossible
  else {
    find the condition a[j] > a[j-1] from last and stop there
    let n1 = a[j]
    find next smallest greater digit than n1
    let n2 = a[i]
    swap(a[j], a[i])

rohith2506

/*
Maintain two heaps. maxheap and minheap
The difference between elements in both heaps is atmost 1.
if elements in both heaps are equal, then take the average of two root elements of two heaps.
else return the root element of max heap.
if diff of elements is more than 1, then add those root elements in max heap to minheap and adjust maxheap.
voila, you will get your answer.
for heap:- https://github.com/rohspeed/Algo-world/blob/master/dsa_easy/heap_sort.cpp
pseudo code
*/