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:

	/*************************************************************************
	> File Name: Maximum Element.cpp
	> Author: Rohit Mourya
	> Blog: https://mouryarohit.blogspot.in/
	> Created Time: Mon April 24 2017
	************************************************************************/
	#include <cmath>
	#include <cstdio>
	#include <vector>
	#include <iostream>
	#include <algorithm>
	#include<stack>
	using namespace std;
	int main() {
	int t,q,n;
	stack<int>st1;
	stack<int> auxSt;
	cin>>t;
	while(t>0) {
	cin>>q;
	if(q==1) {
	cin>>n;
	// Insert first element in both the stack
	if(st1.empty()) {
	st1.push(n);
	auxSt.push(n);
	}
	// Insert greater element in auxSt by comparing current element and top element
	else {
	int n2 = auxSt.top();
	auxSt.push(max(n2,n));
	st1.push(n);
	}
	}
	// pop element from both the stack
	else if (q==2) {
	if(!st1.empty()){
	st1.pop();
	auxSt.pop();
	}
	} else {
	// print the maximum element.
	cout<<auxSt.top()<<endl;
	}
	--t;
	}
	return 0;
	}
	/*
	Input: t --> no of operations
	q --> type of query: 1 for push, 2 for pop and 3 for printing max element
	Sample Input:
	10
	1 97
	2
	1 20
	2
	1 26
	1 20
	2
	3
	1 91
	3
	Output:
	26
	91
	*/

view raw Maximum Element.cpp hosted with ❤ by GitHub

 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:

	<!--************************************************************************
	> File Name: creatingListOfRecords.page
	> Author: Rohit Mourya
	> Blog: https://mouryarohit.blogspot.in/
	> Created Time: Mon April 24 2017
	************************************************************************-->
	<apex:page controller="creatingListOfRecordsController">
	<apex:form >
	<apex:pageBlock title="Creating List Of Expense Records" id="block">
	<apex:pageMessages ></apex:pageMessages>
	<apex:pageBlockButtons location="top">
	<apex:commandButton value="Add Row" action="{!addRow}" reRender="table" immediate="true"/>
	<apex:commandButton value="Save" action="{!saving}" />
	</apex:pageBlockButtons>
	<apex:pageBlockTable value="{!expenseWrapperList}" var="page" id="table">
	<apex:column headerValue="Name">
	<apex:inputField value="{!page.expense.name}"/>
	</apex:column>
	<apex:column headerValue="Amount">
	<apex:inputField value="{!page.expense.Amount__c}" />
	</apex:column>
	<apex:column headerValue="Action">
	<apex:commandLink value="Delete" action="{!removingRow}" immediate="true" reRender="block">
	<apex:param name="index" value="{!page.counterWrap}"/>
	</apex:commandLink>
	</apex:column>
	</apex:pageBlockTable>
	</apex:pageBlock>
	</apex:form>
	</apex:page>

view raw creatingListOfRecords.html hosted with ❤ by GitHub

Apex Controller:

	/*************************************************************************
	> File Name: creatingListOfRecordsController.cls
	> Author: Rohit Mourya
	> Blog: https://mouryarohit.blogspot.in/
	> Created Time: Mon April 24 2017
	************************************************************************/
	public with sharing class creatingListOfRecordsController {
	public list<ExpenseWrapper> expenseWrapperList{get;set;}
	public Integer counter{get;set;}
	public creatingListOfRecordsController(){
	counter = 0;
	expenseWrapperList = new list<ExpenseWrapper>();
	for(Integer i=0;i<5;i++){
	ExpenseWrapper expenseWrap = new ExpenseWrapper(new Expense__c());
	counter++;
	expenseWrap.counterWrap = counter;
	expenseWrapperList.add(expenseWrap);
	}
	}
	public PageReference addRow(){
	ExpenseWrapper expenseWrap = new ExpenseWrapper(new Expense__c());
	counter++;
	expenseWrap.counterWrap = counter;
	expenseWrapperList.add(expenseWrap);
	return null;
	}
	public PageReference removingRow(){
	Integer param = Integer.valueOf(Apexpages.currentpage().getParameters().get('index'));
	for(Integer i=0;i<expenseWrapperList.size();i++){
	if(expenseWrapperList[i].counterWrap == param ){
	expenseWrapperList.remove(i);
	}
	}
	counter--;
	return null;
	}
	public PageReference saving(){
	list<Expense__c> updateExpenseList = new list<Expense__c>();
	if(!expenseWrapperList.isEmpty()){
	for(ExpenseWrapper expenseWrap: expenseWrapperList){
	updateExpenseList .add(expenseWrap.expense);
	}
	}
	if(!updateExpenseList .isEmpty()){
	upsert updateExpenseList ;
	}
	ApexPages.Message myMsg = new ApexPages.Message(ApexPages.Severity.Info,'Record Saved Successfully.');
	ApexPages.addMessage(myMsg);
	return null;
	}
	public class ExpenseWrapper{
	public Expense__c expense{get;set;}
	public Integer counterWrap{get;set;}
	public ExpenseWrapper(Expense__c expense){
	this.expense= expense;
	}
	}
	}

view raw creatingListOfRecordsController.cls hosted with ❤ by GitHub

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:

	/*************************************************************************
	> File Name: bubblesort.go
	> Author: Rohit Mourya
	> Blog: https://mouryarohit.blogspot.in/
	> Created Time: Mon April 24 2017
	************************************************************************/
	package main
	import (
	"fmt"
	"strconv"
	)
	type student struct {
	rollNo int
	name string
	marks float64
	}
	func main () {
	var stdArr[] student
	stdArr = make([]student, 10)
	for i:=0;i<10;i++ {
	stdArr[i].rollNo = i
	stdArr[i].name = "Student " + strconv.Itoa(i+1)
	stdArr[i].marks = (70.06 + float64(i))
	}
	bubbleSort(stdArr,10)
	fmt.Printf("\nSorted Student details:")
	fmt.Printf("\nRoll No\tName\tMarks\n")
	for i:=0;i<10;i++ {
	printStudeDetails(stdArr[i])
	}
	}
	func bubbleSortTraditional(stdArr[] student,n int) {
	swapped := 1
	for i:=0;i<n && swapped == 1;i++ {
	swapped = 0
	for j:= i+1; j < n;j++ {
	if(stdArr[i].marks < stdArr[j].marks) {
	std := stdArr[i]
	stdArr[i] = stdArr[j]
	stdArr[j] = std;
	swapped = 1
	}
	}
	}
	}
	func bubbleSortModified(stdArr[] student,n int) {
	swapped := 1
	for i:=0;i&lt;n &amp;&amp; swapped == 1;i++ {
	swapped = 0
	for j:= i+1; j &lt; n;j++ {
	if(stdArr[i].marks &lt; stdArr[j].marks) {
	std := stdArr[i]
	stdArr[i] = stdArr[j]
	stdArr[j] = std;
	swapped = 1
	}
	}
	}
	}
	func printStudeDetails(std1 student) {
	fmt.Printf("\n%d\t%s\t%f",std1.rollNo,std1.name,std1.marks)
	}

view raw bubblesort.go hosted with ❤ by GitHub

Time Complexity: O(n)

Space Complexity: O(1)