The flood fill problem is a way to fill a region of connected pixels with a new colour, starting from a given pixel in an image. You are given an image represented by an m x n grid of integers, where the image[i] represents the pixel value at position (i, j). You are also given the coordinates of a starting pixel (x, y) and a new colour to use for the flood fill operation.
Given a stack, write a program to sort a stack in ascending order. We are not allowed to make assumptions about how the stack is implemented. The only functions to be used are push(s, x), pop(s), top(s), isEmpty(s). In this blog, we have discussed two approaches: 1) Sorting stack using temporary stack 2) Sorting stack using recursion.
Write a program to find intersection of two sorted linked lists and return the head pointer of the new linked list. Here head pointers of both sorted linked lists are given as input and we shouldn’t do any changes in the structure to generate the output. Note: This is an excellent problem to learn problem-solving using recursion and two pointers in a linked list.
Given a 2-dimensional matrix, write a program to print matrix elements in spiral order. We can imagine spiral traversal as an ordered set of matrix segments with horizontal and vertical boundaries, where both boundaries are reduced by one at each step. Note: This is an excellent problem to learn problem-solving using iteration and recursion.
A head pointer of a singly linked list is given, write a program to reverse linked list and return the head pointer of the reversed list. We need to reverse the list by changing the links between nodes. Note: This is an excellent question to learn problem-solving using both iteration (Three-pointers) and recursion (Decrease and conquer approach).
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.
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.
Binary search is an efficient algorithm to search a value in the sorted array using divide and conquer approach. It compares target value with value at mid-index and repeatedly reduces search interval by half. Searching continues until value is found or subarray size gets reduced to 0 (unsuccessful search). Time complexity of binary search is O(logn).
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.
Merge sort is one of the fastest comparison based sorting algorithms, which works on the idea of divide and conquer approach. Worst and best case time complexity of merge sort is O(nlogn), and space complexity is O(n). This is also one of the best algorithms for sorting linked lists and learning design and analysis of recursive algorithms.
Quicksort algorithm is often the best choice for sorting because it works efficiently on average O(nlogn) time complexity. It is also one of the best algorithms to learn divide and conquer approach. In this blog, you will learn: 1) How quick sort works? 2) How to choose a good pivot? 3) Best, worst, and average-case analysis 4) Space complexity and properties of quicksort.
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.
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.
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.
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.
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.
Given the head pointer of a singly linked list, write a program to swap nodes in pairs and return the head of the modified linked list. If the number of nodes is odd, then we need to pairwise swap all nodes except the last node. Note: This is an excellent problem to learn problem solving using both iteration and recursion in a linked list.
Given two numbers n and K, write a program to find all possible combinations of K numbers from 1 to n. You may return answer in any order. Note: This is an excellent problem to learn problem-solving using the inclusion and exclusion principle of combinatorics and backtracking. We can use similar ideas to solve other problems.
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.