Sort a Single Linked List Using merge sort

Merge Sort:
Merge Sort works on divide and conquer principle. First we have to split the unsorted list to sublist till each sub-lists has only one element, and then merge the sub-lists.

Why QuickSort is not worthy for LinkedList?
As we know Quick sort, average time complexity is O(n2), if we use random quick sort then we can say that the average time complexity is O(nlogn), But in Single link it is too difficult to find a random node. That's the reason Quick sort is not good choice for linkedlist.


Code Implementation:

public static LinkList<Integer> mergeSort(LinkList<Integer> list) {
        if (list != null && list.getNext() != null) {
            LinkList<Integer>[] lists = split(list);
            lists[0] = mergeSort(lists[0]);
            lists[1] = mergeSort(lists[1]);
            return merge(lists[0], lists[1]);
        }
        return list;
    }

    private static LinkList<Integer> merge(LinkList<Integer> linkList,
            LinkList<Integer> linkList2) {
        LinkList<Integer> retval = null;
        if (linkList == null)
            return linkList2;
        if (linkList2 == null)
            return linkList;
        if (linkList.getData() < linkList2.getData()) {
            retval = linkList;
            linkList = linkList.getNext();
            retval.setNext(null);
        } else {
            retval = linkList2;
            linkList2 = linkList2.getNext();
            retval.setNext(null);
        }
        LinkList<Integer> header = retval;
        while (linkList != null && linkList2 != null) {
            if (linkList.getData() < linkList2.getData()) {
                retval.setNext(linkList);
                linkList = linkList.getNext();
                retval = retval.getNext();
                retval.setNext(null);
            } else {
                retval.setNext(linkList2);
                linkList2 = linkList2.getNext();
                retval = retval.getNext();
                retval.setNext(null);
            }
        }
        if (linkList2 != null) {
            retval.setNext(linkList2);
        }
        if (linkList != null) {
            retval.setNext(linkList);
        }
        return header;
    }

    @SuppressWarnings("unchecked")
    private static LinkList<Integer>[] split(LinkList<Integer> list) {
        if (list == null || list.getNext() == null) {
            return (LinkList<Integer>[])(new LinkList<?>[] { list, null});
        }
        LinkList<Integer> slow = list;
        LinkList<Integer> fast = list.getNext();
        while (fast != null) {
            fast = fast.getNext();
            if (fast != null) {
                fast = fast.getNext();
                slow = slow.getNext();
            }

        }
        LinkList<Integer> second = slow.getNext();
        slow.setNext(null);
        return new LinkList[] { list, second };
    } 

class LinkList<T> {
    public LinkList() {
    }

    public LinkList(T data) {
        this.data = data;
    }
    private T data;
    private LinkList<T> next;

    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public LinkList<T> getNext() {
        return next;
    }
    public void setNext(LinkList<T> next) {
        this.next = next;
    }
   
}



Find the k most frequent words from a file

A file is given to us. which contains words. Our objective is to find k word which occurred most in the file.
There are multiple ways to solve this.

Simplest Way(HashMap): Get all the word and store in the hashmap as key and value would frequency of the word, if word is already present in the HashMap then increment the count.Once processing of the file is done then traverse through the hash map and return the k words with maximum counts.

Trie and Min Heap  : Another approach is, to create a Trie to store the word and maintain a Min Heap of size k. Trie is to search the String but can also stores count of occurrences of words.
Trie and Min Heap are linked with each other by storing an additional field in Trie ‘indexMinHeap’ and a pointer "MyTrieNode" in Min Heap.
Initially  indexMinHeap is -1, means word is not present in the Min Heap Otherwise it shows the index in Min Heap.

How to fill Min Heap:

1.  If word is already is present then, increment the count in MinHeap and call heapify method.
2. If Min Heap is not full(not contains k element), and word is not present then add the node to Min Heap and update its minHeapIndex, and call heapify.
3. If word is not present and Min Heap is full and new word frequency is more than minimum head then replace the top element(index=0) with new word and update the minHeapIndexOf both the words.

