Leetcode Two Sum II – Input array is sorted using java

Solution of Leetcode Two Sum II – Input array is sorted using java

O(n log n) runtime, O(1) space – Binary search:

For each element x, we could look up if target – x exists in O(log n) time by applying binary search over the sorted array. Total runtime complexity is O(n log n).

public int[] twoSum(int[] numbers, int target) {
 // Assume input is already sorted.
 for (int i = 0; i < numbers.length; i++) {
 int j = bsearch(numbers, target - numbers[i], i + 1);
 if (j != -1) {
 return new int[] { i + 1, j + 1 };
 }
 }
 throw new IllegalArgumentException("No two sum solution");
}
private int bsearch(int[] A, int key, int start) {
 int L = start, R = A.length - 1;
 while (L < R) {
 int M = (L + R) / 2;
 if (A[M] < key) {
 L = M + 1;
 } else {
 R = M;
 }
 }
 return (L == R && A[L] == key) ? L : -1;
}

O(n) runtime, O(1) space – Two pointers:

Let’s assume we have two indices pointing to the i th and j th elements, Ai and Aj respectively. The sum of Ai and Aj could only fall into one of these three possibilities:

Ai + Aj > target. Increasing i isn’t going to help us, as it makes the sum even bigger. Therefore we should decrement j.
Ai + Aj < target. Decreasing j isn’t going to help us, as it makes the sum even smaller. Therefore we should increment i
Ai + Aj == target. We have found the answer

public int[] twoSum(int[] numbers, int target) {
 // Assume input is already sorted.
 int i = 0, j = numbers.length - 1;
 while (i < j) {
 int sum = numbers[i] + numbers[j];
 if (sum < target) {
 i++;
 } else if (sum > target) {
 j--;
 } else {
 return new int[] { i + 1, j + 1 };
 }
 }
 throw new IllegalArgumentException("No two sum solution");
}