Program for Next Smaller Element | C++ Solution.

Problem:

You are given an array of integers of size n. Your task is to print the next smaller element for each element present in the given array and if no smaller element is present for any element then print -1 for that element. 

The Next Smaller Element for an array element (x) is the first smaller element on the right side of that element (x) in the array. If you reach the last element of the array in that case you cannot see any element on the right side so in that case print -1 if no Next Smaller Element is present. 

You have to store all Next Smaller Elements in an array of n sizes and print them.   

Input: arr = [ 2, 3, 1, 5, 9, 4 ]
Output: ans = [ 1, 1, -1, 4, 4, -1 ]

Explanation:
For 2, the next smaller element present on the right side of 2 in the array is 1.
For 3, the next smaller element present on the right side of 3 in the array is 1.
For 1, there is no next smaller element so you can print -1.
For 5, the next smaller element present on the right side of 5 in the array is 4.
For 9, the next smaller element present on the right side of 9 in the array is 4.
For 4, there is no element present on the right side of 4 so you can print -1. 

I hope that the problem statement is now clear to you, so let's start thinking about different approaches to solve this problem.

Approach 1: Using two nested loops. 

Starting from the left side of the array, the outer loop will pick each element from the array one by one and the inner loop will check if any smaller element is present for the element picked by the outer loop on the right side of that element. If the smaller element is found then store that element in an array and if no smaller element is found then store -1. 

#include <bits/stdc++.h>
using namespace std;

void nextSmallerElement(int arr[], int n, int ans[])
{
    for (int i = 0; i < n; i++)
    {
        int num = -1;
        for (int j = i + 1; j < n; j++)
        {
            if (arr[j] < arr[i])
            {
                num = arr[j];
                break;
            }
        }
        ans[i] = num;
    }
}

int main()
{
    int arr[] = {2, 3, 1, 5, 9, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    int ans[size];

    nextSmallerElement(arr, size, ans);
    for (int i = 0; i < size; i++)
    {
        cout << ans[i] << " ";
    }
}

Output:

1 1 -1 4 4 -1

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Approach 2: Using Stack Data Strcuture.

As you can see that the above approach of solving the problem using two nested loop is not a good approach for solving this problem because it increases your time complexity to O(n^2). You can more efficiently solve the problem using Stack data structure and its property. 

Create a Stack and push -1 initially and now -1 is present at the top of stack. Now approach the given array element from the right hand side and whenever you pick one element x , check the topmost element of the stack. If top element is smaller than the element x you just picked, store the topmost element of stack into your ans array and push the picked element x. 

If you get a situation in which the topmost element is not smaller than element x start popping out elements from the stack until a topmost element smaller element than x. When you find that element, store that element into ans array and push the x into the stack.

#include <bits/stdc++.h>
using namespace std;

void nextSmallerElement(int arr[], int n, int ans[])
{
    stack<int> st;
    st.push(-1);
    for (int i = n - 1; i >= 0; i--)
    {
        int curr = arr[i];
        while (st.top() >= curr)
        {
            st.pop();
        }
        ans[i] = st.top();
        st.push(curr);
    }
}
int main()
{
    int arr[] = {2, 3, 1, 5, 9, 4};
    int size = sizeof(arr) / sizeof(arr[0]);
    int ans[size];

    nextSmallerElement(arr, size, ans);
    for (int i = 0; i < size; i++)
    {
        cout << ans[i] << " ";
    }
}

Output:

1 1 -1 4 4 -1 

• Time Complexity: O(n)
• Space Complexity: O(n)

So I hope you understand both approaches clearly and now you can solve more such coding-related problems using these approaches. You can use the comment section below to ask any questions related to the post.

Stack STL Container in C++.

Stack is a Linear Data Structure that is based on LIFO (Last In First Out) principle and we also have a Stack container class in C++ STL (Standard Template Library) that is implemented based on the same LIFO principle. 

When you use STL Stack, you don't have to worry about the implementation part of the stack operations like push(), pop(), top(), and empty() because in STL Stack all these operations are already provided in the form of a member function. You can directly use these member functions inside your program without thinking about the implementation part. 

Important Stack STL member functions:

• push(): It is used to insert an element at the top end of the Stack.
• pop(): It is used to delete the topmost element of the Stack.
• top(): It returns the topmost element present in the Stack. This function just returns the value present on the top it does not remove that element from the Stack.
• empty(): It is a boolean function that will return true if Stack is empty else it will return false.
• size(): It is used to get the count of the number of elements present in the Stack.

Syntax: stack<datatype> stackname;

Example: C++ code for STL Stack.

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    stack<int> st;

    st.push(50);
    st.push(40);
    st.push(30);
    st.push(20);
    st.push(10);

    cout << "Element present at the top: " << st.top() << endl;
    // delete top element of the stack
    st.pop();
    cout << "Top element after deletion: " << st.top() << endl;
    if (st.empty())
    {
        cout << "Stack is Empty." << endl;
    }
    else
    {
        cout << "Stack is not Empty." << endl;
    }
    cout << "Number of element present in stack " << st.size() << endl;
}

