DEV Community: Nikhil Vats

Competitive Coding Q1: Min Stack

Nikhil Vats — Fri, 10 Apr 2020 21:04:40 +0000

Question

Design a stack that supports push, pop, top, and retrieving the minimum element in constant or O(1) time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

Note - If you are confused about what O(1)/constant time means, I have written a separate comprehensive post covering the topic time complexity.

Now then, let's get to it!

Approach

What is a stack?

A stack is a linear data structure that follows a particular order in which the operations are performed. A simple example is a stack of plates placed over one another in a canteen. The plate which is at the top is the first one to be removed, i.e. the plate which has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO (Last in first out) order. If you want to learn more about it, take a look at this video -

We will use the inbuilt stack in the C++ STL(Standard template library) rather than implementing it ourselves.

stack data structure has the following functions -

empty() – Returns whether the stack is empty
size() – Returns the size of the stack
top() – Returns a reference to the topmost element of the stack
push(x) – Adds the element ‘x’ at the top of the stack
pop() – Deletes the topmost element of the stack

Problem

All the above operations take O(1) time. Now, in our problem, there's just 1 additional constraint which is we have to keep track of the minimum element also. This poses the following problems -

While pushing we have to update the minimum element in case the new element is less than all the existing ones. This can be done simply by checking whether the newly inserted element is less than the current minimum element, if it is we can simply update the minimum element.
When popping, if the topmost element is minimum, we have to recalculate the minimum element but this recalculation takes O(n) time as we have to loop through all the elements to find the minimum one. To find the next minimum element in O(1) time, we will change the push, top and pop operations.

Solution

Let s be the stack, x be the element to be inserted and minElem be the current minimum element. Occasionally, we will denote the previous minimum element (before it was updated) by prevMinElem.

Push Operation

void push(x) {
1. if(s.empty()) {
2.    s.push(x);
3.    minElem = x;
4. } else if(x < minElem) {     // then x is the new minimum element
5.     s.push(2*x-minElem);
6.     minElem = x;
7. } else
8.     s.push(x);
}

A. In line 5, we push 2*x - minElem and not x, this is to keep track of previous the minimum element as we will see in a minute.
B. Note that, the topmost element i.e. 2*x - minElem is less than x (the new min element) because -
x < minElem (the old one)
=> x - minElem < 0
=> x - minElem + x < x (Add x on both sides)
=> 2x - minElem < x
Hence, now the topmost element of stack is less than minElem.

Pop Operation

void pop() {
1. if(s.empty())
2.    cout<<"Stack empty";
3. else {
4.     int top = s.top();
5.     s.pop();
6.     if(top < minElem)
7.         minElem = 2*minElem - top;
8. }
}

A. In Line 6, we check if the element to be removed is less than the minimum element, this will happen if the last element inserted was the minimum element, so, as explained in push operation above, we stored 2*x - minElem in the topmost element and updated the minElem to store x.

B. Line 7 is the key step if we expand the expression above -
minElem = 2*minElem - (2*x - prevMinElem)
minElem = 2*x - (2*x - prevMinElem)
minElem = prevMinElem
Hence we have updated the minElem to store the prevMinElem.

Top Operation

We have to update the top operation as well because if x was less than minElem, we pushed 2*x-minElem in the stack and stored x in minElem. Hence, we change the top operation in the following manner -

int top() {
1. int top = s.top();
2. if(top < minElem)
3.     return minElem;
4. else
5.     return top;
}

A. In line 2, we check if top < minElem, if it is the case then we return minElem as we know that we pushed 2*x-prevMinElem in the stack (hence top = 2*x - minElem) and x in minElem.
B. If top is not < minElem, then we simply return minElem.

You are welcome to try the problem in your IDE now. If you are stuck anywhere, come back to the blog.

Code

class MinStack {
public:
    stack<int> s;
    int minElem;
    MinStack() {
        cout<<"Stack initialized";
    }

    void push(int x) {
        if(s.empty()) {
            minElem = x;
            s.push(x);
        } else if(x < minElem) {
            s.push(2*x-minElem);  
// push 2*x-minElem to keep track of prevMinElem
            minElem = x;
// update minElem to store x
        } else {
            s.push(x);
        }
    }

