find all pairs in an array, that sum up to particular number with best complexity

Here we discuss two possible algorithms

• algorithm with the time complexity O(n) and with no additional space complexity
• algorithm which uses additional hashmap data structure which reduces the time complexity to O(2n) at the cost of additional space complexity O(n)
• brute force algorithm with time complexity of O(n^2)

Algorithm with the time complexity O(n) and with no additional space complexity

        /**
	 * 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 k
	 *            sum for which pair of array elements needs to be searched
	 */
	public void getPair2(int[] arr, int k) {
		int start = 0;
		int end = arr.length - 1;
		int sum = 0;

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

		while (start < end) {
			sum = arr[start] + arr[end];
			if (sum == k) {
				// we have found one pair, add it to our output array
				arrs.append(arr[start] + "," + arr[end] + ";");
				start++;
				end--;
			} else if (sum < k) {
				// 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--;
			}
		}
		System.out.println(arrs.toString());
	}

Output: 1,5;2,4;

Algorithm which uses additional hashmap data structure which reduces the time complexity to O(2n) at the cost of additional space complexity O(n)

/**
	 * Find the pair in an array whose sum with complexity O(2n)
	 * 
	 * @param arr
	 *            input array of elements
	 * @param k
	 *            sum for which pair of array elements needs to be searched
	 * @return string of combination of array pairs
	 */
	public String getPair(int[] arr, int k) {
		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
		String result = "";

		/**
		 * First store array elements into hashmap with key as the value of the
		 * array This has time complexity of O(n) and space complexity of O(n)
		 */
		for (int i = 0; i < arr.length; i++) {
			hm.put(arr[i], arr[i]);
		}

		/**
		 * Try getting the hashmap value at key (sum-array_element) If it
		 * exists, it means array_element and sum-array_element is the pair
		 * thats forms sum 'k' This has time complexity of O(n)
		 */
		for (int i = 0; i < arr.length; i++) {
			if (hm.get(k - arr[i]) != null) {
				result += arr[i] + "," + (k - arr[i]) + ";";
			}
		}
		return result;
	}

Output: Pair of elements at O(2n) time complexity and O(n) space complexity: 4,2;2,4;5,1;1,5;

Brute force algorithm with time complexity of O(n^2)

/**
	 * Find the pair in an array whose sum with complexity O(n^2)
	 * 
	 * @param arr
	 *            input array of elements
	 * @param k
	 *            sum for which pair of array elements needs to be searched
	 * @return string of combination of array pairs
	 */
	public String findPair(int[] arr, int k) {
		int i = 0, j = arr.length - 1;
		String result = "";
		while (i < j) {
			while (i < j) {
				if (arr[i] + arr[j] == k) {
					result += arr[i] + "," + arr[j] + ";";
				}
				j--;
			}
			i++;
			j = arr.length - 1;
		}
		return result;
	}

Output: Pair of elements at O(n^2) time complexity and no additional space complexity: 4,2;5,1;

find intersection of elements in two arrays

Assume two arrays, ‘A’ of size ‘m’ and ‘B’ of size ‘n’

case 1: Two arrays are unsorted

Here we pick one of the array and load it into hash implemented data structure, i.e, HashSet and then proceeds further to find intersection of elements.

Since hashed data structure’s complexity is O(1), the total complexity to find intersection of elements the complexity would become

Algorithm Time Complexity: O(m) + O(n)*O(1)
Algorithm Space Complexity: O(m)

	public void intersect1(int[] a, int[] b) {
		HashSet<Integer> hs = new HashSet<Integer>(); 
		for (int i = 0; i < b.length; i++) {
			hs.add(b[i]);
		}
		
		for (int i = 0; i < a.length; i++) {
			if(hs.contains(a[i])) {
				System.out.println(a[i]+" is present in both arrays");
			}
		}	
	}

pros:
best algorithm when compared to all others provided one implements appropriate hashcode method
cons:
when the size of the data structure grows too high, it might lead to hash collisions

Case 2: Two arrays are sorted

