Sorting algorithms like merge sort, quicksort, insertion sort, heap sort, etc., determine sorted order based on comparison operations. We call such algorithms comparison sort. The tightest lower bound on the number of comparisons performed by comparison based sorting is O(nlogn). In this blog, we have used a decision tree model to prove this.

Divide and conquer is a recursive problem solving approach in data structure and algorithms that divides a problem into smaller subproblems, recursively solves subproblems, and combines subproblem solutions to get the solution of the original problem. So, there are three steps of the DC method: divide, conquer and combine.

In recursive dfs traversals (preorder, inorder and postorder), output depends on the order in which we process the root node. Algorithm is simple and easy to visualize! The critical question is: How do we implement these traversals without using recursion? The answer is: We use stack to simulate a recursive dfs traversal into an iterative dfs traversal.

There are three types of recursive tree traversals: preorder, inorder and postorder. This classification is based on the visit sequence of root node 1) Preorder traversal: root is visited first 2) Inorder traversal: root is visited after left subtree 3) Postorder traversal: root is visited last. These are also called depth first search or DFS traversal.

AVL Trees is a height-balanced BST named after its inventors, Adelson-Velsky and Landis. This is a variation of binary search trees, also known as self-balancing BST. The property of AVL Trees: The absolute difference of height between left and right subtree is at max 1, which could help us to perform bst operations in O(logn) time complexity.

A Fenwick tree is a data structure that efficiently updates elements and calculates prefix sums in an array. It takes O(logn) time for both updates and range sum queries. Fenwick tree is also called binary indexed tree (BIT), which was first described in the paper titled “A new data structure for cumulative frequency tables” (Peter M. Fenwick, 1994).

Hashing is a technique to map (key, value) pairs into the hash table using a hash function. It uses an array of size proportional to the number of keys and calculates an array index from the key using a hash function. We use hashing/hash tables in several real life applications and solve various coding questions efficiently in data structures.

Heap is a complete binary tree structure where each node satisfies a heap property. We learn two types of heap data structure: 1) Max heap, which satisfies the max heap property, and 2) Min heap, which satisfies the min-heap property. We use heap data structures to implement priority queues and solve several coding problems efficiently.

Binary search tree (BST) is a sorted binary tree, where key stored in each node must satisfy the binary search tree property: 1) Keys in the left subtree ≤ Node key 2) Keys in the right subtree ≥ Node key 3) Both subtrees must be binary search trees. In this blog, we have discussed the key properties, operations and differences of BST with a hash table.

The root of the binary search tree and a key k is given. Write a program to insert key k into the binary search tree. Note: BST structure will change after the insertion. So we need to perform insertion in such a way that the BST property continues to hold. In this blog, we have discussed recursive and iterative implementations of insertion in BST.

We start searching from root node and traverse a path downward in binary search tree. For each node in the path, compare target key k with the node key. If equal, search is successful. If k < node key, go to the left subtree. Similarly, if k > node key, go to the right subtree. In this blog, we have discussed recursive and iterative implementations of searching in BST.

We have explained these concepts related to complexity analysis in data structures and algorithms: 1) What is time complexity? 2) Why time complexity analysis important? 3) Assumptions for performing analysis of algorithms 4) Steps to analyze time complexity 5) How do we calculate algorithm time complexity in terms of big-O notation? Etc.

There can be several reasons to learn data structures and algorithms: 1) An algorithm is a technology which helps us to improve performance by a huge margin, 2) Data structures are at the core of several library functions and APIs, 3) DSA is important for cracking the coding interview for top tech companies, 4) Algorithms are beautiful.

This is a complete step by step guide to master data structures and algorithms and crack the coding interview. In this blog, we have highlighted: 1) Syllabus for coding interview 2) List of best resources for learning dsa 3) How to prepare learning and coding interview preparation plan? 4) Critical tips to prepare for a dsa interview.

Learn design, implementation, analysis and comparison of bubble sort, selection sort and insertion sort. In data structures and algorithms, these are one of the fundamental sorting algorithms to learn problem-solving using incremental approach with the help of nested loops. All have the same worst case and average case time complexity.

Level order traversal accesses nodes in level by level order. This is also called breadth first search or BFS traversal. Here we start processing from the root node, then process all nodes at the first level, then process all nodes at the second level, and so on. In other words, we explore all nodes at the current level before going to nodes at the next level.

Definition of an algorithm: Algorithm is a step-by-step procedure to transform a given input into the desired output. A good algorithm must be correct, efficient and easy to implement. In simple words, learning properties and real life applications of an algorithm is essential for building high-performance software and cracking the coding interview.

Recursion means solving the problem using the solution of smaller sub-problems. This blog will explain these critical concepts: 1) What is recursion? 1) How recursion works in programming? 2) Advantages and disadvantages of recursion 3) Steps to solve problems using recursion? 4) Difference between recursion and iteration? Etc.

Counting sort is a stable sorting algorithm that works in O(n) time and space complexity when input are integers in the range 0 to k and k = O(n). Instead of comparison, counting sort uses array indexing to determine position of elements. For each element x, it counts values less than x and places x directly into its correct position in the sorted array.

