Track the Maximum Element in a Stack

Aim: To find out the maximum element in stack. There can be n-number of push and pop operations. At a given point of time, goal is to get maximum element from stack in O(1).

Solution:

1. Create two stacks, one for storing elements and the other auxiliary stack for tracking the maximum element.

2. Initially, enter the first element in both the stacks. After that, insert new element in first stack. Compare top element from auxiliary stack with current element and insert whichever is greater.

3. Whenever any element is popped from first stack, pop element from other stack as well.

4. At any point of time if you want to get maximum element, then simply print the top element from the auxiliary stack.

Code:




 The time complexity get the maximum element is O(1).

Insert/Remove rows dynamically in pageblocktable

Many times we come across a scenario where we need to dynamically add new rows to insert new record into the object. Often we try to give pop up to enter new details. However we can also add new empty row dynamically with the help of wrapper classes.

Here is an example which I've developed to overcome above limitation of creating a pop up.

Visualforce Page:

Apex Controller:

Snapshot

Bubble Sort in O(n)

We all know bubble sort is a comparison based sorting algorithm with a time complexity of O(n²). However we can reduce this time complexity to O(n) by simply introducing one flag.

Traditional bubble sort algorithm:

 func bubbleSort(stdArr[] student,n int) {  
      for i:=0;i<n;i++ {  
           for j:= i+1; j < n;j++ {  
                if(stdArr[i].marks < stdArr[j].marks) {  
                     std := stdArr[i]  
                     stdArr[i] = stdArr[j]  
                     stdArr[j] = std;  
                }  
           }  
      }  
 }  

Time Complexity: O(n²)
Space Complexity: O(1)

Above example is sorting students based on their marks using Golang. Above code can be optimized with time complexity as O(n) by simply introducing one flag in a for loop. This flag prevents execution of loop if items are already swapped.

Complete Program:

Time Complexity: O(n)

Space Complexity: O(1)