May the lights of Diwali diyas fill your home with wealth, happiness, and everything that brings you joy! Wish you and your entire family a very happy Diwali! May prosperity and happiness fill your life with the shine of diyas and the echoes of chants.

There are many sorting algorithms like merge sort, quick sort, etc to sort a linear data structure.

Of all the sort algorithms Counting sort is better, because time complexity is approx O(n).

But counting sort is only viable when

• values of element lie in the small range.
• the values are non-negative.

Counting sort make use of an extra array also known as counting array.

Consider the following array [5, 9, 11, 10, 15, 12, 2, 8 ,10] — Min = 2 and Max = 15.

Counting array will store the frequency of each element of the original array at the relative index position. For example in our case, the frequency of 2 will be stored at index 0, frequency of 3 at 1, frequency of 4 at 2 and so on.

Finally, after storing the frequency of each element in the counting array, we will rewrite the original array on the basis of the counting array. For example in our case index position 0 has 1 – it means only a single 2 was present in the original array, index position 1 has 0 – it means no 3 was present in the original array.

Implementation of Counting Sort in C++

#include <stdio.h>
#include <stdlib.h>
 
int main()
{
    int arr[] = {5, 9, 11, 10, 15, 12, 2, 8 ,10};
    countingSort(arr,0,8,2,15);
 
    return 0;
}
 
void countingSort(int arr[], int s, int e, int mn, int mx){
    int i,k=0,sizeTemp = mx-mn+1;
    int temp[sizeTemp]; 

    // Initializing all element of counting array with 0
    for(i=0; i<sizeTemp; i++){
        temp[i] = 0;
    }
 
    //Store the frequency of each element of the original array 
    //at the relative position in counting array
    for(i=0; i<=e; i++){
        temp[arr[i]-mn]++;
    }
 
    //Iterate through the counting array and re-write the original array.
    for (i=mn; i<=mx; i++){
        while(temp[i-mn]-->0){
            arr[k++]=i;
 
        }
    }
 
    for(i=0; i<=8; i++){
        printf("%d ",arr[i]);
    }
 
}

Output

2 5 8 9 10 10 11 12 15

Counting sort should only be used when the input lies in the specific range and space is not an issue.

Reference: My Blog

What is N Queen Problem?

We are given N chess’s queens and is asked to place them in the chessboard of size NxN so that no two queens attack/eliminate each other.

A queen can only attack if another queen is either on:

• Same Row
• Same Column
• Same Diagonal (left or right)

Solution using Backtracking

import java.util.Scanner;
 
public class Board {
 
    int chessBoard[][];
    int queens;
 
    public Board(int queens) {
        chessBoard = new int[20][20];
        this.queens = queens;
    }
 
    void displayBoard(){
        int i, j;
        for(i=0; i<queens; i++){
            for(j=0; j<queens; j++){
                if(chessBoard[i][j] == 1)
                    System.out.print(" * ");
                else
                    System.out.print(" - ");
            }
            System.out.print("\n");
        }
        System.out.print("\n");
        System.out.print("\n");
    }
 
    void reset(){
        for(int i=0; i<queens; i++){
            for(int j=0; j<queens; j++){
                chessBoard[i][j] = 0;
            }
        }
    }
 
    boolean isValidPlace(int row, int col){
        int i,j;
 
        //Checking horizontally
        for(i=col; i>=0; i--){
            if(chessBoard[row][i] == 1)
                return false;
        }
 
        //checking left diagonal
        for(i=row, j=col; i>=0 && j>=0; i--,j--){
            if(chessBoard[i][j] == 1)
                return false;
        }
 
        //checking right diagonal
        for(i=row, j=col; i<queens && j>=0; i++,j--){
            if(chessBoard[i][j] == 1)
                return false;
        }
 
        return true;
    }
}
 
public class NQueen {
 
    int queens;
    boolean flag;
    Board board;
 
    public NQueen(int queens) {
        this.flag = false;
        this.board = new Board(queens);;
        this.queens = queens;
    }
 
    void solveNqueen(){
 
        int i;
        //starting from (0,0) of the board
        hasSolution(0,0);
 
        //After running hasSolution() still flag == false
        //It means no Solution
        if(!flag)
            System.out.println("No Solution");
 
    }
 
    boolean hasSolution(int ctr, int colQueen){
 
        //Reached beyond last column
        //Means solution (configuration) found
 
        if(colQueen == queens){
            flag = true;
            board.displayBoard();
            //intentionally returning false to find more possible solution
            return false;
        }
 
        int i,j;
        for(i=ctr; i<queens; i++){
 
            //checking if position is safe
            if(board.isValidPlace(i,colQueen)){
                //setting current value to 1 means placing a queen
                board.chessBoard[i][colQueen] = 1;
                //moving to next column's 1st row
                if(hasSolution(0,colQueen+1))
                    return true;
 
                //backtrack
                //reset to 0 means removing queen
                board.chessBoard[i][colQueen] = 0;
            }
 
        }
 
        //When no row is safe in current column
        return false;
    }
}
 
public class App {
 
    static Scanner in = new Scanner(System.in);
 
    public static void main(String args[]){
        System.out.println("Enter number of Queens");
        int queens = in.nextInt();
 
        NQueen nQueen = new NQueen(queens);
        nQueen.solveNqueen();
 
    }
}

Reference: My Programming Blog