O(n) time O(1) space two pointer solution with detailed and clear explanation


  • 3

    To find the two numbers that sum to a target value, let's say the left number is numbers[i], and the right number is numbers[j].

    Let's iterate 0 to numbers.length - 1 one by one to find the left index i.

    Firstly look at when i = 0. Let's say the right j is j* satisfying numbers[i] + numbers[j*] == target. How to find j*? Let's just take a random j satisfying 0 < j < numbers.length. There are 3 situations:

    1. numbers[i] + numbers[j] == target
    2. numbers[i] + numbers[j] < target
    3. numbers[i] + numbers[j] > target

    Answer is found in situation 1.

    In situation 2, if numbers[i] + numbers[j] < target, because the array is sorted, we know that numbers[j*] > numbers[j], and j* > j. So we should check the index bigger than j.

    In situation 3, if numbers[i] + numbers[j] > target, because the array is sorted, we know that numbers[j*] < numbers[j], and j* < j. So we should check the index smaller than j.

    If the left index is not when i == 0, then where is j now?

    It should satisfy:
    numbers[i] + numbers[j] > target
    and
    numbers[i] + numbers[j - 1] < target

    Because answer is not found for i == 0, now let's check when i == 1.

    The trick is, now we only have to check the j that is smaller than the j we have when i == 0. If numbers[0] + numbers[j] > target, then also numbers[1] + numbers[j] > target. So j is decreasing.

    That's how 2 pointer solution come from. Start with i == 0, and j == numbers.length - 1, so that we can always decrease j as we increase i to find the solution.

    public class Solution {
        public int[] twoSum(int[] numbers, int target) {
            int[] res = new int[2];
            int l = 0, r = numbers.length - 1, cur = numbers[l] + numbers[r];
            while (l < r) {
                if (cur == target) {
                    res[0] = l + 1;
                    res[1] = r + 1;
                    break;
                } else if (cur < target) {
                    cur += numbers[l + 1] - numbers[l]; // increase the left index
                    l++;
                } else {
                    cur -= numbers[r] - numbers[r - 1]; // decrease the right index
                    r--;
                }
            }
            return res;
        }
    }
    

  • 0
    M

    @shuangling said in O(n) time O(1) space two pointer solution with detailed and clear explanation:

    In situation 2, if numbers[i] + numbers[j] < target, because the array is sorted, we know that numbers[j*] > numbers[j], and j* > j. So we should check the index bigger than j.
    Great explanation! I was able to understand how to use two pointers to reduce time complexity. Thank You!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.