algorithm to remove element from single linked list

In this algorithm we were not given with the head node but instead given with the node that is to be deleted.

Lets look at an example:

              --------------------------------------
Node        : 1->20  | 2->30  | 3->40  | 4->50  | 5
              --------------------------------------
Node Address: 10     | 20     | 30     | 40     | 50

And assume we want to remove 3rd element where you are given only the THIRD node that is to be deleted.
Output should be: 1,2,4,5

Since you do not have access to the head, change the given node_to_be_deleted in this manner:

                  --------------------------------------
Node            : 1->20  | 2->30  | 4->50  | 4->50  | 5
                  --------------------------------------
Node Address    : 10     | 20     | 30     | 40     | 50

Instead of deleting the 3rd node we are moving 4th node into 3rd node and ignoring 4th node.

	/**
	 * Remove element from SLL
	 * @param node element to be removed
	 */
	public void removeElement(Node node) {
		node.value = node.next.value;
		node.next = node.next.next;
	}
Advertisements

algorithm to find left view and right view of binary tree in java

This algorithm is an extension of breadth first search. In BFS we just print level wise nodes whereas here while printing level wise nodes we add temporary node in between every level (we can call it is Level_Separator (LS)). Once this is structure is formed then the node before the marker belongs to the right view and the node after the marker belongs to the left view.

What is left view? Nodes which are visible when looking from left. What is right view? Nodes which are visible when looking from right. In a tree like below one

            20
    15              25
      18      22      

Left view nodes are ‘20,15,18’ and right view nodes are ‘20,25,22’

Lets look at an example to understand this algorithm:

            20
    15              25
12      18      22      28

BFS puts this tree in a queue such that all level wise nodes are placed next to each other like this

BFS Queue
	--------------------------------
	20 | 15 | 25 | 12 | 18 | 22 | 28
	--------------------------------

Now add level separator in the above queue

Queue Modified for Left/Right Views
	-----------------------------------------------
	20 | LS | 15 | 25 | LS | 12 | 18 | 22 | 28 | LS
	-----------------------------------------------

Let us take nodes before Level_Separator (LS), i.e, 25,28 and after LS i.e, 15,12 excluding root node.

Now add root node to both before/after LS elements; 20,25,28 and 20,15,12 which are nothing but right view and left view of the binary tree.

	/**
	 * Get left and right view of the binary tree
	 * @param node root of the tree
	 */
	public void printLeftNRightViewOfBT(BinaryNode node) {
		Queue<BinaryNode> queue = new LinkedList<BinaryNode>();
		BinaryNode LS = new BinaryNode(null);
		queue.add(node);
		queue.add(LS);

		// left view and right view arrays
		List<BinaryNode> leftView = new ArrayList<BinaryNode>();
		List<BinaryNode> rightView = new ArrayList<BinaryNode>();
		leftView.add(node);

		while (!queue.isEmpty()) {
			BinaryNode currentNode = queue.remove();
			if (!queue.isEmpty() && currentNode.equals(LS)) {
				leftView.add(queue.peek());
				queue.add(LS);
			}
			if (!queue.isEmpty() && queue.peek().equals(LS)) {
				rightView.add(currentNode);
			}
			if (currentNode.left != null) {
				queue.add(currentNode.left);
			}
			if (currentNode.right != null) {
				queue.add(currentNode.right);
			}
		}

		// print views
		printViews(leftView);
		printViews(rightView);
	}

Output is:

Printing left View: 
50 17 9 14 12 
Printing right view: 
50 76 54 72 67 

algorithm to find nth last element of a single linked list

We can do this in two ways

  • Recursive Approach
  • Iterative Approach

Problem Statement: Lets say the Single Linked List (SLL) is 0-1-2-3-4-5-6-7-8-9, and we want to find last 3rd element (say ‘pos=3’) in this SLL