Output:

Element present at the top: 10      
Top element after deletion: 20      
Stack is not Empty.
Number of element present in stack 4

Stack Implementation using Linked List | C++ Code

You can implement the Stack data structure using a singly Linked List but you have to keep in mind that you have to perform all the Stack operations by following the LIFO (Last In First Out) principle. You also have to remember that all the Stack operations like push(), pop(), pee(), and isempty() must be performed under the constant time complexity of O(1).  

Stack operations using Linked List:

To implement a stack using a linked list, you have to create one top pointer that will always point to the head of the linked list or you can say the topmost node of the stack. Because here, in this case, you are not just going to store the variable inside the stack instead you are going to store the node of the list. All your important operations like push and pop are going to perform from the beginning of the list or you can say at the head (top) of the list. 

Push Operation into Stack

push(): To perform the insert operation into the stack, you have to insert an element at the beginning of the list. When your head (top) is pointing to NULL it means your stack is empty so to insert an element into the stack you have to create one new node with that element and assign the address of this node to the head (top). And whenever you want to add one new element, you can perform insert at the beginning operation on the list. 

Pop operation on Stack.

pop(): To remove the top element of the stack, you can simply delete the first node of the list because it is the topmost element present in the stack and as you know that the head (top) always points to the beginning of the list. After deleting the first node, the head (top) will start pointing to the second node which is now the top element of the stack.

peek(): To get the information about the top element of the stack, you can simply return what value is present in the first node of the list which is pointed by the head (top) pointer. If the head (top) is pointing to NULL it means no element is present in the stack.

isempty(): It is very simple to know if the stack is empty or not, if your head contains a NULL value it means your stack is empty.

There is no condition when the stack gets full when you are implementing Stack using Linked List because the size of the Linked List can increase or decrease at runtime.

Example: C++ code for the Implementation of Stack using Singly Linked List.

#include <bits/stdc++.h>
using namespace std;
class ListNode
{
public:
    int data;
    ListNode *next;
    // constructor
    ListNode(int data)
    {
        this->data = data;
        this->next = NULL;
    }
    // destructor
    ~ListNode()
    {
        int value = this->data;
        if (this->next != NULL)
        {
            delete next;
            this->next = NULL;
        }
        cout << "Pop a Node with value " << value << endl;
    }
};
// function to push element into stack
void push(ListNode *&top, int num)
{
    ListNode *temp = new ListNode(num);
    temp->next = top;
    top = temp;
}
// function to pop element from the stack
void pop(ListNode *&top)
{
    if (top == NULL)
    {
        cout << "Stack is Empty" << endl;
    }
    else
    {
        ListNode *temp = top;
        top = top->next;
        temp->next = NULL;
        delete temp;
    }
}
// function to check topmost element of stack
int peek(ListNode *&top)
{
    if (top == NULL)
    {
        cout << "Stack is Empty" << endl;
        return -1;
    }
    else
    {
        return top->data;
    }
}
// function to print all the element of stack
void printStack(ListNode *&top)
{
    ListNode *temp = top;
    while (temp != NULL)
    {
        cout << temp->data << endl;
        temp = temp->next;
    }
}
// function to check stack is empty or not
bool isEmpty(ListNode *&top)
{
    if (top == NULL)
    {
        return true;
    }
    return false;
}
int main()
{
    ListNode *top = NULL;
    // push elements into stack
    push(top, 20);
    push(top, 30);
    push(top, 40);
    push(top, 50);
    cout << "Element present at the top of stack :";
    cout << peek(top) << endl;
    pop(top);
    cout << "New top after deleting topmost element :";
    cout << peek(top) << endl;
    cout << "Elements present in the stack :" << endl;
    printStack(top);
    if (isEmpty(top))
    {
        cout << "Stack is Empty" << endl;
    }
    else
    {
        cout << "Stack is not Empty" << endl;
    }
}

