1

The 3 sum problem is a well known coding interview problem. It states the following:

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.

I understand the algorithm and have coded the solution in python, but I recently tried to translate the python code below into javascript and I'm getting an incorrect answer.

This is very strange to me, because the code is completely translated, line-by-line. Unless javascript's recursive runtime stack under-the-hood has a different implementation of python (unlikely). Is there something more to why the code gives different results on [-1,0,1,2,-1,-4]?

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        def kSum(nums: List[int], target: int, k: int, startIndex: int) -> List[List[int]]:
            if k == 2:
                ts = twoSum(nums, target, startIndex)
                return ts
            
            res = []
            for i in range(startIndex, len(nums)):
                currNum = nums[i]
                takeCurr = target - currNum
                if i == 0 or nums[i - 1] != nums[i]:
                    found = kSum(nums, target=takeCurr, k=k-1, startIndex=i+1)
                    for subset in found:
                        temp = [currNum] + subset
                        res.append(temp)
            return res

        def twoSum(nums: List[int], target: int, startIndex: int) -> List[List[int]]:
            res = []
            lo = startIndex
            hi = len(nums)-1
    
            while (lo < hi):
                curr_sum = nums[lo] + nums[hi]
                if curr_sum < target:
                    lo += 1
                elif curr_sum > target:
                    hi -= 1
                else:
                    res.append([nums[lo], nums[hi]])
                    lo += 1
                    while (lo < len(nums) and nums[lo] == nums[lo-1]):
                        lo+=1

            return res

        nums.sort()
        return kSum(nums, target=0, k=3, startIndex=0)

function threeSum (nums) {
    function kSum(nums, target, k, startIndex) {
        if (k===2) {
            let ts = twoSum(nums, target, startIndex);
            return ts;
        }

        let res = [];
        for (let i = startIndex; i < nums.length; ++i) {
            const currNum = nums[i];
            const takeCurr = target - currNum;
            if (i === 0 || nums[i-1] != nums[i]) {
                let found = kSum(nums, target=takeCurr, k=k-1, startIndex=i+1);
                for (const subset of found) {
                    let temp = [currNum].concat(subset);
                    res.push(temp);
                }
            }
        }
        return res;
    }

    function twoSum(nums, target, startIndex) {
        let res = [];
        let lo = startIndex;
        let hi = nums.length-1;
        while (lo < hi) {
            const curr_sum = nums[lo] + nums[hi];
            if (curr_sum < target) {
                lo++;
            }
            else if (curr_sum > target) {
                hi--;
            }
            else {
                res.push([nums[lo], nums[hi]]);
                lo++;

                while (lo < nums.length && nums[lo] === nums[lo-1]) {
                    lo++;
                }
            }
        }
        return res;
    }
    
    nums.sort(function(a,b) { return a-b;});
    return kSum(nums, target=0, k=3, startIndex=0);
}
nodel
  • 471
  • 6
  • 22
  • What's up with those named arguments in JS? Please share the result/error. – JBallin Jan 24 '23 at 05:02
  • python: [[-1,-1,2],[-1,0,1]] & javascript: [] – nodel Jan 24 '23 at 05:03
  • Interestingly the name arguments seem to work when testing in the browser. It evaluated the value and disregards the name. – JBallin Jan 24 '23 at 05:07
  • The named arguments results in changing the variable value in the outer scope (if it exists). Try removing them. – JBallin Jan 24 '23 at 05:12
  • example: `k=1; foo(k=2); console.log(k) // 2` – JBallin Jan 24 '23 at 05:13
  • that solves it! can you write this in an answer so it can be helpful to others about the scoping problem that was being made? – nodel Jan 24 '23 at 05:25
  • There is no such thing as named arguments in JavaScript, you are simply assigning a value to a variable and that operation returns the value itself, in this case you change the value of the parameters passed to the function when you call it recursively. – Mkalo Jan 24 '23 at 05:27

1 Answers1

0

JavaScript does not support named arguments. This causes your code to work in unexpected ways and therefore should be removed.

Because you use the same variable name in the nested scope's args, you're overwriting the value of the variable in the outer scope when using named arguments.

Simple example:

let a = 1;
foo(a=2);
console.log(a); // 2
JBallin
  • 8,481
  • 4
  • 46
  • 51