Once Processing is done, then traverse through the Min and get the k most frequent word.

TrieNode will look like:

class MyTrieNode {
    char data;
    boolean is_end_of_string;
    Map<Character, MyTrieNode> nodes;
    int frequency = 0;
    int minHeapIndex = -1;

    public MyTrieNode(char data) {
        this.data = data;
        is_end_of_string = false;
        nodes = new HashMap<Character, MyTrieNode>();
    }

    public MyTrieNode children(char data) {
        return nodes.get(data);
    }

    public boolean isChildExist(char c) {
        return children(c) != null;
    }
}

Min Heap Class Code

class MinHeap {
    int size;
    int capacity;
    MyNode[] nodes;
}

class MyNode {
    String word;
    int frequency;

    //This is extra pointer to point to Trie
    MyTrieNode node;
} 


TRIE Class:

class MyTrie {
    MyTrieNode root;
    MinHeap minHeap;

    public MyTrie(int frequency) {
        root = new MyTrieNode(' ');
        this.minHeap = new MinHeap();
        this.minHeap.nodes = new MyNode[frequency];
        this.minHeap.capacity = frequency;
    }

    /*
     * This method to insert the node into the TRIE
     * */
    public void insert(String s) {
        if (s == null || s.trim().length() == 0) {
            return;
        }
        MyTrieNode current = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!current.isChildExist(c)) {
                MyTrieNode node = new MyTrieNode(c);
                current.nodes.put(c, node);
            }
            current = current.children(c);
        }
        if (current.is_end_of_string) {
            current.frequency++;
        } else {
            current.frequency = 1;
            current.is_end_of_string = true;
        }
        insertInMinHeap(s, current);

    }

    /*
     * This method is to insert the word into Min Heap using below rule.
     * 1. If word is already is present then, increment the count in MinHeap and call heapify method.
     * 2. If Min Heap is not full(not contains k element), and word is not present then add the node to Min Heap and update its minHeapIndex, and call heapify.
     * 3.If word is not present and Min Heap is full and new word frequency is more than minimum head then replace the top element(index=0) with new word and update the minHeapIndexOf both the words.
     * */
    private void insertInMinHeap(String s, MyTrieNode current) {
        if (current.minHeapIndex != -1) {
            this.minHeap.nodes[current.minHeapIndex].frequency++;
            minheapify(current.minHeapIndex);
        } else if (this.minHeap.size < this.minHeap.capacity) {
            ++this.minHeap.size;
            MyNode node = new MyNode();
            node.word = s;
            node.frequency = current.frequency;
            node.node = current;
            node.node.minHeapIndex = this.minHeap.size - 1;
            this.minHeap.nodes[this.minHeap.size - 1] = node;
            buildHeap();

        } else if (current.frequency > this.minHeap.nodes[0].frequency) {
            this.minHeap.nodes[0].node.minHeapIndex = -1;
            this.minHeap.nodes[0].node = current;
            this.minHeap.nodes[0].frequency = current.frequency;
            this.minHeap.nodes[0].word = s;
            current.minHeapIndex = 0;
            minheapify(0);
        }
    }

    private void buildHeap() {
        for (int i = (this.minHeap.size - 1) / 2; i >= 0; i--) {
            minheapify(i);
        }

    }

    /*
     * To search any word is the Trie
     * */
    public boolean search(String s) {
        if (s == null || s.trim().length() == 0) {
            return false;
        }
        MyTrieNode current = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!current.isChildExist(c)) {
                return false;
            }
            current = current.children(c);
        }
        return current.is_end_of_string;
    }

    /*
     * This method is to heapify the given and make sure it satisfies the property of the node
     * */
    public void minheapify(int node) {
        int left = (node << 1) + 1;
        int right = (node << 1) + 2;
        int smallest = node;
        if (left < this.minHeap.size
                && this.minHeap.nodes[smallest].frequency > this.minHeap.nodes[left].frequency) {
            smallest = left;
        }
        if (right < this.minHeap.size
                && this.minHeap.nodes[smallest].frequency > this.minHeap.nodes[right].frequency) {
            smallest = right;
        }
        if (smallest != node) {
            int index = this.minHeap.nodes[smallest].node.minHeapIndex;
            this.minHeap.nodes[smallest].node.minHeapIndex = this.minHeap.nodes[node].node.minHeapIndex;
            this.minHeap.nodes[node].node.minHeapIndex = index;
            MyNode temp = this.minHeap.nodes[smallest];
            this.minHeap.nodes[smallest] = this.minHeap.nodes[node];
            this.minHeap.nodes[node] = temp;
            minheapify(smallest);
        }
    }

    /*
     * Traverse through Min Heap and show all words and their frequency
     * */
    public void display() {
        for (int i = 0; i < this.minHeap.size; i++) {
            System.out.println("word\t:\t" + this.minHeap.nodes[i].word
                    + "\t\t\t\tfrequency\t:\t" + this.minHeap.nodes[i].frequency);
        }
    }
}


