Question 214336 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Return seems to be doesn't exit from function

Right now I’m solving some leetcode problems and I found a curious thing in my code for https://leetcode.com/problems/3sum/ but I don’t understand how it really works.

Problem of this code: Return in hasSimularArray doesn’t exits from the function when hasSimularArray used in threeSum function. The problems is that hasSimularArray keeps running as if it’s a recursion function but it’s not. So when it reaches this line of code "return true;" in hasSimularArray it has to stop execution code in the function.

function threeSum(nums: number[]): number[][] {
  const tripletsResult = [];

  nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length - 2; i++) {
    let j = i + 1;
    let k = nums.length - 1;
    while (j < k) {
      const possibleResultEl = [nums[i], nums[j], nums[k]];
      const threeNumsSum = nums[i] + nums[j] + nums[k];
      if (threeNumsSum === 0) {
        const hasVal = hasSimularArray(tripletsResult, possibleResultEl);
        if (!hasVal) {
          tripletsResult.push(possibleResultEl);
        }
      } else if (threeNumsSum < 0) {
        j++;
      } else {
        k--;
      }
    }
  }

  return tripletsResult;
}

function hasSimularArray(mainArr: number[][], searchedArr: number[]) {
  if (mainArr.length === 0) {
    return false;
  }

  const searchArrayStr = JSON.stringify([...searchedArr].sort());
  for (let el of mainArr) {
    const elArrayStr = JSON.stringify([...el].sort());
    if (elArrayStr === searchArrayStr) {
      return true;
    }
  }
  return false;
}
console.log(threeSum([0, 3, 0, 1, 1, -1, -5, -5, 3, -3, -3, 0]));

Sometime before I faced with a simular problem but it was a bit different code with the same return logic in a nested function and that return somehow exited not only from the nested function but also from the parent one.

Tried to understand what’s going on under the hood over debug mode but it didn’t give any clues to me.

In my case things got worse when I tested hasSimularArray by itself without parent function with the same values and it works as it should.

Could someone please explain what is happening here?

Tags:

2

Answers


  1. 0

    Return in hasSimularArray doesn’t exits from the function

    I don’t know how you have come to this conclusion, but there is no problem with the return statements in hasSimularArray: they get executed and do exit the function. We could say it is an inefficient function, but that is not the main problem here.

    Simple debugging shows that your code gets into an infinite while (j < k) when the condition threeNumsSum === 0 becomes true. In that case, you don’t change the values of j nor k, so the next iteration of the while loop will look at the exact same numbers and come to the same conclusion that threeNumsSum is 0, repeating this indefinitely.

    You must make sure that the while loop makes the window (j, k) smaller.

    In the case of threeNumsSum you can both increase j and decrease k:

          if (threeNumsSum === 0) {
        const hasVal = hasSimularArray(tripletsResult, possibleResultEl);
        if (!hasVal) {
          tripletsResult.push(possibleResultEl);
        }
        // Narrow the window!
        j++; 
        k--;
      }
    Login or Signup to reply.
  2. 0

    Your algorithm might be crashing and burning when the nums array is large.

    You can efficiently keep track of which triplets have already been found by using an Object (you could also use a Map). You can also use that same object to store the triplets that you’re going to return.

    function threeSum(nums: number[]): number[][] {
  const dupeTracker = {};

  nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length - 2; i++) {
    let j = i + 1;
    let k = nums.length - 1;
    while (j < k) {
      const threeNumsSum = nums[i] + nums[j] + nums[k];
      if (threeNumsSum === 0) {
        const possibleResultEl = [nums[i], nums[j], nums[k]];
        const uniqueKey = JSON.stringify(possibleResultEl.sort());
        if (!dupeTracker[uniqueKey]) {
          dupeTracker[uniqueKey] = possibleResultEl;
        }
      } else if (threeNumsSum < 0) {
        j++;
      } else {
        k--;
      }
    }
  }

  return Object.values(dupeTracker);
}
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search