Stack | Get Minimum or Maximum Element in O(1) from Stack

The easiest way to achieve this is to create an auxiliary stack and keep pushing minimum ( maximum ) element in it . And to maintain consistency while popping , pop from when auxiliary stack when top elements in both stacks are equal.


Pseudocode :

Stack myStack = new Stack();
Stack maxStack = new Stack ();

void push(int data )
{
    if ( maxStack.isEmpty() || maxStack.peek() < data)
                  maxStack().push(data);

   myStack.push(data);

}

int pop ()
{
          int num = myStack.pop();
        if( ! maxStack.isEmpty() && maxStack.peek() == num )
                      return maxStack.pop();
        return num;
}

What is more important than Performance of code ?

Well you might be amazed , if you are new to industry , that there are actually many factors which have more priority over performance.You should truely consider these aspects before you starts writing yours best efficinent code.

The main domains which have more weight then performance can be as follows in the present context :

Understandability : Writing a very efficient code but its too obfuscated to understand is not a good idea for future reference and documentation.Your next version may be in doom.

Design : Scalability is adhered to proper design , which can be OOPs or Coupling in a MVC frameworks .

Stability : Benchmarking REST APIs and bandwidth can give a detailed idea about performance vs stability .

Security  : As reserachers quotes , this is rising issues since 2000 . User security and privacy is always given top priority against performance .

Features : Living in 2016 , features can save someones life , get you out of emergency or gives you best utility features.

User friendliness : This issue was the most hunting aspect in 90s . Presently you can easily understand the difference between Windows, Macintosh or iOS and Android . This is the most weighted factor when it comes to performance consideration.

Reverse a Linked List Iterative Solution

In Iterative solution for reversing a Linked List  the core idea is as follows :

change link pointers :

next of current to previous
previous to current
current to next of current

Try imagining flow drawing 4 nodes and applying logic from code

Plus in the end  , since ours whole linked list links has been reversed and previous pointer points to last node of actual list given in start,
ours previous pointer holds the new head of reversed list


Node* Reverse(Node *head)
{
  if(head == NULL)
      return head;
   
  Node *prev = NULL  , *temp , *curr = head;
   
    while(curr != NULL)
        {
        temp = curr->next;
        curr->next = prev;
        prev  = curr;
        curr = temp;
    }
   
    head = prev;
    return head;
}

Linked List | Swapping Nodes without swapping data

Node* swapNode(Node* head  , int x  , int y )
{

    if(x == y)
        return ;
       
    Node* prevX = NULL  , *currX  = head, *currY = head , *prevY = NULL  ;
   
    //find xth and yth node
    for(int i = 0 ; i < x ; ++i)
    {
        prevX = currX ;
        currX = currX->next;
    }
    for(int i = 0 ; i < y ; ++i)
    {
        prevY = currY ;
        currY = currY->next;
    }
   
   
    if( currX == NULL || currY == NULL )
        reutrn;
       
       
    //doesnt matter x is smaller or bigger then y
   
        //change head ptr
    if(prevX != NULL )
        prevX -> next = currY;
    else
        head = currY;
       
    if(prevY != NULL )   
        prevY ->next = currX;
    else
        head = currX;
       
   
    //swap next pointers
    Node* temp = currX->next;
    currX->next = currY->next;
    currY->next = temp;
   
    return head;
   
}

LinkedList : Messing with head pointer

During my recent course of practice with LinkedList , i experienced many problems are related to keeping track of right Head pointer of the list . Whether its a Swapping Nodes without swapping data or simple insertion and deletion of nodes.

Pointer :  When dealing with Swapping Nodes , Insertion and Deletion at head , if the pointer to previous Node is NULL  , then it means First Node is  under consideration


This is how I approach :

Node* prevNode = NULL ; 
Node* ptr = head;

for(int i = 0 ; i < position ; ++ i
{
      prevNode = ptr;
      ptr = ptr->next;
}


if( prevNode == NULL )
{
     //  manipulate head pointer here
}

Checkout Swapping Nodes without swapping data for a real life problem