Main/Test Class 

public class TrieForOccurenceOfString {
    public static void main(String[] args) throws IOException {
      
        File file=new File("Path of input file"/input.txt");
        BufferedReader reader=new BufferedReader(new FileReader(file));
         int k=5;
        MyTrie t = new MyTrie(k);
        String ss=null;
        while((ss=reader.readLine())!=null){
            String[] array=ss.split(" ");
            for (int i = 0; i < array.length; i++) {
                t.insert(array[i]);
            }
        }
        reader.close();
    
        t.display();
      
    }
}

Level Order Binary Tree Traversal(BFS)

Please read Tree Introduction before proceeding.

I have already explained how to do following Tree Traversal in java.

1. Pre-Order
2. Post Order
3. In Order.

Today, Lets discuss how to do level order(BFS) Tree Traversing

In the above Example, There are 4 levels. At level 1, there is one node(root). At level 2, we have 2 nodes, node 2 and 3. At level 3, we have 4 nodes,  node 5,6,4 and 7,  and At level4, we have 3 nodes, node 9,8 and 10.
If we do level order traversing for above tree then output would be: 1,2,3,5,6,4,7,9,8,10.

                                                      Before moving to solution, we have to understand what data structure should be used here to store the intermediate nodes. To do level order traversing, we have use data structure through which we can retrieve the node in Inserting order or First In First Out(FIFO). Queue works on "First In First Out" Principle. Instead of using stack we have to use queue to do level order traversing.
          
Code Implementation(Iterative Approach)method:

public void levelOrderTraversing(BinaryTree root){
      if(root==null)return;
      LinkedList<BinaryDataTree> queue = new LinkedList<BinaryDataTree>();
      queue.addFirst(root);
      while (!queue.isEmpty()) {
            BinaryDataTree temp = queue.pollLast();
            if (temp.getLeft() != null) {
                    queue.addFirst(temp.getLeft());
             }
            if (temp.getRight() != null) {
                    queue.addFirst(temp.getRight());
             }
            System.out.print(temp.getData() + "   ");
      }      
}




Level Order Traversing(Recursive Approach):

As we all know, If we solve any problem using recursion, it maintains a stack to keep track of method, is called method stack. For level order traversing we need a Data structure which works on the "FIFO".
                  Now Question is, how can we solve this problem using recursion? If we know the height of the tree, Height of tree is nothing but number of levels in tree. We can pass the level along with the child element and keep calling method until we get the all the nodes of a level, and then print them all.


Code Implementation():

void levelOrderPrintingRecusriveWay(BinaryDataTree root) {
        if (root == null)
            return;
        int height = heightOfTreeByRecursiveWay(root);
        for(int i=1; i<=height; i++)
            levelOrderPrintingRecusriveWay(root, i);
    }

