Aditya Chatterjee's Blog, page 164

K-th Smallest element in a row and column wise sorted matrix

In this article, we have discussed how can we find the kth smallest element in a given n x n matrix, in which every row and column is sorted in non-decreasing order.

Table of contents:

Problem StatementBrute force approachUsing min-heap data structureUsing binary searchProblem statement

Problem statement: Find the kth smallest element in a given n x n matrix, in which every row and column is sorted in non-decreasing order.

Example:

K=3, matrix:
15, 25, 31, 43
16, 27, 36, 45
28, 30, 39, 49...

Move negative elements to front of array

This article focuses on the algorithm to move the negative elements of an array to the front. This is a basic problem of rearranging elements in an array. This can be solved by many approaches, this article will explore the two-pointer approach.

Table of content:

Problem statementIdea, Steps to solve it (with step by step example)Time and Space ComplexityImplementationShortcomingsApplicationsProblem statement

Problem statement: move the negative elements of an array to the front

Example:...

Number of Substrings with distinct characters

In this article, we have explored various algorithms that will help us in determining the number of substrings that a string can have with distinct characters.

We will be exploring the following algorithms:

Naive algorithm, with a time complexity of O(n³)Optimized naive algorithm, with a time complexity of O(n²)Optimized algorithm with hash mapping, with a time complexity of O(n)

Table of content:

Understanding the problem(1) Naive algorithm(2) Optimized naive algorithm(3) Optimized algo...

How to approach Dynamic Programming problems? (with example)

In this article, we have explained How to approach a Dynamic Programming problem with an example. The approach depends on the constraints of the problem at hand.

DP problems are one of the most important topics for interviews, and can be mastered only with practice.

For most of the students DP problems are actually easy to understand, but difficult to recognize when and how to apply it to solve a problem.

So how to approach DP problems??

1 : Always start with greedy solution.
2 : If greedy solut...

Minimum Cut Problem [Overview]

In this article, we have covered the basics of Minimum Cut Problem, its applications like Network Reliability, algorithms like Ford-Fulkerson Algorithm to solve it and much more.

Table of ContentsProblem Definition
i. Cut
ii.Minimum CutMinimum Cut ProblemApplications
i.Network Reliability
ii.Image SegmentationAlgorithms
i.Max-Flow Min-Cut Theorem
ii.Ford-Fulkerson Algorithm
iii.Brute Force
iv.Kargers AlgorithmSummaryUnderstanding QuestionsProblem Definition

In order to understand the Mi...

Dynamic Memory Allocation in C++

Dynamic Memory Allocation in C++ is the process of allocating memory while a program is running or at run time rather than at compile time. C++ uses new and delete operator for dynamic allocation and freeing up of memory. In this article, we will discuss about it in detail.

Table of Content:

Why Dynamic Memory Allocation is needed?Stack Memory vs Heap MemoryHow Dynamic Memory is different?How is Dynamic Memory Allocation done?new OperatorAllocation of memory blockInitialization with value...

Implement Binary Tree in Python

In this article, we have explored the strategy to implement Binary Tree in Python Programming Language with complete explanation and different operations like traversal, search and delete.

Table of contents:

Basics of Binary TreeImplementation in Python with ExplanationTraversal operationSearch OperationDeletion operationBasics of Binary Tree

What is Binary Tree?

Binary tree is special type of heirarichal data structures defined using nodes. Basically its extended version of linked list. ...

Time and Space complexity of Quick Sort

In this article, we have explained the different cases like worst case, best case and average case Time Complexity (with Mathematical Analysis) and Space Complexity for Quick Sort. We will compare the results with other sorting algorithms at the end.

Table of Content:

Basics of Quick SortTime Complexity Analysis of Quick SortBest case Time Complexity of Quick SortWorst Case Time Complexity of Quick SortAverage Case Time Complexity of Quick SortSpace ComplexityComparison with other sorting...

2D arrays in C++ (2 ways)

In this article, we have discussed what are 2 Dimensional (2D) arrays and what are the different ways we can initialize them and how we can use them in C++.

Table of content:

Introduction to arrayImplementing array in C++2D arrays using native array2D arrays using array containersAccessing array elements in 2D arrayDifference between Native arrays and Array containersIntroduction to array

Arrays are considered to be one of the basic and useful data structures in any language not just in ...

Reverse Delete Algorithm for MST

In this article, we have explored the Reverse Delete Algorithm for finding Minimum Spanning Tree (MST).

Prerequisite: What is Minimum Spanning Tree?

Table of content:

Introduction to Spanning TreeReverse Delete AlgorithmStep by Step ExampleTime and Space ComplexityImplementation of Reverse Delete AlgorithmApplication of Reverse Delete AlgorithmIntroduction to Spanning Tree

Let's get started with Spanning Tree.
A spanning tree of a graph, is a sub-graph with same number of vertices but wi...