Divide and conquer is a recursive problem-solving approach that divides the problem into smaller subproblems, recursively solves the subproblems, and combines the solutions to the subproblems to get the solution of the original problem.

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

Merge sort is one of the fastest comparison-based sorting algorithms, which works on the principle of the divide and conquer approach. The worst and best case time complexity of merge sort is O(nlogn), and space complexity is O(n). It is also the best algorithm for sorting linked lists.

Iterative and Recursive approaches are important for solving data structures and algorithms problems. An iterative approach is about repeatedly executing some code statements using a loop, and a recursive method involves solving the problem using the smaller sub-problems.

Recursion means solving the problem via the solution of the smaller sub-problem. This blog will answer some critical questions like - what is recursion? What are its advantages and disadvantages? How do you identify recursion problems? What is the difference between recursion and iteration? etc.

A Segment Tree is a data structure used to answer multiple range queries on an array efficiently. Also, it allows us to modify the array by replacing an element or an entire range of elements in logarithmic time. This blog will focus on the build and query operations on segment trees.

Given a 2-dimensional matrix, print the elements in spiral order. We can imagine the spiral traversal as an ordered set of matrix segments with horizontal and vertical boundaries, where both boundaries are reduced by one at each step. This is a good matrix problem to learn problem-solving using iteration and recursion.

To process data stored in a binary tree, we need to traverse each tree node, and the process to visit all nodes is called binary tree traversal. In this blog, we will be discussing three popular recursive tree traversals: preorder, inorder and postorder traversals. These traversals are also called depth-first search traversal or dfs traversal in data structures.

The binary search is one of the fastest searching algorithms, which search a value in the sorted array in an O(logn) time complexity. Here we search a value using divide and conquer by repeatedly dividing the search interval in half. Problem statement: Given a sorted array X[] of n elements, search a given element key in X[]. If the key exists, then return its index in the sorted array. Otherwise, return -1.

Given a singly linked list, write a program to swap every two adjacent nodes and return its head. If the number of nodes are odd, then we need to pair-wise swap all the elements except the last element.

Given a stack, write a program to sort the stack in ascending order. We are not allowed to make any assumptions about how the stack is implemented. The only functions to be used are push(s, x), pop(s), top(s), isEmpty(s).

Given two sorted linked lists, write a program to find the intersections of the linked lists, and return the head of the new Linked List.

Given two numbers n and K and you have to find all possible combinations of K numbers from 1 to n. This is a good interview problem to understand the concept of problem-solving using backtracking and combinatorics.

Write a program to reverse a linked list. A head pointer of a linked list is given and our task to reverse the entire list so that when the resulted list is traversed it looks like we are traversing the original list from tail to head.

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

Quicksort is often the best practical choice for sorting because it works remarkably efficiently on average O(nlogn) time complexity. It is also one of the best algorithms to learn problem-solving using recursion and divide and conquer approach. In this blog, we have covered: 1) How quick sort works recursively? 2) Choosing a correct pivot value in the partition algorithm 3) Best, worst, and average-case time complexity analysis 4) Space complexity and essential properties of the quick sort. Explore and Enjoy!