    void levelOrderPrintingRecusriveWay(BinaryDataTree root, int level) {
        if(root==null)return;
        if (level == 1) {
            System.out.print(root.getData() + " ");
            return;

        }
        levelOrderPrintingRecusriveWay(root.getLeft(), level - 1);
        levelOrderPrintingRecusriveWay(root.getRight(), level - 1);
    }

public int heightOfTreeByRecursiveWay(BinaryDataTree root) {
        if (root == null)
            return 0;
        int l = heightOfTreeByRecursiveWay(root.getLeft());
        int r = heightOfTreeByRecursiveWay(root.getRight());
        if (l > r)
            return l + 1;
        return r + 1;
    }



Stream API in Java 8

Java 8 Stream API is a new API which got recently introduced in Java Collections. Using Streaming API, Collections can be processed through different APIs. Stream API is introduced to work with LAMBDA Expression.
                         
                                                                     Java 8 Stream is different from Java IO Streaming. IO Stream is a collection of bytes or characters where as Java 8 Stream API is a collection of objects.
Stream Pipeline consists of three types of steps-

• A source
• Zero or more intermediate operations
• A terminal operation

      

Example

int salarySum = employees.stream()
                           .filter(e->e.getCity().equals("A"))
                           .map(i->i.getSalary())
                           .sum();
Table of Contents:

Getting a stream from collection

Stream filter

Stream map

Stream collect

Stream max/min

Stream count

Stream reduce

Stream sum

Getting a stream from collection

Suppose your collection looks like:

List collections=new ArrayList();
collections.add("Bangalore");
collections.add("Mumbai");
collections.add("New York");
collections.add("California");
collections.add("san diego");
collections.add("san francisco");


Stream steam=collections.stream();


Stream filter

Filter is boolean condition, it filters based on the condition. It takes Predicate as a function which internally makes a call to test method

steam.filter(s-> s.startsWith("s"));


Stream map

map method updates or modifies each 'n' every element of the collection. In this example, if we want to update all the city's name with lower/upper case, we can achieve it using map method.

 
steam.map(s->s.toUpperCase());


Stream collect

collect is an terminal Operation. This method collects the data from stream. All the intermediate Operations will be executed as soon as terminal operation gets invoked. Collection Object on which we are getting stream, is final.

List newList=collections.stream()
.filter(s-> s.startsWith("s"))
.map(s->s.toUpperCase())
.collect(Collectors.toList());


Stream max/min

max/min method returns the maximum/minimum element from collection based on the Comparison Condition. max/min takes a Comparator as an argument for comparison In this example if we are comparing the cities based on length of names .

String maxCityByLength=collections.stream()
.map(s->s.toUpperCase())
.max((s1,s2)->s1.length()-s2.length())
.get();

String minCityByLength=collections.stream()
.map(s->s.toUpperCase())
.min((s1,s2)->s1.length()-s2.length())
.get();



Stream count

count  returns the number of elements, which satisfies all the intermediate conditions. It is also a Terminal Operation.

long count = collections.stream()
.filter(s-> s.startsWith("s"))
.count(); //2

Stream reduce

The reduce() method reduces/merge the elements of a stream to a single value.

String result=collections.stream()
.reduce((s,k)->s+"-"+k)
.get();

reduce takes Binary Operator as a parameter. It can be passed using LAMBDA Expression.

Stream sum

The sum() is used to add all the Integer Elements.

long count = collections.stream()
.mapToInt(i->i.length())
.sum();

How to check whether linked list is palindrome or not?

What is Single Linked List?