Output:

Element present at the top of stack :50   
Pop a Node with value 50
New top after deleting topmost element :40
Elements present in the stack :
40
30
20
Stack is not Empty

You can observe that all the stack operations like push(), pop() and peek() are done within constant time complexity O(1) using a singly Linked List.

Stack Implementation using Array | C++ Code

The Stack data structure can be easily implemented using a 1D array. You can easily perform all the basic stack operations like push(), pop(), peek(), and isEmpty() in constant time O(1) without using any loop and by following the LIFO (Last In First Out) principle. 

To implement all the stack operations, you need one fixed-size array and a very important variable name top that always points to the topmost element of the stack data structure. In your case, the top variable is going to hold the index of the top element of the stack. 

• Initially, the top is initialized with a -1 value which means that your stack is empty and if you met a condition when (size of the array - top) is less than 1 then you can say your stack is full.

Stack operations using Array.

push(): It is a function used to insert an element at the top of the stack. 

• Check if the stack is full or not. When (SIZE - 1 == top), "STACK is FULL" you cannot insert any further value to terminate the function.
• If (SIZE-1 is not equal to top), increment the top value by 1 (top++) and initialize arr[top] = value.

pop(): It is a function used to delete an element from the top of the stack.

• Check if the stack is empty or not. When top == -1, "STACK IS EMPTY" there is no element present to delete so terminate the function.
• If top > -1, delete the top element by decreasing the top value by one. (top--).

peek(): It is a function that returns the topmost value present in the stack.

• Check if top == -1, the stack is empty so there is no element present in the stack.
• If top > - 1, return the top value using arr[top]. 

isEmpty(): It is a function to check if the stack is empty or not. If the stack is empty return TRUE else return FALSE.

• If top == -1, return true else return false.

Stack Implementation using Array

Example: C++ code for Implementation of Stack using Array.

#include <bits/stdc++.h>
using namespace std;