For every element in array A, do a binary search in array B (instead of linear search as shown in case-1), so here for every value in ‘A’ we go through log(n) interations in ‘B’ to find out if element in ‘A’ exists in ‘B’

Algorithm Time Complexity: O(m)*O(logn)

		public void intersect(int[] a, int[] b) {
			for(int i=0; i<a.length; i++) {
 				int val = binarySearch(b, a[i], 0, a.length);
 				if(val == b[j]) {
 					System.out.println(a[i]+" is present in both arrays");
 					break;
 				}
 			}
 		}

case 3: Two arrays are unsorted

Brute force algorithm: For every element in array A, traverse through all the elements of array B and find out if the element exists or not.
Algorithm Time Complexity: O(m)*O(n)

In Java

		public void intersect(int[] a, int[] b) {
			for(int i=0; i<a.length; i++) {
				for(int j=0; j<b.length; j++) {
					if(a[i] == b[j]) {
						System.out.println(a[i]+" is present in both arrays");
						break;
					}
				}
			}
		}

pros:
works well for smaller arrays
works for unsorted arrays
cons:
order/complexity is directly proportional to the product of size of arrays, this can take huge time for arrays of larger lengths

Matrix Search – find group of connected-1s/sectors in a matrix

find length of connected cells of 1s(sector) in an matrix of 0s and 1s?
find number of islands in a matrix?
find connected sectors of a matric?
implementation of flood fill algorithm?
All these questions are same, below are the implementation details

Full source code can be downloaded from here

Consider a two-dimensional grid of cells, each of which may be empty or filled. The filled cells that are connected form a sector. Two cells are said to be connected if they are adjacent to each other horizontally, vertically or diagonally. There may be several sectors on the grid. Your job is to find the largest sector (in terms of number of cells) on the grid.

The following figure illustrates a grid with 3 sectors (the largest contains 5 cells).

Problem
Write a program that determines the size of the largest sector for a given grid.

Input
The input begins with a single positive integer on a line by itself indicating the number of the cases
following, each of them as described below. This line is followed by a blank line, and there is also a blank
line between two consecutive inputs. The grid is given as a set of string, each composed of 0s and 1s.
The 1 indicates that the cell is filled and 0 indicates an empty cell. The strings should be converted into
the grid format. The largest grid that should be considered is a 25×25 grid.

Attached is the input file:
input.txt

Output
For each test case, the output must follow the description below. The outputs of two consecutive cases
will be separated by a blank line. The output is the size of the largest sector found on the grid.

Sample Input
2

11000
01100
00101
10001
01011

1011
1010

Sample Output
5
3

This solution is a recursion of depth of 8 levels :

int findMaxDepth(int[][] n, boolean[][] bool, int i, int j) {
	// Check if i, j (indexes) are within the size of array
	// Check if the cell is already traversed or not using bool array
	// Check if the cell value is 1 before counting it as part of a sector
	if(i >= 0 && i < n.length &&  				j >=0 && j < n[0].length
				&& bool[i][j] != true && n[i][j] != 0) {
		currentDepth++;

		// Mark the status of the cell for backtracking purpose
		bool[j] = true;

		// left traversal
		findMaxDepth(n, bool, i-1, j);
		// right traversal
		findMaxDepth(n, bool, i+1, j);

		// top traversal
		findMaxDepth(n, bool, i, j-1);
		// bottom traversal
		findMaxDepth(n, bool, i, j+1);

		// Top-Bottom diagnol
		// diagnol-down traversal
		findMaxDepth(n, bool, i+1, j+1);
		// diagnol-up traversal
		findMaxDepth(n, bool, i-1, j-1);

		// Bottom-Top diagnol
		// diagnol-down traversal
		findMaxDepth(n, bool, i+1, j-1);
		// diagnol-up traversal
		findMaxDepth(n, bool, i-1, j+1);
	}
	return currentDepth;
}

Full source code can be downloaded from here

Attaching the problem statement, input.txt.
counting_cell