 Linked list a data structure used for storing collection of data. It has following properties: 

• Successive elements are connected through reference(Pointer)
• Last Element stores NULL reference.
• Size is not fixed. Can dynamically grow.
• Only Forward traversing is possible, No Backward processing is allowed.
•  No wastage of memory. 

Sample Linked List Class

So far We got basic information about Linked List. 
Now we have to check whether given Linked List is palindrome or not?

Before solving the problem, lets first understand, what is palindrome?. A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward



We can solve this problem by following approaches:

1. Using Stack(Iterative way or Recursive Way(internally uses stack))
1. Push all the elements into stack.
2. Pop the element from stack and compare with header of Linked List
3. If both the elements are same, then header to next node
4. Repeat the steps 2 & 3, until stack is empty and no more left in Linked List  
2.  Without stack
1. First find the middle node of the node.
2. Reverse the second half.
3. Now compare Next pointer of middle with header, 
4. If both are same then move to next pointer and compare. 
5. Repeat step 2 &3 until it reaches to end of the linked list,

LinkList Class


public class LinkList<T> {
    public LinkList() {
    }

    public LinkList(T data) {
        this.data = data;
    }
    private T data;
    private LinkList<T> next;

    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public LinkList<T> getNext() {
        return next;
    }
    public void setNext(LinkList<T> next) {
        this.next = next;
    }
}



With Stack:

        Recursive Way:

        
         LinkList<Integer> originalListHeader=getLinkedList();
       
         boolean isPalindrome=isPalindromeRecursiveWay(originalListHeader);

         private boolean isPalindromeRecursiveWay(LinkList<Integer> listHeader) {
                 if (listHeader == null) {
                            return true;
                  }
               if(isPalindromeRecursiveWay(listHeader.getNext())){
                        if(listHeader.getData()==originalListHeader.getData()){
                              originalListHeader=originalListHeader.getNext();
                             return true;
                         }
                       return false;
                 }
        return false;
    }


Iterative Way:  


private boolean isPalindromeIterativeWay(LinkList<Integer> listHeader) {
      Stack<LinkList<Integer>> stack=new Stack<LinkList<Integer>>();
      LinkList<Integer> list=listHeader;
     while(list!=null){
          stack.push(list);
          list=list.getNext();
       } 
    while(listHeader!=null){
          LinkList<Integer> list=stack.pop();
          if(list.getData()!=listHeader.getData()){
                return false;
          }    
         listHeader=listHeader.getNext();
     }
return true;
}




Without Stack:

private boolean isPalindrome1(LinkList<Integer> root) {
        LinkList<Integer> middleNode = middleNode(root);
        LinkList<Integer> middleNext = reverse(middleNode.getNext());
       
        while (middleNext!=null) {
            if (root.getData() != middleNext.getData()) {
                return false;
            }
            root = root.getNext();
            middleNext = middleNext.getNext();
        }
        return true;
    } 

I'll post Middle Node and reverse function in separate post.

In-Oder traversing in Binary Tree

Information about Tree : Tree Introduction
Pre-Order Traversal in Binary Tree
Post-Order Traversal in Binary Tree

In Order Traversal in Binary Tree: First we traversal through Left child, Node and then right child. Left child should be traversed before the Parent Node traversing, Right child should be traversed after parent node.

1. Traverse the left subtree by recursively calling the in-order function.
2. Display the data part of root element (or current element).
3. Traverse the right subtree by recursively calling the in-order function.

In the above Example, In Oder==> 5,9,2,6,1,8,4,3,7,10

Recursive Way:

public void inOrderRecusriveWay(BinaryDataTree<Integer> root) {
   if (root == null) {
            return;
       }
     inOrderIterativeWay(root.getLeft());
     System.out.print(root.getData() + " ");
    inOrderIterativeWay(root.getRight());
}

Iterative Way

public void inOrderIterativeWay(BinaryDataTree<Integer> root) {
        Stack<BinaryDataTree<Integer>> s = new Stack<BinaryDataTree<Integer>>();
        if (root == null) {
            System.out.println("No Element In the Tree");
            return;
        }
        while (true) {
            while (root != null) {
                s.push(root);
                root = root.getLeft();
            }
            if (s.isEmpty()) {
                break;
            }
           BinaryDataTree temp = s.pop();
            System.out.print(temp.getData() + " ");
           root = temp.getRight();
        }
    } 

ThreadLocal in Java

ThreadLocal is way to maintain the Thread Confinement.

What is Thread Confinement ?..
 How data can be accessed from a single thread. When an Object is confined to a thread, then usage is thread safe even if the confined object itself is not thread safe.

ThreadLocal provides facility that How an object can be bind to a thread, and multiple threads will not be able to see other thread's confined object . Once thread gets killed or done with its job then bind object instance will also be eligible for garbage collection.






