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 
Advertisements

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

finding three elements in an array whose sum is equal to a given number

Finding three elements in an array whose sum is equal to a given number(say trisum)

Here, for every element(arr[i]) that we pick, trisum-arr[i] gives us the bisum (algorithm to find a pair of elements that matches to sum k), hence we make use of our bisum algorithm to find a pair that matches to sum k

Assumption: The input array is sorted.

Example
arr: {1,2,3,4,5} and trisum is 8 then tri pairs are 1,3,4 and 1,2,5
Here lets say arr[i] is 1 then bisum=trisum-arr[i] i.e, bisum=8-1=7 therefore we should run bisum algorithm for sum 7

Time complexity for this algo: O(n^2) because for every element we need to find set of pairs

Note: If the array is not sorted the the complexity would be nlogn + O(n^2)

/**
 * find 3 elements in an array, that sum up to particular number with best
 * complexity
 * 
 * @author ntallapa
 * 
 */
public class TriPairSumCloseToK {

	public void getTriPair(int[] arr, int expectedTriSum) {
		for (int i = 0; i < arr.length; i++) {
			int expectedBiSum = expectedTriSum - arr[i];
			String output = getPair2(arr, expectedBiSum, i);
			if(!output.equalsIgnoreCase("")) {
				System.out.println(arr[i]+","+output.toString());
			}
		}
	}
	
	/**
	 * Find the pair in an array whose sum with complexity O(n). This assumes
	 * the array passed is sorted array and there are no duplicates in the 
	 * array
	 * @param arr
	 *            input array of elements
	 * @param expectedBiSum
	 *            sum for which pair of array elements needs to be searched
	 */
	public String getPair2(int[] arr, int expectedBiSum, int ignoreIndex) {
		int start = 0;
		int end = arr.length - 1;
		int sum = 0;

		// output array to record matching pairs
		StringBuilder arrs = new StringBuilder();

		while (start < end) {
			//
			if(start == ignoreIndex)
				start++;
			//
			if(end == ignoreIndex)
				end--;
			
			sum = arr[start] + arr[end];
			if (sum == expectedBiSum) {
				// we have found one pair, add it to our output array
				arrs.append(arr[start] + "," + arr[end] + ";");
				start++;
				end--;
			} else if (sum < expectedBiSum) {
				// if the sum of the pair is less than the sum we are searching
				// then increment the start pointer which would give us the sum
				// more than our current sum as the array is sorted
				start++;
			} else {
				// if the sum of the pair is greater than the sum we are 
				// searching then decrement the end pointer which would give us 
				// the sum less than our current sum as the array is sorted
				end--;
			}
		}
		return arrs.toString();
	}

	/**
	 * Client to test
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		TriPairSumCloseToK p = new TriPairSumCloseToK();

		// sorted array algo
		int[] arr1 = { 1, 2, 3, 4, 5 };
		p.getTriPair(arr1, 1);

	}
}

algorithm to find first unrepeated character in a string

We can do it in two different ways

  • Algorithm with O(2n) time complexity and O(1) space complexity
  • Algorithm with O(2n) time complexity and O(n) space complexity

Algorithm with O(2n) time complexity and O(1) space complexity
Here we take a fixed size (256 in which all characters small and caps fall into) integer array and we scan the string two times

  • First scan we increment the counter in integer array for every character that appears in string
  • In second scan, we look for counter value 1 which gives the first unrepeated character in string

Note: Here space complexity is O(1) because the int array size is always constant irrespective of the string we pass

	public static char firtUnrepeatedCharInString(char[] s) {
		char result = '\0';
		int[] counts = new int[256];
		for (char c : s) {
			counts[c]++;
		}

		for (int i = 0; i < s.length; i++) {
			if (counts[s[i]] == 1) {
				result = s[i];
				break;
			}				
		}

		return result;
	}

Algorithm with O(2n) time complexity and O(n) space complexity
Here we take hashmap and we scan the string two times

  • First scan we insert every character that appears in string as key and its number of appearances as value in hashmap
  • In second, scan we look for key whose value is 1 which gives the first unrepeated character in string
	public static char firtUnrepeatedCharInString(char[] s) {
		char result = '\0';
		HashMap<Character, Integer> hm = new HashMap<Character, Integer>();
		for (char c : s) {
			Object o = hm.get(c);
			if(o == null) {
				hm.put(c, 1);
			} else {
				int ctr = hm.get(c);
				hm.put(c, ++ctr);
			}
		}

		for (char c : s) {
			int ctr = hm.get(c);
			if(ctr == 1) {
				result = c;
				break;
			}
		}
		return result;
	}

algorithm to merge two sorted arrays without additional array

Algorithm to merge two sorted arrays: Here we use merge sort logic but with a small change; we take the larger size array and start inserting elements from end of that array.

package algorithms.sort;

/**
 * Algorithm to merge two sorted arrays without additional array,
 * provided one of the two arrays has the size of the combination
 * sizes of two arrays
 *
 * @author ntallapa
 *
 */
public class Merge2SortedArraysWO3rdArray {

	public void mergeArrays(int[] aArr, int aSize, int[] bArr, int bSize) {
		// pointer to end of the first sorted array
		int aIdx=aArr.length-1;
		// pointer to end of the second sorted array (pointer at 100 in below array bArr)
		int bIdx=bArr.length-aArr.length-1;
		// pointer to end of the second sorted array (pointer at last 0)
		int cIdx=bArr.length-1;

		/**
		 * whichever is higher in two arrays, place that
		 * element in last position of the bigger array
		 */
		while(cIdx>=0 && aIdx>=0 && bIdx>=0) {
			if(aArr[aIdx] > bArr[bIdx]) {
				bArr[cIdx--] = aArr[aIdx--];
			} else {
				bArr[cIdx--] = bArr[bIdx--];
			}
		}

		// run through the left over elements of array aArr
		while(aIdx>=0) {
			bArr[cIdx--] = aArr[aIdx--];
		}

		// run through the left over elements of array bArr
		while(bIdx>0) {
			bArr[cIdx--] = bArr[bIdx--];
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Merge2SortedArraysWO3rdArray mergeArrays = new Merge2SortedArraysWO3rdArray();
		int[] aArr = {3,7,12,16};
		int[] bArr = {1,4,9,100,0,0,0,0};

		mergeArrays.mergeArrays(aArr, aArr.length, bArr, bArr.length);

		for(int i: bArr) {
			System.out.println(i);
		}
	}
}

Output:

1 3 4 7 9 12 16 100
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