Intuition behind initializing both the pointers at the beginning versus one at the beginning and other at the ending

Question

I solved a problem few days ago:

Given an unsorted array A containing N integers and an integer B, find if there exists a pair of elements in the array whose difference is B. Return true if any such pair exists else return false. For [2, 3, 5, 10, 50, 80]; B=40;, it should return true.

as:

int Solution::solve(vector<int> &A, int B) {
    if(A.size()==1) return false;
    int i=0, j=0;     //note: both initialized at the beginning

    sort(begin(A), end(A));
    while(i< A.size() && j<A.size()) {
        if(A[j]-A[i]==B && i!=j) return true;
        if(A[j]-A[i]<B) j++;
        else i++;
    }

    return false;
}

While solving this problem the mistake I had committed earlier was initializing i=0 and j=A.size()-1. Due to this, decrementing j and incrementing i both decreased the differences and so valid differences were missed. On initializing both at the beginning as above, I was able to solve the problem.

Now I am solving a follow-up 3sum problem:

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. If nums = [-1,0,1,2,-1,-4], output should be: [[-1,-1,2],[-1,0,1]] (any order works).

A solution to this problem is given as:

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    for (unsigned int i=0; i<nums.size(); i++) {
        if ((i>0) && (nums[i]==nums[i-1]))
            continue;
        int l = i+1, r = nums.size()-1;   //note: unlike `l`, `r` points to the end
        while (l<r) {
            int s = nums[i]+nums[l]+nums[r];
            if (s>0) r--;
            else if (s<0) l++;
            else {
                res.push_back(vector<int> {nums[i], nums[l], nums[r]});
                while (nums[l]==nums[l+1]) l++;
                while (nums[r]==nums[r-1]) r--;
                l++; r--;
            }
        }
    }
    return res;
}

The logic is pretty straightforward: each of nums[i]s (from the outer loop) is the 'target' that we search for, in the inner while loop using a two pointer approach like in the first code at the top.

What I don't follow is the logic behind initializing r=nums.size()-1 and working backwards - how are valid differences (in this case, the 'sum's actually) not being missed?

Edit1: Both problems contain negative and positive numbers, as well as zeroes.

Edit2: I understand how both snippets work. My question specifically is the reasoning behind r=nums.size()-1 in code# 2: as we see in code #1 above it, starting r from the end misses some valid pairs (http://cpp.sh/36y27 - the valid pair (10,50) is missed); so why do we not miss valid pair(s) in the second code?

Answer 1

Reformulating the problem

The difference between the two algorithms boils down to addition and subtraction, not 3 vs 2 sums.

Your 3-sum variant asks for the sum of 3 numbers matching a target. When you fix one number in the outer loop, the inner loop reduces to a 2-sum that's actually a 2-sum (i.e. addition). The "2-sum" variant in your top code is really a 2-difference (i.e. subtraction).

You're comparing 2-sum (A[i] + A[j] == B s.t. i != j) to a 2-difference (A[i] - A[j] == B s.t. i != j). I'll use those terms going forward, and forget about the outer loop in 3-sum as a red herring.

---

2-sum

Why L = 0, R = length - 1 works for 2-sum

For 2-sum, you probably already see the intuition of starting at the ends and working towards the middle, but it's worth making the logic explicit.

At any iteration in the loop, if the sum of A[L] + A[R] > B, then we have no choice but to decrement the right pointer to a lower index. Incrementing the left pointer is guaranteed to increase our sum or leave it the same and we'll get further and further away from the target, potentially closing off the potential to find the solution pair, which may well still include A[L].

On the other hand, if A[L] + A[R] < B, then you must increase your sum by moving the left pointer forward to a larger number. There's a chance A[R] is still part of that sum -- we can't guarantee it's not a part of the sum until A[L] + A[R] > B.

The key takeaway is that there is no decision to be made at each step: either the answer was found or one of the two numbers at either index can be definitively eliminated from further consideration.

Why L = 0, R = 0 doesn't work for 2-sum

This explains why starting both numbers at 0 won't help for 2-sum. What rule would you use to increment the pointers to find a solution? There's no way to know which pointer needs to move forward and which should wait. Both moves increase the sum at best and neither move decreases the sum (the start is the minimum sum, A[0] + A[0]). Moving the wrong one could prohibit finding the solution later on, and there's no way to definitively eliminate either number.

You're back to keeping left at 0 and moving the right pointer forward to the first element that causes A[R] + A[L] > B, then running the tried-and-true original two-pointer logic. You might as well just start R at length - 1.

---

2-difference

Why L = 0, R = length - 1 doesn't work for 2-difference

Now that we understand how 2-sum works, let's look at 2-difference. Why is it that the same approach starting from both ends and working towards the middle won't work?