                                 Thread-local variables are used to prevent sharing in design. To understand the usage of ThreadLocal, Lets take an example, Suppose you have an Application that exposes RESTful services. In this application each request is new/independent request i.e request is not depend on the previous request or session. Suppose Once you get the request you have to do validation and send request to another class say 'A' for further processing, A is design to  perform some business logic based on the request. Once A done with its work the call another class 'C', which is responsible to interact with DB.
            In the above example, There is a variable  which is required by some of the classes for processing but not for all the class. One way is to pass this variable in each 'n' every class. This approach is a bad design where each class has to carry this variable just for passing. What if we have multiple variables, we can not pass multiple variables to each and every until those are required by all the classes. Another approach is, We can create a ThreadLocal which can store  all the variables, those are required by multiple classes.Any class can set the variable in the ThreadLocal and get the variables from ThreadLocal.

ThreadLocal provides get and set accessor methods that maintain a separate copy of the value for each thread that uses it, So a get returns the most recent value passed to set from the currently executing thread. To understand the ThreadLocal<T>  is as holding a Map<Thread,T> that store Thread specific values.






Code Example:

import java.util.HashMap;
public class LocalCache extends HashMap<String, String> {
    private static final long serialVersionUID = 1L;
  
    private static final ThreadLocal<LocalCache> cache =
            new ThreadLocal<LocalCache>() {
                    public LocalCache initialValue() {
                        return new LocalCache();
                        }
                };

    public static LocalCache getLocalCache() {
        return cache.get();

    }

}


Any class can set the variable in cache and get it from the cache. This cache is bound to a thread and cannot be corrupt by other thread. When a thread calls ThreadLocal.get for the first time, intialValue is requested to provide the initial value for that thread.

How to set the variable:
LocalCache.getLocalCache().put("name", "abc");

Any class can retrieve this variable using below command.
LocalCache.getLocalCache().get("name");

Eight queens puzzle with O(n) complexity

Problem Statement: (Wiki Definition):
The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.
                                 The eight queens puzzle is an example of the more general n-queens problem of placing n queens on an n×n chessboard, where solutions exist for all natural numbers n with the exception of n=2 and n=3.





There could be multiple solutions for this problem, What I mean to say is, there is multiple ways to arrange queens on a chess board. Different approaches might give different arrangements/outputs.

Possible Solution

• Backtracking algorithm
• Optimized Way

Backtracking Algorithm :

It starts with first row and place the Queen in the first cell. Once placed it will ignore the row, column and diagonal cell for next Queen. Proceed with next row and apply the same rule/logic. Keep repeating this until you get the solution. At any point if you see there is no more place left for QUEEN, It means all the above positions where Queen has been placed is not the correct cells,  Go back to previous row and try to find another place for the Queen. If you still don't find the place in this as well then move back to earlier one.

                             Keep repeating above process until you get the solution. As soon as, you get the solution stop the algorithm.







public class NQueenProblem {

private static int n = 8;
int[] array = new int[n];
int[][] chessBoard = new int[n][n];

private boolean[] status = new boolean[] { false };
/*
     * Whether Queen can be placed at this location or not.
     *
     * @Param row : ROW number
     *
     * @Param col : Column number
     *
     * @return boolean: true if queen can be place else false.
     */
    public boolean isQueuePlaced(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (array[i] == col
                    || Math.abs(array[i] - col) == Math.abs(i - row)) {
                return false;
            }
        }
        return true;
    }

