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