    void pop() {
        if(s.empty()) {
            cout<<"Stack empty";
        }
        int top = s.top();
        s.pop();
        if(t < minElem) {
            minElem = 2*minElem-top; // update minElem to prevMinElem
        }
    }

    int top() {
        int t = s.top();
        if(t < minElem)
            return minElem; 
        else
            return t;
    }

    int getMin() {
        return minElem;
    }
};

The hard part is over, take a bow! Let's come to time complexity now. We can easily see that the time complexity for each operation is O(1) since there is no loop, etc. and we are simply comparing numbers and performing basic stack operations that have time complexity O(1).

Drop a comment or tell me on twitter if you liked this article or have any suggestions or reviews.

Merge Sort: Algorithm Analysis

Nikhil Vats — Sat, 28 Mar 2020 22:23:26 +0000

Recap -

Insertion Sort is one of the simplest algorithms for sorting. It sorts a list/array by looping through it and placing each element at its correct position in the sorted array which starts from 0th element and ends at current_position-1.
Pseudocode is an informal way of writing programs that do not require any strict programming language syntax.
Insertion Sort takes linear time to run in the best case (sorted) and quadratic time in the worst (reverse sorted) and average case.

In this article, we will learn about some of the common ways of designing algorithms before moving on to merge sort, its running time and its comparison with insertion sort.

Designing Algorithms

Some of the common ways of designing algorithms are -

Incremental approach: Building the solution one component at a time. Ex - Insertion Sort
Divide and Conquer approach: Breaking the problem into several sub-problems of smaller size (unit size), solving them recursively and finally, combining their solutions to find the solution for the original problem. Ex - Merge Sort

Merge Sort

Merge Sort, being a divide and conquer algorithm includes the following steps -

Divide: Split the n element sequence into two subsequences of n/2 elements each.
Conquer: Recursively, sort the two subsequences by dividing them further into smaller subsequences until we reach atomic subsequences (subsequences containing one element each).
Combine: Merge the two sorted sequences into one sorted sequence repeatedly to find the solution.

Note - In the above steps, sequence means an array/list/etc., we will use these terms interchangeably from now on.

Merge Sort Algorithm

Merge sort algorithm is illustrated below -

MERGE-SORT (A, p, r) 
1.   if p < r                      //check for base case
2.        q ← ⌊(p + r) / 2⌋        //divide
3.        MERGE-SORT (A, p, q)     //conquer
4.        MERGE-SORT (A, q + 1, r) //conquer
5.        MERGE (A, p, q, r)       //combine

Note - For any real number x, we denote the greatest integer less than or equal to x by ⌊x⌋ (read “the floor of x”) and the least integer greater than or equal to x by ⌈x⌉ (read “the ceiling of x”).

Step 1 checks for the base case i.e. checks that the array doesn't contain only one element (p = r) and proceeds only if that's not the case.

Step 2 divides the array into two parts p...q and q+1...r.

Step 3 recursively calls the function MERGE-SORT on the first array (p...q).

Step 4 recursively calls the function MERGE-SORT on the second array (q+1...r).

Step 5 combines the two arrays by calling another function MERGE. The pseudocode for MERGE(A, p, q, r) is given below.

MERGE(A, p, q, r)
    n1 = q - p + 1
    n2 = r - q

    /* create temporary arrays */
    Let L[n1] and R[n2] be new arrays.

    /* Copy data to temporary arrays L[] and R[] */
    for i = 1 to n1
        L[i] = A[p + i]

    for j = 1 to n2
        R[j] = A[q + 1 + j]; 

    /* Merge the temp arrays back into A[p..r]*/
    i = 0; // Initial index of first subarray 
    j = 0; // Initial index of second subarray 
    k = p; // Initial index of merged subarray
    while i < n1 && j < n2  
        if L[i] <= R[j]
            A[k] = L[i]; 
            i++;  
        else
            A[k] = R[j]; 
            j++;  
        k++; 

    /* Copy the remaining elements of L[], if any */
    while i < n1
        A[k] = L[i]; 
        i++; 
        k++; 

    /* Copy the remaining elements of R[], if any */
    while j < n2
        A[k] = R[j]; 
        j++; 
        k++;

Merge Sort Analysis

