This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

link

The leetcode gods have not been kind to me. I am far from worthy of its blessing ... the depression brought on by failing to pass the tests is weighing down on my soul ... oh god ~~

This question is hard ... I thought it would be fun to do a series of questions, but that again proves to be a crazy idea.

Below is the best of my attempt:

var threeSumSmaller = function(nums, target) {
    const sorted = nums.sort(function(a,b){ return a>b ? 1 : -1});
    let midI, rightI;
    let midNum, rightNum;
    let sum;
    let answers = 0;

    sorted.forEach(function(leftNum, leftI){
        rightI = sorted.length-1;
        midI = rightI-1;

        while (rightI - leftI > 1) {
            rightNum = sorted[rightI];
            midNum = sorted[midI];
            sum = leftNum + midNum + rightNum;

            while (sum >= target && leftI < midI) {
                midI--;
                midNum = sorted[midI];
                sum = leftNum + midNum + rightNum;
            }
            answers += midI-leftI;
            rightI--;
            midI = rightI-1;
        }
    })
    return answers;
};

The idea is that instead of searching for every possible index, what I could do is for each iteration of left index, I start at the end for the two other pointers. This is this way when I move the "mid" pointer to the left, when the sum becomes < target, I can just stop the search there.
Take for example:
[1,2,3,4,5,6,7], target = 13
1+6+7 = 14
1+5+7 = 13
1+4+7 = 12
Note that since we found that the sum is smaller than target at [1,4,7], it then means [1,2,7] and [1,3,7] must also be smaller than target, so we can just stop the iteration there and move on to the next one.

However, the performance for this is poor, it is merely a slightly better solution than the brute force where you just straight up try the triple nested for loop.

Apparently there was a VERY similar answer, it is the two pointer approach in the solution, below is by modifying my above code to it:

var threeSumSmaller = function(nums, target) {
    const sorted = nums.sort(function(a,b){ return a>b ? 1 : -1});
    let midI, rightI;
    let midNum, rightNum;
    let sum;
    let answers = 0;

    sorted.forEach(function(leftNum, leftI){
        midI = leftI+1;
        midNum = sorted[midI];
        rightI = sorted.length-1;
        rightNum = sorted[rightI];

        while (midI < rightI) {
            rightNum = sorted[rightI];
            midNum = sorted[midI];
            sum = leftNum + midNum + rightNum;
            if(sum < target) {
                answers+= rightI - midI;
                midI++;
            } else {
                rightI--;
            }
        }
    })
    return answers;
};

WELL I'LL BE DARNED!!! it is basically the exact fucking same thing except for some reason midI starts at leftI +1 as we normally think it should.
The thing that bothered me is why is answers+= rightI-midI in this case?
[1,2,3,4,5,6,7], target = 13
1+2+7 = 10, midI = 1, rightI = 6, answers += 5 = 5
1+3+7 = 11, midI = 2, rightI = 6, answers += 4 = 9
1+4+7 = 12, midI = 3, rightI = 6, answers += 3 = 12
ah okay, so when 1+2+7 is smaller than 13, it means also that:
1+2+6 < 13
1+2+5 < 13
1+2+4 < 13
1+2+3 < 13
So basically the same logic but backwards...so backwards of my backward logic ...nice...
However, I went back to modify my backwards solutions just to see whether I could make it work. I could get a solution that calculates correctly, but inefficiently still.
I believe the reason is that the correct solution shrinks the search in the while loop no matter what and does not need to revisit. On the other hand, my solution requires a "spring back to end" action every time, which makes it do some unnecessary revisiting.

So the lesson here is that ... I don't have good intuition on questions that deal with sorted array, yeah I don't know how to word it at all even...fuck... I was so close though!

Let me know anything on your mind after reading through this, THANKS!