Recursive Approach:
Take a instance/global variable to track the post recursive call and when it is same as ‘pos’, print the value.
Order of complexity: O(n) for pre recursive calls and O(n) for post recursive calls, which is = O(2n)

	public void getElementRecursive(Node node, int pos) {
		if(node != null) {
			getElementRecursive(node.next, pos);
			ctr++;
			if(pos==ctr) {
				System.out.println("Middle element of the list is: " + node.value);
			}
		}
	}

Iterative Approach:
Take two pointers ‘n1’ and ‘n2’, as first step – move pointer n1 to ‘n-1’ positions and as second step – move n1 and n2 simultaneously till n1 is not equal to null.
Order of complexity: O(pos) for first step and O(n-pos) for second step, which is = O(n)

	public void getElementIterative(Node node, int pos) {

		Node n1 = node;
		Node n2 = node;

		for(int i=0; i<pos-1; i++) {
			n1 = n1.next;
		}

		while(n1 != null && n1.next != null) {
			n1 = n1.next;
			n2 = n2.next;
		}
		System.out.println("Middle element of the list is: " + n2.value);
	}

Note: Out of these two approaches, recursive first comes to mind, but looking at the complexities iterative approach is better to implement this algorithm.

algorithm to find substring in a string (KMP Algorithm)

String Search Algorithm in java OR String Matching Algorithm in java: KMP Algorithm is one of the many string search algorithms which is better suited in scenarios where ‘pattern to be searched’ remains same whereas ‘text to be searched’ changes.

Full Source Code cab be downloaded here

Knuth-Morris-Pratt Algorithm (KMP) detailed analysis
Understanding this would show us what a careful algorithmic thinker would code even for a small problem like this. This is one of the algorithms which is easy to implement but one needs lot of attention and hard work to understand the algorithm.

Problem Statement: lets assume we want to search for the pattern P in the text T.
T: [abcabdabcabdabcabdabdabc]
P: [abcabdabc]

This algorithm is executed in two phases.

  • Preprocessing Phase
  • Search Phase

PRE PROCESSING PHASE

In this phase, KMP algorithm creates a temporary array which is prepared from the pattern. We call this temporary array as Partial Match Table (PMT), lets call this PMT as b[i].

What is Partial Match Table?
It is an array of size (pattern_length+1) where, for each position of i in pattern p, b[i] is defined such that it takes the ‘length of the longest proper suffix of P[1…i-1]’ that matches with the ‘prefix of P’.
What is longest prefix/suffix match??? Proper prefix is a prefix which is not same as the substring. Recall proper set which is a subset of a set but is not same as the set. This is very important to understand the algorithm. Let me take an example and show it, considering the above pattern ‘abcabdabc’

I am taking all possible substrings in the pattern ‘abcabdabc’:

a
ab
abc
abca
abcab
abcabd
abcabda
abcabdab
abcabdabc

Now take each substring and find all possible set of proper prefixes and proper suffixes,

a         : no prefix and no suffix since there is only one letter
ab        : prefixes[a]
            suffixes[b]
abc       : prefixes[a,ab]
            suffixes[c,bc]
abca      : prefixes[a,ab,abc]
            suffixes[a,ca,bca]
abcab     : prefixes[a,ab,abc,abca]
            suffixes[b,ab,cab,bcab]
abcabd    : prefixes[a,ab,abc,abca,abcab]
            suffixes[d,bd,abd,cabd,bcabd]
abcabda   : prefixes[a,ab,abc,abca,abcab,abcabd]
            suffixes[a,da,bda,abda,cabda,bcabda]
abcabdab  : prefixes[a,ab,abc,abca,abcab,abcabd,abcabda]
            suffixes[b,ab,dab,bdab,abdab,cabdab,bcabdab]
abcabdabc : prefixes[a,ab,abc,abca,abcab,abcabd,abcabda,abcabdab]
            suffixes[c,bc,abc,dabc,bdabc,abdabc,cabdabc,bcabdabc,abcabdabc]

Now look at the longest proper prefix which is same as the proper suffix:

a         : no prefix and no suffix since there is only one letter
ab        : 0
abc       : 0
abca      : 1 [a]
abcab     : 2 [ab]
abcabd    : 0
abcabda   : 1 [a]
abcabdab  : 2 [ab]
abcabdabc : 3 [abc]

Now start computing the Partial Match Table array values:
b[0] is computed by looking at longest prefix and suffix match of the substring of p[0…0-1] as p[-1] is not defined, hence b[0] is given -1
b[1] is computed by looking at longest prefix and suffix match of the substring of p[0…1-1] = b[0] = A, since there wont be any prefix and suffix for one letter word, b[1] is 0.
Note: For any given pattern b[0] and b[1] are always fixed
b[2]: is computed by looking at longest prefix and suffix match of the substring of p[0…2-1] = b[0…1] = AB = 0
… so on, below are the values of partial match table

b[0] = -1
b[1] = 0
b[2] = 0
.
.
.
b[7] = 1
b[8] = 2
b[9] = 3

Final array is:

p    :  a   b   c   a   b   d   a   b   c
p[i] :  0   1   2   3   4   5   6   7   8
b[i] : -1   0   0   0   1   2   0   1   2   3

Note: Why a prefix should match suffix of the pattern? its because when we shift the pattern its the prefix of P which comes towards the suffix. And also the key idea is that if we have successfully matched prefix P[1…i-1] of the pattern with the substring T[j-(i-1)…j-1] of the input string and P(i)!=T(j), then we dont need to reprocess any of the suffix T[j-(i-1)…j-1] since we know this portion of the text string is the prefix of the pattern that we have just matched.

Pre Processing Code:

	/**
	 * Pre processes the pattern array based on proper prefixes and proper
	 * suffixes at every position of the array
	 *
	 * @param ptrn
	 *            word that is to be searched in the search string
	 * @return partial match table which indicates
	 */
	public int[] preProcessPattern(char[] ptrn) {
		int i = 0, j = -1;
		int ptrnLen = ptrn.length;
		int[] b = new int[ptrnLen + 1];

		b[i] = j;
		while (i < ptrnLen) { 			
		        while (j >= 0 && ptrn[i] != ptrn[j]) {
				// if there is mismatch consider the next widest border
				// The borders to be examined are obtained in decreasing order from 
				//  the values b[i], b[b[i]] etc.
				j = b[j];
			}
			i++;
			j++;
			b[i] = j;
		}
		return b;
	}

Code Walkthrough:
Lets analyze the pre processing phase:

Standard Definitions:
The preprocessing algorithm inner while loop:
If p(j) == p(i), A border of width j can be extended by p(i), here it doesnt go into inner while loop.
If p(j) != p(i), the next-widest border is examined by setting j = b[j]. The loop terminates at the latest if no border can be extended (j = -1).
Now let us look at how partial match table is prepared:
Provided that the values b[0], …, b[i] are already known, the value of b[i+1] is computed by checking if a border of the prefix p[0] … p[i-1] can be extended by p[i]. This is the case if p[b(i)] = p(i). The borders to be examined are obtained in decreasing order from the values b[i], b[b[i]] etc.

What do these definitions say? you will understand once we walk through the code looking at the below PMT table once again

p    :  a   b   c   a   b   d   a   b   c
p[i] :  0   1   2   3   4   5   6   7   8
b[i] : -1   0   0   0   1   2   0   1   2   3

