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;
			}
		}	
	}
Advertisements

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