class Stack
{
public:
    // integer type pointer
    int *arr;
    int top;
    int size;
    // behaviour
    Stack(int size)
    {
        this->size = size;
        // dynamically allocating memory
        arr = new int[size];

        top = -1;
    }
    // function to push element in stack
    void push(int element)
    {
        if (size - 1 == top)
        {
            cout << "Stack OverFlow" << endl;
        }
        else
        {
            top++;
            arr[top] = element;
        }
    }
    // function to pop element in stack
    void pop()
    {
        if (top == -1)
        {
            cout << "Stack is Empty" << endl;
        }
        else
        {
            top--;
        }
    }
    // function to peek element in stack
    int peek()
    {
        if (top == -1)
        {
            cout << "stack is empty !!" << endl;
            return -1;
        }
        else
        {
            return arr[top];
        }
    }
    // check if stack is empty or not.
    bool isEmpty()
    {
        if (top == -1)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};

int main()
{
    Stack s(5);

    s.push(20);
    s.push(30);
    s.push(40);
    s.push(50);

    cout << "Top Element: " << s.peek() << endl;
    // delete the top element of the stack which is now 50
    s.pop();
    // top element after deleting 50
    cout << "Top Element: " << s.peek() << endl;

    if (s.isEmpty())
    {
        cout << "Stack is Empty !!!" << endl;
    }
    else
    {
        cout << "Stack is not Empty !!!" << endl;
    }
}

Output:

Top Element: 50
Top Element: 40
Stack is not Empty !!!

Implementation of Stack using Array is easy to use but it is not dynamic in nature so we can increase or decrease the size of Stack at runtime. To solve this problem, you can use Linked List for the implementation of Stack because as we know that the size of the Linked List data structure is not fixed.

Stack Data Structure Introduction.

Stack is a Linear Data Structure that follows a LIFO (Last In First Out) principle. 

To understand stack data structure let's take a real-life example of the arrangement of plates as shown below. You can observe that plate 1 is placed at the bottom and plate 2 is placed on top of plate 1 similarly plate 3 is placed on top of plate 2. 

Now if you want to put one more late, the easiest way to arrange them is to put the next plate on top of all the other plates, and similarly, if you want to pick one plate then the easiest way is to pick the topmost plate from the stack of plates. 

You can observe that the plate which you are putting, at last, is present on the top and you have to pick that plate first to take the other plates. So this is the basic idea of the LIFO principle of stack data structure. 

Real-Life use of Stack Data Structure.

• Records of your phone logs use the Stack data structure to store all your call records so you get the most recent call details at the top.
• The browser saves your browsing history using the Stack data structure so you can see most of the details of the most recently visited page at the top.
• For recursive function calls, you have to be sure that your function calls do not each stack overflow exception. 

You can implement the Stack data structure in two different ways, 

• Stack Implementation using 1D Array.
• Stack Implementation using Singly Linked List.

There are basically three important operations that you can perform on the Stack and with the help of these operations on the stack, you can solve many complex coding problems. These operations are:

push(): It is used to push any element inside the given stack. It is the rule of stack data structure that you cannot directly push an element in between or at the bottom of the stack. You can push it on the top of the stack.

Push Operation 

pop(): It is used to remove an element from the top of the stack. You cannot directly remove the middle or last element from the stack.

Pop Operation

peek(): It is used to check which element is present at the top of the stack. It returns the value which is present a the top but it does not perform any changes.

All the above operations, push(), pop() and peek() take constant time O(1)  

(getButton) #text=(Stack Implementation using Array) #icon=(link) #color=(#2339bd)

(getButton) #text=(Stack Implementation using Linked List) #icon=(link) #color=(#2339bd)

Program Reverse a String using Stack in C++

Problem: Given a String, reverse the given string using stack. 

Input: str = "algolesson"
Output: str = "nosselogla"

Input: str = "orange"
Output: str = "egnaro"

Steps to reverse the string using stack.

• Create one empty Stack.
• Push all the characters of the given string one by one into the stack.
• Create a new empty string.
• Add the top character of the stack to the empty string then pop the top character.  
• Repeat the fourth step until the stack gets empty and you will get the reverse of the given string.

Example: C++ Code to reverse a string using stack.

//C++ Program to reverse String using Stack

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    string str = "orange";
    stack<char> sc;
    string s = "";
    //push all the char to the stack
    for (int i = 0; i < str.size(); i++)
    {
        sc.push(str[i]);
    }
    //pop all the char from the stack

    // and add then to new empty string.
    while (!sc.empty())
    {
        s += sc.top();
        sc.pop();
    }
    cout << "Reverser String " << s << endl;
}

Output:

Reverser String egnaro

• Time Complexity: O(n)
• Space Complexity: O(n)

As you can see that we are using extra space to reverse the given string which means that this is not an efficient algorithm because we solve the same problem without using any extra space and without using a stack. 

Example: C++ Code to reverse a string without using extra space and without using stack.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string str = "orange";

    //size of the given string
    int n = str.size();
    
    for (int i = 0; i < n / 2; i++)
    {
        swap(str[i], str[n - 1 - i]);
    }
    cout << "Reverse String " << str << endl;
}

Output:

Reverse String egnaro

Time Complexity: O(n).

Space Complexity: O(1)

Binary Search Algorithm with code in C++.

Binary Search is one the most popular and widely used search algorithms used to search whether a particular element is present in the given sorted array or not. It is much better than the Linear search algorithm because it is much faster.  

Problem: Given a sorted array of integers arr[ ] of size n and a target element x, write a C++ program to search the position of x in the given array.

Input: arr[ ] = {7, 10, 11, 15, 20, 30, 26}   x = 20

Output: 4
x is present at index 4.

Input: arr[ ] = {11, 15, 22, 30, 35, 43, 60, 75, 120}   x = 65

Output: -1
x is not present in the arr[ ].

Binary Search Explanation. 

When you try to find the target element in the given array, the worst-case scenario is that when you have to check each element of the given array and it leads to O(n) time complexity. But when the array elements are arranged in sorted order, you can use this extra information to reduce the time complexity to O(log n). 

