algorithm to reverse a string array in O(n/2) complexity

This problem is a subcase of ‘reversing words of a string‘.

There are many ways of reversing a string but best possible case should be considered keeping space and time complexities in mind. Complete source code can be downloaded from here.

Steps to solve this algorithm

  • take two pointers, one pointing to the start of the array and another to the end of the array and swap the values at respective pointers.
  • While traversing the array increment starting pointer and decrement ending pointer and continue swap the values at respective pointers
  • continue this till we reach the middle of the array

by this time array will be reversed as

'welcome to coding algorithms' would become 'smhtirogla gnidoc ot emoclew'

Psuedocode for O(n/2) complexity:

    /**
	 * Algorithm to reverse a string
	 * @param arr
	 * @param wordIdx
	 * @param wordMidIdx
	 * @param wordLastIdx
	 * 
	 * @return reversed string array
	 */
	public char[] reverse(char[] arr, int wordIdx, int wordMidIdx,
	        int wordLastIdx) {
	    for (; wordIdx < wordMidIdx; wordIdx++) {
	        // swap first letter with the last letter in the
	        char tmp = arr[wordIdx];
	        arr[wordIdx] = arr[wordLastIdx - 1];
	        arr[wordLastIdx - 1] = tmp;
	        wordLastIdx--;
	    }
	    return arr;
	}

Output is: smhtirogla gnidoc ot emoclew

Space Complexity: No additional space is required as we are just swapping the letters within the same array
Time Complexity: Order of this algorithm: O(n/2), where is ‘n’ is the length of the input array

O(2n) Complexity
We can use character array stack also to do this operation but to build the stack we need O(n) time and to dump the stack which print the char array in reverse order will take O(n) order.

Complete source code can be downloaded from here.

Note: how to build stack can be looked at here

Advertisements

print single linked list in reverse order

This is frequently asked question as we would be having only forward reference but not the backward reference to traverse the single linked list (SLL) in backward direction.

We can do this in two different ways

  • Recursive Way: Using recursion we can traverse the list in backward direction because when we recursively traverse SLL in forward direction all the method calls are kept on the stack which will be revisited in the same order but in reverse direction till the base condition is met.
  • Linear programming by using stack implementation.

Recursive Way

	public void reverse(Node node) {
		if (node != null) {
			reverse(node.next);
			System.out.print("  " + node.value);
		}
	}

Linear Programming:

	public void reverse1(Node node) {
		Deque<Node> stack = new ArrayDeque<Node>();
		while (node != null) {
			stack.push(node);
			node = node.next;
		}
		// print the stack
		while (!stack.isEmpty())
			System.out.println(stack.poll().value);
	}

Full Source Code

package algorithms.lists;
import java.util.ArrayDeque;
import java.util.Deque;

public class SLLReverse {
	private static Node root, tmp;

	public void reverse(Node node) {
		if (node != null) {
			reverse(node.next);
			System.out.print("  " + node.value);
		}
	}

	public void reverse1(Node node) {
		Deque<Node> stack = new ArrayDeque<Node>();
		while (node != null) {
			stack.push(node);
			node = node.next;
		}
		// print the stack
		while (!stack.isEmpty())
			System.out.println(stack.poll().value);
	}

	public void insert(Node n) {
		if (root == null) {
			root = n;
			tmp = root;
		} else {
			tmp.next = n;
			tmp = n;
		}
	}

	public static void main(String[] str) {
		SLLReverse s = new SLLReverse();
		// build the SLL
		for (int i = 0; i < 10; i++) {
			s.insert(new Node(i));
		}

		// print SLL in reverse order
		s.reverse1(s.root);
	}

	static class Node {
		Node next;
		int value;

		Node(int i) {
			value = i;
		}
	}
}

order of hashmap/hashtable in BIG-O Notation

Order or complexity of any hash implemented data structure in java is O(1).

O(1)  means the time to retrieve an element from the data structure is always almost equals to constant. However poor implementation of hashing can lead to the complexity of O(n).