Analyzing divide and conquer algorithms results in recurrences relation, for example in merge sort -

Divide: D(n) = Θ(1) as dividing takes constant time.
Conquer: solve two subproblems, each of size n/2, which contributes 2T(n/2) to the running time.
Combine: the MERGE procedure on an n-element subarray takes time Θ(n) because we only loop through elements of different arrays, so C(n) = Θ(n).

Hence T(n) = Θ(1) if n = 1 (already sorted so, constant time) and T(n) = 2T(n/2) + Θ(n) if n > 1

Solving this, we get T(n) = Θ(nlogn) i.e. a quasilinear function. Hence, merge sort takes linearithmic/quasilinear running time in the best, average and worst case. We will discuss the different ways of solving it in the next article, for now, just focus on the result.

Merge Sort vs Insertion Sort

Now, let's see why running time is important by comparing insertion sort (running time = c1.n²) with merge sort (running time = c2.nlogn) . Take two computers A and B sorting 10⁷ numbers -

Computer A performs Insertion sort and executes 10-billion instructions per second
Computer A is 1000 times faster than B.
Suppose c1 = 2.
It takes c1.n²/execution speed = 2.(10⁷)² instructions / 10¹⁰ instructions per second
= 20000 seconds
= more than 5.5 hours
If rather we sort 100 million numbers than computer A would take more than 23 days.
Computer B performs Merge sort and executes 10 million instructions per second
Suppose c2 = 50
It takes c2.nlogn/execution speed = 50.10⁷ log 10⁷ instructions / 10⁷ instructions per second
= 1163 seconds
= less than 20 minutes
If rather we sort 100 million numbers than computer B would take less than 4 hours.

Hence, even when the computer performing Insertion sort was 1000 times faster and the constant c1 was also less for Insertion sort, the computer performing Merge sort takes much less time when the number of elements is very large.

That's it for this one. Please comment if there are any mistakes, doubts or suggestions. As I said, we will discuss various ways of solving recurrence relations in the next article to see how we got the running time for merge sort.

Insertion Sort: Algorithm Analysis

Nikhil Vats — Thu, 19 Mar 2020 15:20:55 +0000

Hola, first things first, thanks for making it to this article. The last one was a tough one, no? Just for me? Okay then (^__^)!

Recap -

We analyze space and time complexity of an algorithm to see how efficient it is and whether we should go with it or design a new one according to our needs (the amount of data, the operations we need to perform and so on).
There are three kinds of analysis namely the worst case, best case, and average case.
There are five asymptotic notations -
- Big-Oh: upper bound of an algorithm
- Big-Omega: lower bound of an algorithm
- Theta: lower and upper bound (tight bound) of an algorithm
- Little-oh: upper bound that is not asymptotically tight
- Little-omega: lower bound that is not asymptotically tight

Insertion Sort

Sorting is a very common problem in Computer Science and is asked often in coding interviews and tests. As the name suggests, sorting basically means converting an unsorted input like [1,10,5,8,2] to a sorted output like [1,2,5,8,10], increasing order unless specified otherwise.

Insertion sort is a common way of sorting and is illustrated below -

Credits - GeeksForGeeks
You probably know this but GfG is one of the best sources for learning many topics in Computer Science. So, if you ever feel stuck or if you have a doubt, go read the GfG article for that topic.

Now, let's go through the pseudocode for Insertion Sort but you may ask what is Pseudocode? Here you go.

Pseudocode -

It is an informal way of writing programs that do not require any strict programming language syntax. We describe algorithms in Pseudocode so that people who know any programming language can understand it easily. One important point to note is that in pseudocode, index (of arrays, etc.) generally starts from 1 as opposed to 0 in programming languages. The pseudocode for Insertion Sort is -



1. for j=2 to A.length      
// loop from the second element till the end
2.    key=A[j]               
// store the current element in a variable named key
3.    i=j-1
// start from current position - 1
4.    while i>0 and A[i]>key
// loop until we reach the beginning of array or we find an element less than the key (current element) in the sorted array
5.       A[i+1]=A[i]
// if condition in the step above is true, shift the element right one place
6.       i=i-1
// go to the previous position, then go to step 4
7.    A[i+1]=key
// insert the current element at its correct position in the sorted array

