medium-problems

Shortest path in an unweighted graph

Problem Statement Given the directed, connected and unweighted graph G, a Source and a Destination and the task to find the shortest path possible between two given vertices in the graph. Note: The path does not contain any cycle which means path have finite number of vertices. Example Input Expected Output Path : 0 3 Implementation in Shortest path in an unweighted graph

Nodes are on same path in a tree or Not

Problem Statement Given a tree and two nodes of tree and the task to check whether these two nodes are on the same path from root to the bottom or not. Example Input Node1 = 1 Node2 = 5 Expected Output Yes Approach The idea is to apply Depth First Search on every node. And Nodes are on same path in a tree or Not

Count number of trees in a forest

Problem Statement Given a forest with edge representation, find the number of trees in the forest. Example Input edges = {{0, 1}, {0, 2}, {3, 4}, {4, 5}, {5, 6}} Expected Output 2 Approach The idea is to apply Depth First Search on every node. If every connected node is visited from one source then Count number of trees in a forest

How to detect negative edge weight cycle in a graph ?

Given a directed weighted graph with possibly negative edge weights, how to detect the presence of a negative edge weight cycle in the graph ? What is a negative edge weight cycle ? The weight of a cycle in a graph is the sum of all the edge weights in the cycle for the graph. How to detect negative edge weight cycle in a graph ?

Replace each element of an array by its corresponding rank

Given an array of n elements, replace each element of the array by its corresponding rank. The rank of the lowest element is 1 and the highest element is n. Take a look at the example given below: Solution The easiest way to solve this problem would be to iterate over the array and store Replace each element of an array by its corresponding rank

Snake and Ladder Problem

Problem statement Given a snake and ladder coordinates which represent the actual snake and ladder board, find the minimum number of dice throws required to reach the destination cell from source cell. This problem can be easily solved bu using 0-1 BFS. Example Input Expected Output Implementation in Python

Divide Two Integers | Leet Code

Given two integers dividend and divisor, divide them and output the quotient, without using multiplication, division and mode operator. Note: Both dividend and divisor will be 32-bit signed integers. The divisor will never be 0. Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For Divide Two Integers | Leet Code

Detect Cycle in a Directed Graph

Problem Statement Given the directed, connected and unweighted graph G and the task to check whether the graph contains a cycle or not. Example Input Expected Output No Approach The approach is to use Depth First Traversal to detect a cycle in a Graph. While traversing through the graph if previous node visited node is encountered again Detect Cycle in a Directed Graph

Valid Perfect Square | LeetCode

Given a number N, check if it is a valid perfect square or not. Solution The naive way would be to just iterate over all the integers from 1 to N and check if N is perfect square of one of the integers. However, in the worst case this would lead to a time complexity Valid Perfect Square | LeetCode

Remove Kth Node From End From Linked List | LeetCode

Given a linked list with N nodes, remove the kth node from end and return its head. Bonus: Do it in one iteration. Solution To remove the kth node from the linked list, first step is traversing to the (k-1)th node in the linked list. After that, we just need to rewire the pointers and Remove Kth Node From End From Linked List | LeetCode

[gravityforms id="5" description="false" titla="false" ajax="true"]