Lexicographically next permutation With One swap

Objective: Given an array of integers (in particular order or permutation of a set of numbers), write an algorithm to find the lexicographically next permutation of the given permutation with only one swap.  This problem can also be asked as “Given a permutation of numbers you need to find the next larger permutation OR smallest … Read more Lexicographically next permutation With One swap

Find the number of distinct Islands OR connected components.

Objective: Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of distinct or unique islands. Island: An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Assume all four edges of the grid are all surrounded by water. Given such a grid, write an … Read more Find the number of distinct Islands OR connected components.

Check if Graph is Bipartite – Adjacency List using Depth-First Search(DFS)

Objective: Given a graph represented by the adjacency List, write a Depth-First Search(DFS) algorithm to check whether the graph is bipartite or not. Earlier we have solved the same problem using Adjacency Matrix (Check if Graph is Bipartite – Adjacency Matrix) with Time complexity: O(V2) where V – No of vertices in the graph. In … Read more Check if Graph is Bipartite – Adjacency List using Depth-First Search(DFS)

Evaluation of Prefix Expressions (Polish Notation) | Set 2

Earlier we had discussed how to evaluate prefix expression where operands are of single-digit. In this article, we will discuss how to evaluate prefix expression for any number ( not necessarily single digit.) Prefix notation is a notation for writing arithmetic expressions in which the operands appear after their operators. Let’s assume the below Operands … Read more Evaluation of Prefix Expressions (Polish Notation) | Set 2

Evaluation of Prefix Expressions (Polish Notation) | Set 1

Prefix notation is a notation for writing arithmetic expressions in which the operands appear after their operators. There are no precedence rules to learn. Let’s assume the below Operands are real numbers in real digits. (Later we will Enhance the solution for any number) Permitted operators: +,-, *, /, ^(exponentiation) Blanks are NOT permitted in … Read more Evaluation of Prefix Expressions (Polish Notation) | Set 1

Convert Prefix to Postfix Expression

Objective: Given a Prefix expression, write an algorithm to convert it into Postfix expression. Example: Input: Prefix expression:  + A B  Output: Postfix expression: A B + Input: Prefix expression:  *-A/BC-/AKL Output: Postfix expression: ABC/-AK/L-* Approach: Use Stacks Algorithm: Iterate the given expression from right to left, one character at a time If the character … Read more Convert Prefix to Postfix Expression

Convert Postfix to Prefix Expression

Objective: Given a Postfix expression, write an algorithm to convert it into prefix expression. Example: Input: Postfix expression:  A B +  Output: Prefix expression- + A B Input: Postfix expression:  ABC/-AK/L-* Output: Infix expression: *-A/BC-/AKL Approach: Use Stack Algorithm: Iterate the given expression from left to right, one character at a time If the character … Read more Convert Postfix to Prefix Expression

Convert Postfix to Infix Expression

Objective: Given a Postfix expression, write an algorithm to convert it into Infix expression. Example: Input: Postfix expression:  A B +  Output: Infix expression- (A + B) Input: Postfix expression:  ABC/-AK/L-* Output: Infix expression: ((A-(B/C))*((A/K)-L)) Approach: Use Stack Algorithm: Iterate the given expression from left to right, one character at a time If a character … Read more Convert Postfix to Infix Expression

Convert Prefix to Infix Expression

Objective: Given a Prefix expression, write an algorithm to convert it into Infix expression. Example: Input: Prefix expression: + A B Output: Infix expression- (A + B) Input: Prefix expression: *-A/BC-/AKL Output: Infix expression: ((A-(B/C))*((A/K)-L)) Approach: Use Stacks Algorithm: Iterate the given expression from right to left (in reverse order), one character at a time … Read more Convert Prefix to Infix Expression

Convert Infix to Prefix Expression

Objective: Given an Infix expression, write an algorithm to convert it into Prefix expression. Example: Input: Infix expression – A + B Output: Prefix expression- +AB Input: Infix expression – A+B*(C^D-E) Output: Prefix expression- +A*B-^CDE Approach: Use Stack Operator stack: This stack will be used to keep operations (+, -, *, /, ^) Order of … Read more Convert Infix to Prefix Expression

Max Flow Problem – Ford-Fulkerson Algorithm

Objective: Given a directed graph that represents a flow network involving source(S) vertex and Sink (T) vertex.  Each edge in the graph has an individual capacity which is the maximum flow that edge allows. Flow in the network has the following restrictions- Input flow must match to output flow for each node in the graph, … Read more Max Flow Problem – Ford-Fulkerson Algorithm

Convert Infix to Postfix Expression

Objective: Given an Infix expression, write an algorithm to convert it into Postfix expression. Example: Input: Infix expression – A + B Output: Postfix expression- AB+ Input: Infix expression – A+B*(C^D-E) Output: Postfix expression- ABCD^E-*+ Approach: Use Stacks Operator stack: This stack will be used to keep operations (+, -, *, /, ^) Order of … Read more Convert Infix to Postfix Expression

Evaluation of Infix expressions

Infix notation is commonly used in arithmetic formula or statements, the operators are written in-between their operands. Let’s assume the below Operands are real numbers. Permitted operators: +,-, *, /, ^(exponentiation) Blanks are permitted in expression. Parenthesis are permitted Example: A * ( B + C ) / D 2 * (5 + 3) / … Read more Evaluation of Infix expressions

Merge K sorted Linked List – Using Priority Queue

Objective: Given, K sorted linked list, Write an algorithm to merge all the linked list into one linked list which will be also be sorted. Example: List 1: –>1–>5 List 2: –>4–>8 List 3: –>4–>6–>9 List 4: –>2–>7–>10 Merged Linked List: –>1–>2–>4–>4–>5–>6–>7–>8–>9–>10 Approach: Use Priority Queue Please read Priority Queue and Linked List if needed. … Read more Merge K sorted Linked List – Using Priority Queue

Valid Brackets – Part 2 | Stack Method

Objective: Given a string containing just the characters ( , ) determine if the input string is valid. Example: ()()(()(()))() valid: true )()()( valid: false ()()) valid: false Approach: Earlier we discussed the solution which keeps the count of open and closed parentheses. In this solution we will solve this problem using stack. Using Stack: Initialize a … Read more Valid Brackets – Part 2 | Stack Method