That's it. Simple, eh? If you have any doubts, I would be happy to elaborate in the comments section.

Now, let's analyze the performance of insertion sort, using the concepts we learned in the previous article.

The cost for ith step is ci. The cost for any comment is 0 since it's not performed and is just for the programmer's understanding. Hence, insertion sort is essentially a seven-step algorithm.

Now, steps 1, 2, 4 and 8 will run n-1 times (from second to the last element).

Step 5 will run tj times (assumption) for n-1 elements (second till last). Similarly, steps 6 and 7 will run tj-1 times for n-1 elements. They will run one less time because for each element - before line 8 is executed, while condition (step 5) is checked/executed but steps 6 and 7 ain't as the condition in while statement fails.

Summing up, the total cost for insertion sort is -

Now we analyze the best, worst and average case for Insertion Sort.

Best case -

The array is already sorted. tj will be 1 for each element as while condition will be checked once and fail because A[i] is not greater than key.

Hence cost for steps 1, 2, 4 and 8 will remain the same. Cost for step 5 will be n-1 and cost for step 6 and 7 will be 0 as tj-1 = 1-1 = 0. So cost for best case is -

We can express this running time as an+b where a and b are constants that depend on costs ci. Hence, running time is a linear function of size n, that is, the number of elements in the array.

Worst case -

The array is reverse sorted. tj will be j for each element as key will be compared with each element in the sorted array and hence, while condition will be checked j-1 times for comparing key with all elements in the sorted array plus one more time when i becomes 0 (after which i > 0 will fail, control goes to step 8).

The explanation for the first summation is simple - the sum of numbers from 1 to n is n(n+1)/2, since the summation starts from 2 and not 1, we subtract 1 from the result. We can simplify the second summation similarly by replacing n by n-1 in the first summation.

We can express this worst-case running time as an²+bn+c where a, b and c are constants that depend on costs ci. Hence, running time is a quadratic function of size n, that is, the number of elements in the array.

Average case -

The average case running time is the same as the worst-case (a quadratic function of n). On average, half the elements in A[1..j-1]􏰂 are less than A[j] 􏰂, and half the elements are greater. On average, therefore, we check half of the subarray A[1..j-1], and so tj is about j/2. The resulting average-case running time turns out to be a quadratic function of the input size, just like the worst-case running time.

That's it for today. If you have any reviews/suggestions, please tell them in the comments section. In the next article, we will go through various techniques for finding

Complexity Analysis

Nikhil Vats — Wed, 18 Mar 2020 20:48:15 +0000

Recap

Data structures are used for storing data and organizing data in a way such that the required operations like sorting, inserting can be performed efficiently.
An algorithm is a finite set of instructions designed to perform a specific task.
Data structures and algorithms together make a program.

Complexity Analysis

There are two types of complexity we analyze when we design an algorithm -

Time Complexity tells us how much time an algorithm takes to complete.
Space Complexity tells us how much storage does this algorithm need for completion.

Kinds of time complexity analysis -

1. Worst case

upper bound on running time for any input.
T(n) = maximum time of an algorithm on any input of size n.

2. Average case

Expected running time over all inputs.
T(n) = expected running time of an algorithm over all inputs of size n.

3. Best case

lower bound on running time for any input.
T(n) = minimum time of an algorithm on any input of size n.

Asymptotic Notations

Asymptotic notations are a very important part of this course and it will really haunt you (>_<) if you don't understand them properly. Most of us face difficulties at first in understanding asymptotic notations, in my case, I read class notes, stack overflow, and this book before my mid-semester exam to understand them. The issue is as we move on to the o (little-oh) and w (little-omega) notations, we get confused. So, I have summarised all I have learned from the above resources to explain in the best way possible. Pay attention y'all or maybe take a break and come back with a fresh mind?

The asymptotic notations are of the following five types -

1. O (Big-Oh) notation

O-notation, pronounced "big-oh notation", is used to describe the asymptotic upper bound of an algorithm. Formally, it is defined as:

For a given function, g(n) , we denote by O(g(n)) the set of functions,
O(g(n)) = { f(n): there exist positive constants c and n0 such that
0 <= f(n) <= c.g(n) for all n >= n0 }.

Some common O notations are -