In O(1) complexity, the elements of the data structure are distributed across the buckets evenly.

In O(n) complexity, the elements of the data structure are all stored in one bucket (very poor hashing implementation).

Note: However SUN will revisit the user given hash code to avoid O(n) complexity, to get more into the details look at detailed hashmap implementation

best searching algorithm

Consider a data structure, say, array ‘a’ of size m

  1. Linear Search with complexity O(n)
  2. Binary Search with complexity O(log n)
  3. Search using HASH value with complexity O(1)

Linear Search with complexity O(n):
Here for a given element, say a[i],  we have to traverse the entire data structure till we find the element, so in the worst case we have to traverse till end of the DS and hence the order/complexity of linear search is O(n)

This is a brute force way of doing it.

pros:
suitable for smaller sized data structures
suitable for data structures which are not sorted
simpler approach, simple and less code (KISS principle)

cons:
for large sized data structures this wont do any good in terms of time complexity

Binary Search with complexity O(log n):
Binary search implements divide and conquer algorithm to search for a required element in the data structure. But to do a binary search on the data structure(DS), DS elements needed to be in sorted manner. (see best sorting algorithms)

Every iteration we divide the array by 2 and then see which side the element (to be searched) falls (lower half or upper half) and recursively do the same thing till the element is found.

logarithm is just a mathematical scale to represent number system in powers of base, in binary search case, base=2 (because every time we divide the DS by two in one way also implies raising the power by 2 in other way)

Example:
1,3,5,7,10,12,16,19
Here we have 8 elements, so every time we divide by half, we can pin point to any element within three iterations, that is, lets assume we are searching for ’19’

First Iteration:
step 1:   pivot = a[(0+7)/2) = a[3] = 7
step 2: Since 19>7, ignore left side of pivot and consider right side array of pivot, that is, 10,12,16,19

Second Iteration:
step 1:   pivot = a[(0+3)/2) = a[1] = 12
step 2: Since 19>12, ignore left side of pivot and consider right side array of pivot, that is, 16,19

Third Iteration:
step 1:   pivot = a[(0+1)/2) = a[0] = 16
step 2: Since 19>16, ignore left side of pivot and consider right side array of pivot, that is, 19, return this value

hence number of elements =8=2^3=3(in log with base 2 scale), therefore the complexity of binary search algorithm is O(log n)

/**
* @author ntallapa
*
*/
public class BinarySearch {

	/**
	 *
	 * @param a integer array to be searched
	 * @param value element of the array to be searched
	 * @param left left most index of the passed array
	 * @param right most index of the passed array
	 * @return element value if found else -1 if not found
	 */
	public int binarySearch(int[] a, int value, int left, int right) {

		// choose pivot index element as middle element
		int idx = (left+right)/2;

		// check if pivot index exists in the array
		if(idx>=a.length) {
			return -1;
		}
		int pivot = a[idx];

		if(left > right)
			return -1;

		if(value < pivot) {
			right = idx-1;
			return binarySearch(a, value, left, right);
		} else if(value > pivot) {
			left = idx+1;
			return binarySearch(a, value, left, right);
		} else {
			return pivot;
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a = {1,2,3,4,5};
		BinarySearch bs = new BinarySearch();

		System.out.println(bs.binarySearch(a, 3, 0, a.length));
	}
}

pros:
Best suitable for large sized arrays

cons:
array elements must be sorted prior to search

Search using HASH value with complexity O(1): 
Insert the elements of the data structure into a hash implemented data structure like Hashtable or HashMap and you are good to go with one line statement:
hashArr.contains(a[i])
Since the elements of hashmap are indexed by hashcode, the time to search for any particular element would almost be = 1 (CONSTANT time)

pros:
Best in case of medium-large sized arrays

cons:
If the array is very large then it might lead to collisions in the hash implemented DS
Additional space requirements to store array elements into hashmap

WHICH ONE TO USE:
It is actually a trade off between these three approaches on which one to use. There is never always one best approach to follow blindly. We should analyze the scenario and adopt one of these.

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