• If you use a binary search on 100 elements to find your target, the worst-case scenario would be 10 searches. Can you imagine a huge performance improvement? 😲

You get this huge performance improvement because, for each iteration, you reduce the number of elements you will be looking at in half. The idea is to compare the target element to the middle element of the array. 

• If you find the target element is equal to the middle element, return the position of the middle element and stop.
• If the target element is smaller than the middle element, continue searching on the left side of the middle element. high = mid-1
• If the target element is greater than the middle element, continue searching on the right side of the middle element. low = mid+1
• Repeat all three steps until you find the matching element else return -1.

Example: C++ code for Binary Search Algorithm.

#include <iostream>
using namespace std;

int binarySearch(int arr[], int n, int key)
{ 

    int low = 0, high = n - 1; 

    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        //target is found
        if (arr[mid] == key)
        {
            return mid;
        }
        else if (arr[mid] < key) //target might be present in right half
        {
            low = mid + 1;
        }
        else    //target might be present in left half
        {
            high = mid - 1;
        }
    }
    return -1;
}

int main()
{

    int arr[] = {7, 10, 11, 15, 20, 30, 36};
    // size of given array
    int size = sizeof(arr) / sizeof(arr[0]);
    // target element to be find
    int x = 20;

    int index = binarySearch(arr, size, x);
    if (index == -1)
    {
        cout << "Value is not present in the given array." << endl;
    }
    else
    {
        cout << "Value present at index: " << index << endl;
    }
}

Output:

Value present at index: 4

• Time Complexity: O(log n)
• Space Complexity: O(1)

Important points to note: 

int low = 0, high = n - 1;

low and high work like a boundary and we will be looking at elements inside the boundary to find out the target element x and these boundaries get change with each iteration until we found our target loop gets terminated when low == high.

int mid = (high + low) / 2; //formula 1 
int mid = low + (high - low) / 2; //formula 2

Now, a few of you might be thinking that why we are using formula 2 instead of formula 1 as both the formula is going to give the same result? The answer to this question is to avoid integer overflow as the maximum value the integer datatype can hold is 2147483647.  So when you in case of adding two bigger numbers and try to store them in integer datatype it will give you a wrong answer. 

I believe the remaining part of the code was easy to understand with the help of the above explanation and animation gif. If you have any questions or suggestions related to the post, you can share them with us in the comment section below.

Linear Search Algorithm with code in C++.

Linear Search is a searching algorithm that is also known as a sequential search. It is one of the very popular searching algorithms that is used to search whether an element is present in the given array or not. 

Problem: Given an array of integers arr[ ] of size n and a target element x, write a C++ program to search the position of x in the given array. You can return -1 in the element x is not present in the given array. 

Input arr[ ] = {20, 10, 7, 30, 11, 15, 36} 
x = 11

Output:  4
Element is present at index 4

Input arr[ ] = {5, 10, 8, 30, 12, 70, 25, 19}
x = 15

Output: -1 
Element is not present at any index.

Steps to follow:

• Start from the 0 index element of the given array and start comparing each element with x.
• If you find an index element matches with x, return the index. arr[index]  == x
• If you are unable to find the matching element in the array, return -1.

Example: C++ Program for Linear search.

#include <iostream>
using namespace std;

// Function for Linear Search
int linearSearch(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++)
    {
        if (arr[i] == x)
        {
            return i;
        }
    }
    return -1;
}
int main()
{
    // Elements present in the array
    int arr[] = {20, 10, 7, 30, 11, 15, 36};
    // size of given array
    int size = sizeof(arr) / sizeof(arr[0]);
    // Element x to be search in the array
    int x = 11;
    int pos = linearSearch(arr, size, x);
    if (pos == -1)
    {
        cout << "Element " << x << " is not present in the given array." << endl;
    }
    else
    {
        cout << "Element " << x << " is present at index " << pos << endl;
    }
}

Output:

Element 11 is present at index 4

• Time Complexity: O(n).
• Space Complexity: O(1).

Mostly in real-life applications, we rarely use a Linear search algorithm. We mostly use a Binary search algorithm with time complexity O(log n) which is more efficient than this linear search.