O(1) - constant, independent of size n
O(log n) - logarithmic
O(n) - linear
O(nlogn) = O(logn!) - loglinear, quasilinear or linearithmic
O(n²) - quadratic
O(n^c) - polynomial or algebraic
O(cⁿ) where c > 1 - exponential
O(n!) - factorial

2. Ω (Big-Omega) notation

Ω-notation, pronounced "big-omega notation", is used to describe the asymptotic lower bound of an algorithm. Formally, it is defined as:

For a given function, g(n), we denote by Ω(g(n)) the set of functions,
Ω(g(n)) = { f(n): there exist positive constants c and n0 such that
0 <= c.g(n) <= f(n) for all n >= n0 }.

3. Θ (Theta) notation

We talked about O notation above. The disadvantage of describing the complexity of an algorithm in terms of O notation is that if we say that an algorithm runs in f(n)=O(n²), then that algorithm could actually run in n time.

Here comes the role of Θ notation. Usually, we want to be able to say that an algorithm runs no slower and no faster than a particular function. This is called a tight bound. Hence, we define Θ notation as -

For a given function, g(n), we denote by Θ(g(n)) the set of
functions
Θ(g(n)) = { f(n): there exist positive constants c1 , c2 , and n0 such that 0 ≤ c1.g(n) <= f(n) <= c2.g(n) for all n >= n0 }.

4. o (little-oh) notation