Initially b[0] is set to -1
At 1st loop, i=0, j=-1, since j<0, it will not enter into inner while loop and i&j are incremented, i.e, i=1&j=0 and b[1]=0
At 2nd loop, i=1, j=0, since a[1] is not equal to a[0], it will enter into inner while loop and set j to -1 (because b[j] i.e, b[0]=-1) and i&j are incremented, i.e, i=2&j=0 and b[2]=0
At 3rd loop, i=2, j=0, since a[2] is not equal to a[0], it will enter into inner while loop and set j to -1 (because b[0]=-1) and i&j are incremented, i.e, i=3&j=0 and b[3]=0
At 4th loop, i=3, j=0, since a[3] is equal to a[0], it will not enter into inner while loop and i&j are incremented, i.e, i=4&j=1 and b[4]=1
At 5th loop, i=4, j=1, since a[4] is equal to a[1], it will not enter into inner while loop and i&j are incremented, i.e, i=5&j=2 and b[5]=2
NEXT LOOP IS IMPORTANT TO UNDERSTAND
At 6th loop, i=5, j=2, since a[5] is not equal to a[2], it will enter into inner while loop and set j to 0 (because b[j] i.e, b[2]=0) and still a[5] is not equal to a[0], it will again enter into inner while loop and set j to -1 (because b[j] i.e, b[0]=-1) .
Why j is jumping from 2, 0, and -1?? see the definition ‘The borders to be examined are obtained in decreasing order from the values b[i], b[b[i]] etc.’, here it is b[5] i.e 2, b[b[5]] i.e 0, b[b[b[5]]] i.e -1

Now it will exit inner while loop, increment i&j, i.e, i=6&j=0 and b[6]=0
…. so on
by now you might have understood how to evaluate other values of the array (IF NOT PLS PING I will add the other values as well)

SEARCH PHASE

This is pretty simple once we get the partial match table from preprocessing phase. Here we just compare first character of the text T i.e, t(i) with the first character of the pattern P i.e, p(i), if there is a match we increment the pointers i and j and go forward. If there is a mismatch then we look into the partial match table b[j] to shift the position of j to appropriate value based on the prefix/suffix match by using b[j].

Code Walkthrough

/**
	 * Based on the pre processed array, search for the pattern in the text
	 *
	 * @param text
	 *            text over which search happens
	 * @param ptrn
	 *            pattern that is to be searched
	 */
	public void searchSubString(char[] text, char[] ptrn) {
		int i = 0, j = 0;
		// pattern and text lengths
		int ptrnLen = ptrn.length;
		int txtLen = text.length;

		// initialize new array and preprocess the pattern
		int[] b = preProcessPattern(ptrn);

		while (i < txtLen) {
 			while (j >= 0 && text[i] != ptrn[j]) {
				j = b[j];
			}
			i++;
			j++;

			// a match is found
			if (j == ptrnLen) {
				System.out.println("found substring at index:" + (i - ptrnLen));
				j = b[j];
			}
		}
	}

Lets analyze the search phase:

Index 	      0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  17  18  19  20  21  22  23
Text(T)       a b c a b d a b c a b  d  a  b  c  a  b   d   a   b   d   a   b   c
Pattern(P)    a b c a b d a b c
PMT (b[i])   -1 0 0 0 1 2 0 1 2 3

Here j is a variable used to track the pattern P and i is used to track the text T. Looking at the Text and Pattern, T[0…8] and P[0…8] have a perfect match, once there is a perfect match it enters into if loop at line #26, where j is set from 9 to 3 because b[9]=3; and the program continues from i=8 and j=3, going further there is a mismatch at i=11 and j=5, the program enters into inner while loop where j is set to 2 (because b[5]=2), since p[2] is not equals to t[11], program enters into inner while loop again where j is set to 0 (because b[2]=0), since p[0] is still not equals to t[11], program enters into inner while loop again where j is set to -1 (because b[0]=-1); at j=-1 program exits the inner while loop increments i and j; in next loop at i=12 and j=0, the outer while loop executes with perfect match again at T[12…20] and P[0…8]

Advantages:
Implementation is simple
Time complexity is O(m+n) when compared to the brute force algorithm O(mn)
This algorithm takes atmost 2n comparisions

Disadvantages:
Chances of mismatch increases with big sized alphabets (other than English).

Full Source Code cab be downloaded here

The output of this program is:

 a   b   c   a   b   d   a   b   c   a b e a b c a b d a b c a b d   