The reason is that when you're subtacting two numbers, you lose the all-important guarantee from 2-sum that moving the left pointer forward will always increase the sum and that moving the right pointer backwards will always decrease it.

In subtraction between two numbers in a sorted array, A[R] - A[L] s.t. R > L, regardless of whether you move L forward or R backwards, the sum will decrease, even in an array of only positive numbers. This means that at a given index, there's no way to know which pointer needs to move to find the correct pair later on, breaking the algorithm for the same reason as 2-sum with both pointers starting at 0.

Why L = 0, R = 0 works for 2-difference

Finally, why does starting both pointers at 0 work on 2-difference? The reason is that you're back to the 2-sum guarantee that moving one pointer increases the difference while the other decreases the difference. Specifically, if A[R] - A[L] < B, then L++ is guaranteed to decrease the difference, while R++ is guaranteed to increase it.

We're back in business: there is no choice or magical oracle necessary to decide which index to move. We can systematically eliminate values that are either too large or too small and hone in on the target. The logic works for the same reasons L = 0, R = length - 1 works on 2-sum.

---

_{As an aside, the first solution is suboptimal O(n log(n)) instead of O(n) with two passes and O(n) space. You can use an unordered map to keep track of the items seen so far, then perform a lookup for every item in the array: if B - A[i] for some i is in the map, you found your pair.}

Answer 2

Your question boils down to the following:

For a sorted array in ascending order A, why is it that we perform a different two-pointer search for t for the problem A[i] + A[j] == t versus A[i] - A[j] == t, where j > i?

It's more intuitive why for the first problem, we can fix i and j to be at opposite ends and decrease the j or increase i, so I'll focus on the second problem.

With array problems it's sometimes easiest to draw out the solution space, then come up with the algorithm from there. First, let's draw out the solution space B, where B[i][j] = -(A[i] - A[j]) (defined only for j > i):

B, for A of length N
    i   ---------------------------->
j   B[0][0]     B[0][1]     ... B[0][N - 1]
|   B[1][0]     B[1][1]     ... B[1][N - 1]
|   .           .         .
|   .           .           .
|   .           .             .
v   B[N - 1][0] B[N - 1][1] ... B[N - 1][N - 1]
---
In terms of A:
X           -(A[0] - A[1])  -(A[0] - A[2])  ...  -(A[0] - A[N - 2]) -(A[0] - A[N - 1])
X           X               -(A[1] - A[2])  ...  -(A[1] - A[N - 2]) -(A[1] - A[N - 1])
.           .               .               .                       .
.           .               .                 .                     .
.           .               .                   .                   .
X           X               X               ...  X                  -(A[N - 2] - A[N - 1])
X           X               X               ...  X                  X                       

Notice that B[i][j] = A[j] - A[i], so the rows of B are in ascending order and the columns of B are in descending order. Let's compute B for A = [2, 3, 5, 10, 50, 80].

B = [
   i------------------------>
j  X    1    3    8    48    78
|  X    X    2    7    47    77
|  X    X    X    5    45    75
|  X    X    X    X    40    70
|  X    X    X    X    X     30
v  X    X    X    X    X     X
]

Now the equivalent problem is searching for t = 40 in B. Note that if we start with i = 0 and j = N = 5 there's no good/guaranteed way to reach 40. However, if we start in a position where we can always increment/decrement our current element in B in small steps, we can guarantee that we'll get as close to t as possible.

In this case, the small steps we take involve traversing either right/downwards in the matrix, starting from the top left (could equivalently traverse left/upwards from the bottom right), which corresponds to incrementing both i and j in the original question in A.

Answer 3

Conside this:

A = {2, 3, 5, 10, 50, 80}
B = 40

i = 0, j = 5;

When you have something like

while(i<j) {
    if(A[j]-A[i]==B && i!=j) return true;
    if(A[j]-A[i]>B) j--;
    else i++;
}

consider the case when if(A[j]-A[i]==B && i!=j) is not true. Your code makes an incorrect assumption that if the difference of the two endpoints is > B then one should decrement j. Given a sorted array, you don't know whether you decrementing j and then taking the difference would give you the target difference, or incrementing i and then taking the difference would give you the target number since it can go both ways. In your example, when A[5] - A[0] != 10 you could've gone both ways, A[4] - A[0] (which is what you do) or A[5] - A[1]. Both would still give you a difference greater than the target difference. In short, the presumption in your algorithm is incorrect and hence isn't the right way to go about.

In the second approach, that's not the case. When the triplet nums[i]+nums[l]+nums[r] isn't found, you know that the array is sorted and if the sum was more than 0, it has to mean that the num[r] needs to be decremented since incrementing l would only further increase the sum further since num[l + 1] > num[l].