Introduction
The N Queen Problem is one of the best problem used to teach backtracking and of course recursion. Backtracking is a general algorithm which finds all complete solutions to a problem by building over partial solutions. In this process, the problem might reach to a partial solution which may not result into a complete solution. Such partial solutions are effectively rejected by the backtracking algorithm.
To know more about backtracking please visit the Wikipedia article.
The classic case of N Queen problem
In this problem, you are given an empty chess board of dimensions N *...

Read More
# Algorithms

This category contains all the posts related to Algorithms. For e.g.: Sorting, Hashing, Searching, Tree Traversals, Graph Theory etc.

## Building an autocomplete system using Trie

Introduction
Few days back I wrote a post about the Trie data structure. This post is a continuation to it, and intends to introduce some practical problems which Trie solves. An autocomplete system is a perfect use case.
Many of the websites use this feature to help there users with suggestions & autocomplete. Also, in this post we will define a Trie interface and then work through this problem statement.
An autocomplete system using Trie
As we know from the previous text that a Trie is a tree like data structure which stores words such that the search for a word is proportional to ...

Read More
## Paint Fill Implementation – Image Editing

Introduction
Most of the image editing software like Microsoft paint, Paint.NET, Adobe Photoshop offer features like paint fill. This post is an attempt to define a simple version of the algorithm which is used to implement paint fill. The problem definition goes like this:
There is a grid with dimensions N*M such that each cell of the grid is colored. The paint fill technique allows a user to choose a color to be filled, say K and a cell C(i,j).
If the cell C(i,j) has the same color as K, then do nothing.
If the cell C(i,j) has a color L which is different from K then find all the...

Read More
## Find the Point of Rotation in Sorted Array

Problem Statement
You are given a sorted array. However, there is a problem. Someone just rotated the sorted array by K spaces and we do not know the value of K.
Write a program to find the value of K by which the array is rotated. As the array has millions of numbers, it would be good to have a solution which takes minimal time.
Approach to Find the Point of Rotation
Brute Force
Let us try out my favorite approach, the Brute Force Method. It is quite simple, below are the steps:
Start traversing the array from the beginning
There will be a index in the array where the value sto...

Read More
## Understanding Binary Search Algorithm

Introduction
The problem of searching is very trivial. It goes like this:
There is an array of elements A[1..N] and we need to find the index of a given element in the array. In case the element is not present in the array, we can choose to return a specific value (say -1) which suggests that the element doesn't exist in the array.
Binary Search is a very efficient and interesting searching algorithm. Regular searching algorithms take running time proportional to the size of the input. They are called linear time algorithm O(N) to be asymptotically true.
Binary Search on the other ha...

Read More