[LeetCode #1 ] Two Sum

One of the interesting problem to solve is Two Sum
First Solution
My first assumption from the problem was that input will be always sorted, and obviously leetcode bot rejected the solution.

	public class Solution {
		public int[] twoSum(int[] numbers, int target) {
			int[] result = new int[2];
			int l = 0;
			int r = numbers.length - 1 ;
			while (l < r) {
				if (numbers[l] + numbers[r] == target) {
					result[0] = l + 1;
					result[1] = r + 1;
					break;
				} else if (numbers[l] + numbers[r] < target) {
					l++;
				} else {
					r--;
				}
			}
			return result;
		}
	}

After fixing that issue, I forget about duplicate entries

public class Solution {
		public int[] twoSum(int[] numbers, int target) {
			
			java.util.Map<Integer, Integer> numMap = new java.util.HashMap<Integer,Integer>();
			for ( int i = 0; i < numbers.length; i++) {
				numMap.put(numbers[i], i + 1);
			}
			Arrays.sort(numbers);
			
			int[] result = new int[2];
			int l = 0;
			int r = numbers.length - 1 ;
			while (l < r) {
				if (numbers[l] + numbers[r] == target) {
					result[0] = numMap.get(numbers[l]);
					result[1] = numMap.get(numbers[r]);
					break;
				} else if (numbers[l] + numbers[r] < target) {
					l++;
				} else {
					r--;
				}
			}
			return result;
		}
	}


Here is the accepted Solution

	public class Solution {
		public int[] twoSum(int[] numbers, int target) {

			java.util.Map<Integer, java.util.List<Integer>> numLocationMap = new java.util.HashMap<Integer, java.util.List<Integer>>();
			for (int i = 0; i < numbers.length; i++) {
				java.util.List<Integer> indexList = numLocationMap
						.get(numbers[i]);
				if (indexList == null) {
					indexList = new java.util.ArrayList<Integer>();
					numLocationMap.put(numbers[i], indexList);
				}
				indexList.add(i + 1);
			}
			Arrays.sort(numbers);

			int[] result = new int[2];
			int l = 0;
			int r = numbers.length - 1;
			while (l < r) {
				if (numbers[l] + numbers[r] == target) {
					if (numLocationMap.get(numbers[l]).size() == 1) {
						result[0] = numLocationMap.get(numbers[l]).get(0);
						result[1] = numLocationMap.get(numbers[r]).get(0);
					} else {
						result[0] = numLocationMap.get(numbers[l]).get(0);
						result[1] = numLocationMap.get(numbers[r]).get(1);
					}
					break;
				} else if (numbers[l] + numbers[r] < target) {
					l++;
				} else {
					r--;
				}
			}
			Arrays.sort(result);
			return result;
		}
	}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s