LeetCode - Algorithms - 167. Two Sum II - Input array is sorted

Problem

167. Two Sum II - Input array is sorted

Java

Brute-force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        final int N = numbers.length;
        int[] idxArr = {0, 0};
        for (int i = 0; i < N; i++)
            for (int j = N - 1; j > i; j--) {
                if (numbers[j] + numbers[i] == target) {
                    idxArr[0] = i + 1;
                    idxArr[1] = j + 1;
                    return idxArr;
                }
            }
        return idxArr;
    }
}

Submission Detail

  • 17 / 17 test cases passed.
  • Runtime: 191 ms, faster than 7.92% of Java online submissions for Two Sum II - Input array is sorted.
  • Memory Usage: 39.6 MB, less than 16.46% of Java online submissions for Two Sum II - Input array is sorted.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        final int N = numbers.length;
        int index1 = 0, index2 = 0;
        for (int i = 0; i < N / 2 + 1; i++) {
            index1 = i;
            int diff = target - numbers[i];
            int lo = 0;
            int hi = i - 1;
            if (diff >= numbers[i]) {
                lo = i + 1;
                hi = N - 1;
            }
            index2 = search_rank(numbers, lo, hi, diff);
            if (index2 > -1) {
                index1++;
                index2++;
                break;
            }
        }
        return new int[]{index1, index2};
    }

    public int search_rank(int[] nums, int lo, int hi, int target) {
        // Array must be sorted.
        while (lo <= hi) {
            // Key is in a[lo..hi] or not present.
            int mid = lo + (hi - lo) / 2;
            if (target < nums[mid])
                hi = mid - 1;
            else if (target > nums[mid])
                lo = mid + 1;
            else
                return mid;
        }
        return -1;
    }
}

Submission Detail

  • 17 / 17 test cases passed.
  • Runtime: 2 ms, faster than 21.89% of Java online submissions for Two Sum II - Input array is sorted.
  • Memory Usage: 39.2 MB, less than 45.66% of Java online submissions for Two Sum II - Input array is sorted.

Two Pointer

Algorithm Two Pointer Technique:

The two pointer technique is a useful tool to utilize when searching for pairs in a sorted array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        final int N = numbers.length;
        for (int lo = 0, hi = N - 1; lo < hi; ) {
            if (numbers[lo] + numbers[hi] > target)
                hi--;
            else if (numbers[lo] + numbers[hi] < target) {
                lo++;
            } else {
                return new int[]{lo + 1, hi + 1};
            }
        }
        return new int[]{0, 0};
    }
}

Submission Detail

  • 17 / 17 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Two Sum II - Input array is sorted.
  • Memory Usage: 39.4 MB, less than 33.74% of Java online submissions for Two Sum II - Input array is sorted.