o-notation, pronounced little-oh notation, is used to denote a upper bound that is not asymptotically tight.
Asymptotically tight: We say a bound f(n) = O(g(n)) is asymptotically tight if f(n) = Θ(g(n)), that is, if also g(n) = O(f(n). The bound 2n² = O(n²) is asymptotically tight as n² = O(2n²) also hold, but the bound 2n = O(n²) is not as n² != O(2n) because there is no c for which c.2n >= n² for n>no. So 2n = o(n²) but 2n² != o(n²).
For a given function, g(n), we denote by o(g(n)) the set of functions o(g(n)) = { f(n): for any positive constant c > 0, there exists a constant n0 > 0 such that 0 <= f(n) < c.g(n) for all n >= n0 }.
The implication of this is that g(n) becomes insignificant relative to f(n) as n approaches infinity:

So the main differences between Big O and small O are points 2 and 4 and the fact that there is no equality in the definition of little oh (in point 3, compare with the definition of Big O). Apart from these, some other differences (picked from here) are -

In Big-O, it is only necessary that you find a particular multiplier c for which the inequality holds beyond some minimum n. In Little-o, it must be that there is a minimum x after which the inequality holds no matter how small you make c, as long as it is not negative or zero.
Although somewhat counter-intuitively, Little-oh is the stronger statement. There is a much larger gap between the growth rates of f and g if f ∈ o(g) than if f ∈ O(g).
One illustration of the disparity is this: f ∈ O(f) is true, but f ∈ o(f) is false.
Therefore, Big-Oh can be read as "f ∈ O(g) means that f's asymptotic growth is no faster than g's", whereas little-o can be read as "f ∈ o(g) means that f's asymptotic growth is strictly slower than g's". It's like <= versus <.

5. ω (little-omega) notation

ω-notation, pronounced little-omega notation, is used to denote a lower bound that is not asymptotically tight.
For a given function, g(n), we denote by ω(g(n)) the set of functions ω(g(n)) = { f(n): for any positive constant c > 0, there exists a constant n0 > 0 such that 0 <= c.g(n) < f(n) for all n >= n0 }.
The implication of this is that g(n) becomes insignificant relative to f(n) as n approaches infinity:

We can analyze the differences between little and big omega in a similar manner as done above.

Some relational properties of the notations are given below -

Thanks for bearing me, this was a long one for all of us. I hope you understood. If you have any doubts/suggestions/reviews, please let me know in the comment section. Your one single praise can go a long way in motivating me xD. In the coming articles, we will use the notations described above, so if you are lost about what the use of these notations is, read the next article.

Introduction to DSA

Nikhil Vats — Wed, 18 Mar 2020 14:35:07 +0000

Hey everyone, in this series we will go through the basics of Data Structures and Algorithms. This post is the first article in the series. The series is based on my learnings from the course with the same name taught at BITS Pilani, Rajasthan, India. The series will cover the following topics in no particular order -

Introduction
Linear Structures (Arrays, Linked lists)
Non-Linear Structures (Trees, Graphs)
Sorting and Searching Techniques (including Hashing)
Performance Analysis (Time and Space Complexity)

Most of the content of the course is handpicked from the book Introduction to Algorithms by Cormen (CLRS). I highly recommend reading it if you are stuck at any point. You can find it here (for free!).

In this article, we will cover the basics of Data Structures and Algorithms - the definitions, their advantages, etc.

1. Data Structure -

A Data structure is a way of storing and organizing data so that it can be used efficiently. For example, let's assume that we want to write the names of people along with their phone numbers in a diary. Consider two cases -

We write the names of people followed by their phone numbers starting from page 1 followed by page 2 and so on.
We reserve one page for each letter (A, B, C, D,.., Z) and write the names of people and their phone numbers on the page reserved for the first letter of the first name. For example - Tanya's phone number will be stored on the page reserved for the letter 'T'.

Now the method we choose for writing names depends on our use. If we want to make a phonebook, the second way is probably better since we can search a phone number easily later (go to the page marked 'T' for getting the phone number of Tanya) but if we just want to write 2 or 3 phone numbers method 1 is better.

So the data structure we use helps us to manage and organize our data more efficiently and makes our code cleaner and efficient. Some commonly used data structures are Arrays, Linked Lists, Graphs, Trees, Stack, Queue.
The common operations performed on data structures are Sorting, Merging, Deleting, Inserting, Traversing, Searching.

2. Algorithms -

An algorithm is a finite set of instructions that accomplishes a particular task. It is a high level (human-readable), language-independent description of a step by step process for solving a problem. Algorithms and Data Structures together make a computer program that solves a problem like storing phone numbers of people alphabetically efficiently.

That's it for this one. In the next article, I will talk about Performance Analysis. Please comment if you have any suggestions or requests.

Pretty printing data in console

Nikhil Vats — Wed, 30 Jan 2019 00:00:00 +0000

If you are a frontend developer, you must have spent a considerable amount of time looking at the structure of the complex nested data coming from backend. No one loves going to the browser's console and click on those tiny little arrows only to see 100s of lines of messy data. Read this post to increase your efficiency by learning two better ways of logging data to console.

Tip: Click an image to zoom in.

1. Using console.table()

You can use console.table(data) for pretty-printing the data (array of objects, an array of arrays) in the format of a table.

Note that in Chrome console.table(data) may not work sometimes when the data is just an array of strings or numbers (data is not compound). In that case just use console.table([data]).



// Syntax - 
console.table(data [, columns])

The function takes two parameters -

Data to be pretty-printed. [Mandatory]
An array containing the columns to be included in the output. [Optional]

Example -



// an array of objects, logging only firstName

function Person(firstName, lastName) {
  this.firstName = firstName;
  this.lastName = lastName;
}

var john = new Person("John", "Smith");
var jane = new Person("Jane", "Doe");
var emily = new Person("Emily", "Jones");

console.table([john, jane, emily], ["firstName"]);

Result -

You can also sort the table in ascending or descending order of any field by clicking the arrow in the column headers. The upward arrow in the right corner of the second column indicates that the table is arranged based on the ascending order of first names.

Keep in mind that console.table() is not supported in IE.

2. Using console.log() with JSON.stringify()

You can also use console.log(JSON.stringify(data, undefined, 4)) for pretty-printing the data with whitespaces for readability.

JSON.stringify() takes 3 parameters -

The first parameter contains the data. [Mandatory]
The second one is the replacer parameter which can be an array or a function. This parameter is used for filtering the properties of the object (ex - printing some selected fields only). [Optional]
The third one is the number of spaces to improve the readability of data by formatting it. The max value can be 10. [Optional]

Example -



function replacer(key, value) {
  // Filtering out properties
  if (typeof value !== 'string') {
    return undefined;
  }
  return value;
}

var foo = {foundation: 'Mozilla', model: 'box', week: 45, transport: 'car', month: 7};
console.log(JSON.stringify(foo, replacer,4));

// Alternatively we could have just used console.log(JSON.stringify(foo, ['week', 'month']));