Stacking up the concepts of Stacks

Stacks are one of the most common data structures which can be seen to have the most daily life applications. As the term defines stacks can be imagined as a pile of books stacked upon each other. Stacks is a linear LIFO data structure, where the term LIFO defines last in first out. This means the element which is inserted at last will be the first one to go out. This can also be imagined by taking the example of the books pile. If we want to take a book from the middle it will be a little tough to take it out directly as it may lead to other books collapsing, hence to avoid this we start taking a book from the top, which means the book which was inserted at the end was the first to be taken out. The picture given below summarizes all the above information.

Stack and operations supported

To use a stack we need to use :

stack<int> Stack; // in C++ STL

By now we can have an intuition that stacks have majorly two operations

1. Inserting data at the top which is termed as a push operation.
2. Deleting data from the top is termed as pop operation.

Along with these, there are some additional operations supported by C++ STL which are given below:

1. Stack.top(): To get the top element of the stack.
2. Stack.size(): To check the size of the stack. i.e. the number of elements in the stack.
3. Staack.empty(): A boolean function that returns true if the stack is empty and false when the stack is non-empty.
4. Stack.pop(): Removes or pops off the top element from the stack.
5. Stack.push(x): Pushes or inserts x at the top of the stack.

Applications

Now that we have got a picture of what stacks are let’s see their applications in our lives:

1. For expression conversion: The normal expressions which we use in our day to day lives like (a+b) are called infix expressions. These expressions when given to a computer are converted to either postfix or prefix expressions. This is done with the help stacks.
2. Recursion: The major confusion when we are dealing with recursion is when the function calls itself, again and again, how does it remember the sequence and progress of each function? The answer to this is each time a function calls itself it is pushed into a recursion function call stack which stores its progress till now and when each time a function returns a value it is popped of and hence continuing from where the work was left.

Now that we have laid a conceptual base let us solve a problem from LeetCode(Medium).

Problem statement

Merge Intervals - LeetCode

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Approach

Let’s first analyze the question and find the condition when two intervals are merging. Two intervals will merge if they have any common numbers between them. To understand this let’s take an example-

Let’s consider 2 intervals [a,b] and [c,d], these intervals are said to be merging if b ≥ c. Test this condition with the above-given test cases to have better insight. After this, we need to traverse all the intervals and observe how many intervals this condition will follow. To do that the first and foremost thing which we must do is to sort the array based on the first element of the interval. So our approach will be to maintain a stack of intervals and initially push the first interval in the stack. After that we traverse the remaining intervals, if two intervals are found to overlapping then we don't push them in the stack we just update the second element of the interval located on top of the stack to the second element of the current element we are it only if the second element of the interval on top of the stack is less than the current interval’s second element. The moment the overlapping condition fails to satisfy we push the particular interval in the stack and repeat the above instructions until we cover all the intervals.

In the end, we just pop elements from the stack and print them as these are the elements that are non-overlapping.

Why???

That’s because if an interval was found to be overlapping with the interval on top of the stack it wasn’t pushed in the stack at all, instead, we just updated the second element. Hence the only elements remaining in the stack are non-overlapping. This is why we pop the stack elements one by one and print.

Let’s take a look at the code for this approach.

Code

Analysis

In the above approach, we traverse the vector of intervals only once which makes the time complexity as O(n) where n is the number of intervals. Due to the use of stacks in our code, our auxiliary space complexity becomes O(n).

This program can be further optimized to O(1) space complexity but that won’t involve the usage of stacks. Hope this blog cleared your concepts in stacks, please give a clap if you liked the article and don’t forget to suggest any new algorithms for this problem.