printing pattern, partial match table, and its index
 a   b   c   a   b   d   a   b   c    
-1   0   0   0   1   2   0   1   2   3   
 0   1   2   3   4   5   6   7   8   
FOUND SUBSTRING AT i 9 and index: 0
Setting j from 9 to 3

Mismatch happened, between text char e and pattern char d, hence jumping 
  the value of j from 5 to 2 at text index i at 11 based on partial match table
Mismatch happened, between text char e and pattern char c, hence jumping 
  the value of j from 2 to 0 at text index i at 11 based on partial match table
Mismatch happened, between text char e and pattern char a, hence jumping 
  the value of j from 0 to -1 at text index i at 11 based on partial match table

FOUND SUBSTRING AT i 21 and index: 12
Setting j from 9 to 3

I know, this algorithm is too big to digest at one shot, but practising more examples and analysing different patterns with the above explanation would give you a good start. Hope you enjoy this article, happy reading 🙂 🙂 🙂

REFERENCES:
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/stringmatchingclasses/KmpStringMatcher.java

algorithm to find middle element of linked list @ O(n/2) order

Since every node in a linked list has the reference to its next node, we can achieve this solution by taking two pointers.

For every increment in one pointer, increment the second pointer twice, in this way by the time second pointer reaches the end of the linked list, first pointer should reach the middle element of the linked list.

	public void traverse(Node node) {
		tmp = node;
		while (tmp != null && tmp.next != null) {
			node = node.next;
			tmp = tmp.next.next;
		}
		System.out.println("Middle element of the list is: " + node.value);
	}

Note: With this logic, in any linked list we can find 1/2th element (with above logic) OR 1/3rd element (by replacing the code ‘tmp = tmp.next.next;’ to tmp = tmp.next.next.next;) OR 1/4th element (by replacing the code ‘tmp = tmp.next.next;’ to tmp = tmp.next.next.next.next;), so on

algorithm to remove element from an array

This can be achieved in many ways, some of them are discussed here
– standard way when existing order is important: traverse through the elements, once element_to_be_deleted is found, shift remaining elements one position towards left. The complexity of this algorithm is O(n)
– when order of array is not important: take two pointers; one at the beginning of array and another at the end of the array. Increment the starting pointer till the element_to_be_deleted is found and decrement the ending pointer till element is not equals to element_to_be_deleted and then swap elements at start_pointer and end_pointer. The complexity of this algorithm is O(n)
– brute force algorithm. The complexity of this algorithm is O(n*n)

standard way when existing order is important @ O(n)

	public int removeNumber(int[] a, int n) {

		if (a == null || a.length == 0) 
			return -1;
		int i = 0;
		for (int j=0; j<a.length; j++)
			if (a[j] != n) 
				a[i++] = a[j];
		
		System.out.println("New size of the array is "+i);
		return i; // The new dimension of the array
	}

when order of array is not important @ O(n)

	public void removeElementO_n(int[] a, int element) {
		int startPtr = 0; 
		int endPtr = a.length-1;
		//{1,4,2,4,3,5,4,4};
		while(startPtr < endPtr) {
			while(endPtr > 0 && a[endPtr] == element) {
				a[endPtr]=-1;
				endPtr--;
			}
                        
			while(startPtr < a.length && a[startPtr] != element) {
				startPtr++;
			}
			
			if(startPtr < endPtr) {
				a[startPtr] = a[endPtr];
				a[endPtr] = -1;
				startPtr++;
				endPtr--;
			}
		}
	}

brute force algorithm @ O(n*n)

public void removeElementO_n2(int[] a, int element) {
		int ct=0;
		int ln = a.length;
		//{1,4,2,4,3,5,4,4};
		for (int i = 0; i < a.length; i++) {
			if(a[i] == element) {
				ct++;
				for (int j = i; j < a.length; j++) {
					if((j+1)<a.length) {
						a[j] = a[j+1];
					}
				}
				a[ln-ct] = -1;
			}
		}	
	}