Understanding iteration vs recursion is one of the critical ideas in data structures and algorithms. If we compare iterative vs recursive approaches, one thing is common: Repeated execution of instructions until our task is done. But there are many differences in terms of implementation, code execution, time complexity analysis, etc.

A well-designed code using data structure is just like a design of a good house. So mastering algorithms require a good understanding of data structure definition, classification, types, implementation techniques, key operations, etc. We should also explore various real-life applications to understand the use case of data structures.

What is iteration in programming? Iteration is executing a sequence of code instructions specified times or until a specific condition is true. We implement iteration using the two most common types of loop: while loop and for loop. The idea is simple: Understanding patterns of iterative algorithms is essential for mastering DSA problem-solving.

Dynamic Programming is a popular problem solving approach in data structures and algorithms, which solve problems by combining subproblem solutions like divide and conquer. But rather than solving the same sub-problem again, DP solves sub-problems once and stores the calculated value in extra memory to avoid the recomputation.

There are several for and while loop patterns in programming: loop running constant or linear time, loop growing exponentially, loop running on a specific condition, two nested loops, three nested loops, etc. So to design an efficient algorithm and optimize code further, we should learn to analyze time complexity of loop in terms of big-O notation.

Learning analysis of recursion is critical to understand time complexity analysis of recursive algorithms. We will discuss these concepts of recursion analysis: recurrence relations of recursive algorithms, steps to analyze time complexity of recursion, recursion tree method, master theorem to analyze divide and conquer algorithms, etc.

We know that a binary tree is a rooted tree in which each node has no more than two children. We can extend this definition to an n-ary tree. If a tree is rooted in which each node has no more than n children, it is called an n-ary tree. In other words, n ary trees are tree data structures with up to n children nodes for each node present in the tree.

Suffix trees are a compressed version of the trie that includes all of a string's suffixes. It can be used to solve many string problems that occur in text editing, free-text searches, etc. Some popular applications of suffix trees are string search, finding the longest repeated substring, finding the longest common substring, data compression, etc.

We mainly use trie data structure to process strings efficiently. It is a tree where each node represents a prefix or end of a word. The best thing is that the time complexity of trie operations depends on string length, which is independent of number of strings. Applications of trie: Autocomplete search, longest prefix matching, spell checker, etc.

Understanding differences between top down (memoization) and bottom up approach (tabulation) of dynamic programming will help us make critical decisions during problem-solving. One idea is common to both approaches: They use extra memory to store solutions to sub-problems, avoid recomputation and improve performance.

Learning divide and conquer vs dynamic programming is one of the critical ideas in DSA. Both use a similar idea to break problems into subproblems and combine their solutions to get the final solution. There are lot of differences between both approaches in terms of the types of problems they solve, implementation, time and space complexity, etc.

There could be two popular categories of problems that can be solved using dynamic programming: 1) Optimization problem: Here we need to find an optimal solution (minimum, longest, shortest, etc.) from a large solution space 2) Counting problem: Here we need to count different ways to find all occurrences of a combinatorial pattern.

Binary tree is one of the simplest tree data structures where each node has at most two child nodes. In other words, a node in a binary tree can have 0 or 1 or 2 child nodes. In this blog, we have discussed: 1) Key terminologies 2) Types of binary tree 3) Properties of binary tree 4) Linked and array representation 5) Binary tree applications.

In this blog, we will learn how to use segment trees for efficient point and range updates. For point update query, update(idx, val), we need to increment element at index idx from the original array by val, i.e. arr[idx] = arr[idx] + val. For range update query, update(l, r, val), we increment all elements from index l to r from the original array by val.

This blog highlights some popular problem solving techniques for solving coding problems. Learning to apply these strategies could be one of the best milestones in mastering data structure and algorithms and cracking the coding interview. We can categorize these strategies into two categories: Iterative approach and Recursive approach.

Algorithmic thinking is a method for solving data structure and algorithms problems based on a clear definition of the steps logically and repeatedly. The best idea would be to develop this skill independently from learning programming with proper practice and visualization. This could help us learn several problem-solving strategies in coding.

A segment tree is a binary tree data structure such that each node stores information about a range. We use segment trees to efficiently answer multiple range queries on an array like range minimum, range maximum, range sum, etc. Also, it allows us to modify the array by replacing an element or an entire range of elements in logarithmic time.

Why sorting algorithms are important in data structure? There are various reasons: 1) Sorting helps us to learn both iterative and recursive problem-solving approaches, 2) Sorting is one of the best ideas for learning time complexity analysis, code optimization techniques, etc. 3) We can solve several coding problems efficiently by sorting the input data.

A dynamic array is a variable-size data structure which increases array size dynamically as we need them. Dynamic arrays overcome a limitation of static arrays, where we cannot adjust the size in the middle of the code execution. It is implemented as a standard library in programming languages like vector in C++ and ArrayList in Java.

An array is a sequential collection of elements of same data type and stores data elements in a continuous memory location. Each element can be efficiently located by its index, which can be easily calculated by adding an offset to the base address. This blog has discussed various array concepts like array types, operations, properties, etc.

Comparison of sorting algorithms based on different parameters helps us choose an efficient sorting approach. In this blog, we have covered these concepts: 1) What is comparison based sorting? 3) Which sorting is best in terms of time complexity? 3) How to compare sorting algorithms in terms of properties like in-place, stability, etc.?