    public void NQueueProblemSol(int startRow, int queueRowSize) {
        for (int i = 0; i < queueRowSize; i++) {
            if (status[0]) {
                return;
            }
            if (isQueuePlaced(startRow, i)) {
                array[startRow] = i;
                Arrays.fill(chessBoard[startRow], 0);
                chessBoard[startRow][i] = 1;
                if (startRow == queueRowSize - 1) {
                    status[0] = true;
                    return;
                }
                int nextRow = (startRow + 1);
                NQueueProblemSol(nextRow, queueRowSize);
            }
        }
    }
}






Optimized Way:
 Instead of going to backtracking approach, We can place Queens in step fashion.

No Queen threaten each other in above image.


public class NQueenProblem {

    private static int n = 10;

    int[] array = new int[n];

    int[][] chessBoard = new int[n][n];

 public void NQueueProblemSol(int queueRowSize) {

        if(queueRowSize==1 || queueRowSize==2){
            chessBoard1[0][0]=1;
            return;
        }
        if(queueRowSize==3){
            chessBoard[0][0]=1;
            chessBoard[1][2]=1;
            return;
        }
        int r = queueRowSize - 1, c = queueRowSize - 2;
        for (int k = queueRowSize - 1; k >= 0; k--) {
            chessBoard[r][c] = 1;
            r = r - 1;
            if (c < 2) {
                c = queueRowSize - 1;
            } else {
                c = c - 2;
            }

        }

    }
 }



Above code has only one for loop which executes n times where n is the size of general board. This is the reason why Complexity of this program is O(n).
 

How to validate Sudoku With O(n2) complexity

Sudoko is number placement puzzle, We have to fill 9X9 matrix with numbers ranging 1 to 9 and  following criteria should be fulfilled.

1)  Each row should contain unique digits
2)  Each column should contain unique digits
3)  Each subgrid or region (3X3)(Coloured) should also contain unique digits

For any valid Sudoku, above criterion should be fulfilled.
First we have to check, it should contain digits from 1-9 and should not be repeated in same row. Same is true for column and subgrid.






Lets take a row, it is nothing but 1-D Array with size 9.

How to check whether array has duplicate number or missing number from given range 1-9. ...???

One way to solve this problem is, Sort the array and validate it. Sorting will work here but the complexity would be nlogn or O(n)(counting sort). In case of counting sort space complexity would be O(n).

Is there any way to solve this problem in O(n) time complexity and space complexity should be O(1)...???

Yes, we can achieve it by using XOR operation. Column validation could also be done in similar fashion.

Now, I have to check each highlighted sub grid(3X3).






Lets write a Program to solve this problem in O(n2):

public static boolean isSudokuSolutionValid(int[][] sudoku) {
        int row = 1;
        int col = 1;
        int block1 = 1;
        int block2 = 1;
        int block3 = 1;
        boolean isValid = true;
       for (int i = 0; i < sudoku.length; i++) {

            for (int j = 0; j < (sudoku.length)/3; j++) {
                row = row ^ sudoku[i][j];
                col = col ^ sudoku[j][i];
                block1 = block1 ^ sudoku[i][j];
            }

            for (int j = 3; j < 3+(sudoku.length)/3; j++) {
                row = row ^ sudoku[i][j];
                col = col ^ sudoku[j][i];
                block2 = block2 ^ sudoku[i][j];
            }
            for (int j = 6; j < 6+(sudoku.length)/3; j++) {
                row = row ^ sudoku[i][j];
                col = col ^ sudoku[j][i];
                block3 = block3 ^ sudoku[i][j];
            }
            if ((i + 1) % 3 == 0) {
                if (block1 != 0 || block2 != 0 || block3 != 0) {
                    return false;
                }
                block1 = 1;
                block2 = 1;
                block3 = 1;
            }
            if (row != 0 || col!=0) {
                return false;
            }
            row = 1;
            col = 1;
        }
        return isValid;
    }


 Above Sudoku is  an example of invalid Sudoku.

Above Sudoku is an example of valid Sudoku.

This Problem takes O(n2) complexity to validate whether Sudoku is valid or not.