38) Two Sum II

Not immediately sure how this is different from OG two sum

// 1 indexed
// dear god why
// already sorted numbers array
// find two numbers that add up to a target
// return the indices of the two numbers
 
function twoSum(numbers: number[], target: number): number[] {
    const numMap: Map<number, number> = new Map()
 
    for (let i = 1; i <= numbers.length; i++){
        let num = numbers[i-1]
        const compliment = target - num
        if (numMap.has(compliment)){
            return [numMap.get(compliment)!, i]
        }
        numMap.set(num, i)
    }
};

Okay yup. Weirdness. Looks like Leetcode is just not really enforcing space-complexity correctly here, which is the kicker as far the differences go. I shouldn’t be allowed to use a hashmap ‘legally’ here, as hashmaps are obviously O(n) space complexity. That is, 100 elements use 100 elements of storage, and 10 use 10.

There is a way to use pointers so that 100 elements use 2 units of storage, as do 10. Let me try to figure that out.

function twoSum(nums: number[], target: number): number[] {
    let leftPoint = 0
    let rightPoint = 1
 
    while (leftPoint < nums.length-1){
        if (nums[leftPoint]+nums[rightPoint] === target){
            return [leftPoint, rightPoint]
        }
 
        if (rightPoint < nums.length){
            console.log({rightPoint})
            rightPoint++
            continue
        }
        leftPoint++
        rightPoint = leftPoint + 1
    }
};

Messed up, and didn’t think to add this line at first: rightPoint = leftPoint + 1

There are some more problems. Here is the right solution:

function twoSum(nums: number[], target: number): number[] {
    let leftPoint = 0;
    let rightPoint = 1;
 
    while (leftPoint < nums.length - 1) {
        if (nums[leftPoint] + nums[rightPoint] === target) {
            return [leftPoint, rightPoint];
        }
 
        // Move rightPoint to the next element
        rightPoint++;
 
        // If rightPoint reaches the end, move leftPoint forward and reset rightPoint
        if (rightPoint >= nums.length) {
            leftPoint++;
            rightPoint = leftPoint + 1;
        }
    }
 
    // If no pair is found, return an empty array (or handle as needed)
    return [];
}

My solution was weird…it sort of made sense. I was only moving the right point forward if there was “room”, but the clever thing is that I didn’t really need to make this check, as the leftPoint < nums.length-1 and the right point start as 1 more than this, so there’s at least room for it on the first loop.

Instead, I can check to see if we’ve reached that last position, or even out of index - it would be okay I guess if we went out of index since we aren’t going to pass it into the function where the array will be accessed.

So if we do find our right point is leaving the index on the right side, we can conclude

1. We have checked every other potential match for our current left point, and can move the left point along
2. If we move the left point along, well, we need to “reset” the right point, 1 in front of our new left point

The only real thing left to do is to return something if our while loop never finishes. Although. It should.