Generate all the strings of length n from 0 to k-1.

Objective: Given two numbers, n and k (k>=n), write an algorithm to generate all the strings of length n drawn from 0 – k-1. Example: k = 2, n = 2Output:  0 0      0 1         1 0         1 1 k = 3, n = 2 Output: 0 0         1 0        2 0        0 1         1 … Read more

Graph – Detect Cycle in a Directed Graph using colors

Objective: Given a directed graph write an algorithm to find out whether graph contains cycle or not. Example: Approach: Graph contains cycle if there are any back edges. There are two types of back edges as seen in the example above (marked in red) Edge from a vertex to itself. Self loop. (4-4) Edge from … Read more

Graph – Detect Cycle in an Undirected Graph using DFS

Objective: Given undirected graph write an algorithm to find out whether graph contains cycle or not. Example: Approach: Earlier we have seen how to find cycles in directed graphs. In this article we will solve it for undirected graph. This problem can be solved in multiple ways, like topological sort, DFS, disjoint sets, in this … Read more

Graph – Detect Cycle in a Directed Graph

Objective: Given a directed graph write an algorithm to find out whether graph contains cycle or not. Example: Approach: Graph contains cycle if there are any back edges. There are two types of back edges as seen in the example above (marked in red) Edge from a vertex to itself. Self loop. (4-4) Edge from … Read more

Dynamic Programming – Egg Dropping Problem

Objec­tive:  There are n number of eggs and building which has k floors. Write an algorithm to find the minimum number of drops is required to know the floor from which if the egg is dropped, it will break. Note: One trial is – dropping an egg once from the particular floor. If egg does not … Read more

Nuts & Bolts Problem (Lock & Key problem)

Objec­tive:  Given ‘n’ Nuts and ‘n’ Bolts of different sizes. There is one-to-one mapping between nuts and bolts. Write an algorithm to find all matches between nuts and bolts Note: This problem can also be framed as- Given ‘n’ keys and ‘n’ locks. There is one-to-one mapping between keys and locks, means each lock has a … Read more

Majority Element- Boyer–Moore majority vote algorithm

Objec­tive:  Given an array of integer write an algorithm to find the majority element in it (if exist). Majority Element: If an element appears more than n/2 times in array where n is the size of the array. Example: int [] arrA = {1,3,5,5,5,5,4,1,5}; Output: Element appearing more than n/2 times: 5 int []arrA = {1,2,3,4}; … Read more

Find the element which appears maximum number of times in the array.

Objective: Given an array of integers, write a algorithm to find the element which appears maximum number of times in the array. Example: int [] arrA = {4, 1, 5, 2, 1, 5, 9, 8, 6, 5, 3, 2, 4, 7}; Output: Element repeating maximum no of times: 5, maximum count: 3 Approach: Naive approach: … Read more

Kadane’s Algorithm – Maximum Subarray Problem

Objective:  The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. Example: int [] A = {−2, 1, −3, 4, −1, 2, 1, −5, 4}; Output: contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6. Approach: Naive solution would be … Read more

Dynamic Programming – Coin Change Problem

Objective: Given a set of coins and amount, Write an algorithm to find out how many ways we can make the change of the amount using the coins given.

This is another problem in which i will show you the advantage of Dynamic programming over recursion.

Example:

Amount = 5

coins [] = {1,2,3}

Ways to make change = 5

{1,1,1,1,1} {1,1,1,2}, {1,2,2}, {1,1,3} {2,3}

Approach:

Read more

The Word Break Problem

Objective : Given an string and a dictionary of words, find out if the input string can be broken into a space-separated sequence of one or more dictionary words. Example: dictionary = [“I” , “have”, “Jain”, “Sumit”, “am”, “this”, “dog”] String = “IamSumit” Output: “I am Sumit” String =”thisisadog” Output : String can’t be broken … Read more

Dynamic Programming – Longest Increasing Subsequence

Objective: The longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence in a given array such that all elements of the subsequence are sorted in increasing order. OR Given a array A[1,2,……,n] , calculate B[1,2….m] with B[i]

Backtracking – Knight’s Tour Problem

Objective : A knight’s tour is a sequence of moves of a knight on a chessboard such that the knight visits every square only once. If the knight ends on a square that is one knight’s move from the beginning square (so that it could tour the board again immediately, following the same path), the … Read more

Backtracking – Search a Word In a Matrix

Objective : Given a 2D matrix of characters. Check whether the word exist in the matrix or not. If it exists then print its path. All movements are allowed (right, left, up, down and diagonally). Example: Approach: We will show the path as increment counter   Create a solution matrix of the same structure as … Read more