print level wise nodes in the binary tree (Breadth First Traversal)

This can be achieved using breadth first traversal algorithm.
– push level wise nodes into the queue at every iteration
– pop the node from queue at every iteration and print its value

Lets look at example:

            20
    15              25
12      18      22      28

BFS puts this tree in queue such there level wise nodes are placed one-another like this

	--------------------------------
	20 | 15 | 25 | 12 | 18 | 22 | 28
	--------------------------------

And at every loop element from queue is removed in FIFO manner

	public void breadthFirstNonRecursive() {
		Queue<BinaryNode> queue = new java.util.LinkedList<BinaryNode>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			BinaryNode node = queue.poll();
			System.out.println(node.element);
			if (node.left != null)
				queue.offer(node.left);
			if (node.right != null)
				queue.offer(node.right);
		}
	}

Output: 20, 15, 25, 12, 18, 22, 28

find depth of binary search tree

We can find the depth of the binary search tree in three different recursive ways
– using instance variables to record current depth and total depth at every level
– without using instance variables in top-bottom approach
– without using instance variables in bottom-up approach

Full source code can be downloaded here
Approach #1: using instance variables to record current depth and total depth at every level

	int currentDepth, depth;
	public int depth(BinaryNode n) {
		if (n != null) {
			currentDepth++;
			
			// record total depth if current depth is greater than total depth 
			if (currentDepth > depth) {
				depth = currentDepth;
			}

			// recursively traverse entire tree
			depth(n.left);
			depth(n.right);
			
			// decrement as we traverse up the binary tree
			currentDepth--;
		}
		return depth;
	}

Pros: Easier to implement and understand
Cons: Usage of instance variables. Ideally any recursive call should not make use of instance variables and by doing so it moves close towards linear programming.

Approach #2: without using instance variables in top-bottom approach

	public int depth3(BinaryNode node, int d){
		int leftDepth = d, rightDepth = d;
		
		if(node.left != null){
			leftDepth = depth3(node.left, d+1);
		}
		if(node.right != null){
			rightDepth = depth3(node.right, d+1);
		}
		
		return leftDepth > rightDepth ? leftDepth : rightDepth;
	}
	

Approach #3: without using instance variables in bottom-up approach

	public int depth2(BinaryNode node){
		if(node == null)
			return 0;
		int left = depth2(node.left);
		int right = depth2(node.right);
		
		int x = left > right ? left+1 : right+1;
		return x;
	}

Approach #2 and #3 are actually recursive way of finding the depth. In #2 we only depend on the return type of the method because back-tracking helps us to keep track of the tree depth. In #3, since we are incrementing the depth in top-bottom fashion, we need additional parameter to the method to track the depth.

My 2 cents for best approach is #2.

Full source code can be downloaded here

Output:

Maximum depth of the Binary Tree is using instance variables: 3
Maximum depth of the Binary Tree is without using instance variables in bottom-up approach: 3
Maximum depth of the Binary Tree is without using instance variables in top-bottom approach: 3
|	|-------28
|-------25
|	|-------22
20
|	|-------18
|-------15
|	|-------12

Mawazo

Mostly technology with occasional sprinkling of other random thoughts

amintabar

Amir Amintabar's personal page

101 Books

Reading my way through Time Magazine's 100 Greatest Novels since 1923 (plus Ulysses)

Seek, Plunnge and more...

My words, my world...

ARRM Foundation

Do not wait for leaders; do it alone, person to person - Mother Teresa

Executive Management

An unexamined life is not worth living – Socrates

Diabolical or Smart

Nitwit, Blubber, Oddment, Tweak !!

javaproffesionals

A topnotch WordPress.com site

thehandwritinganalyst

Just another WordPress.com site

coding algorithms

"An approximate answer to the right problem is worth a good deal more than an exact answer to an approximate problem." -- John Tukey