Skip to main content

Find all unique triplets in the array which gives the sum of zero

Leetcode Problem 15 — 3Sum

Difficulty: Medium
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c= 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4]

Solution in javascript with explanation of the logic in plain english below:

const threeSum = (nums, target) => {
  const hash = {};
  const ans = [];
  for (let i = 0; i < nums.length; i++) {
    for (key in hash) {
      if(hash[key][target - (nums[i] + +key)] === undefined) {
        hash[key][nums[i]] = null;
      } else {
        hash[key][target - (nums[i] + +key)] = nums[i];
        ans.push([+key, target - (nums[i] + +key), nums[i]]);
      }
    }
    if (hash[nums[i]] === undefined) {
      hash[nums[i]] = {}
    }
  }
  return ans;
}

Example

console.log(threeSum([-1, 0, 1, 2, -1, -4], 0));

Output

[ [ -1, 0, 1 ], [ 0, 1, -1 ], [ -1, 2, -1 ] ]

Explanation

{
    -1: {0:1, 1:null, 2:-1, -1:null, -4:null},
    0: {1:-1, 2: null, -1:null, -4:null},
    1: {2: null, -1:null, -4: null},
    2: {-1:null, -4:null},
    -4: {}
}
  1. iterate through array > if not in object, add to object
  2. iterate through objects > if not in object of object, add it with value as null | else log

Comments

Post a Comment

Popular posts from this blog

Python - List - Append, Count, Extend, Index, Insert, Pop, Remove, Reverse, Sort

🐍 Advance List List is widely used and it's functionalities are heavily useful. Append Adds one element at the end of the list. Syntax list1.append(value) Input l1 = [1, 2, 3] l1.append(4) l1 Output [1, 2, 3, 4] append can be used to add any datatype in a list. It can even add list inside list. Caution: Append does not return anything. It just appends the list. Count .count(value) counts the number of occurrences of an element in the list. Syntax list1.count(value) Input l1 = [1, 2, 3, 4, 3] l1.count(3) Output 2 It returns 0 if the value is not found in the list. Extend .count(value) counts the number of occurrences of an element in the list. Syntax list1.extend(list) Input l1 = [1, 2, 3] l1.extend([4, 5]) Output [1, 2, 3, 4, 5] If we use append, entire list will be added to the first list like one element. Extend, i nstead of considering a list as one element, it joins the two lists one after other. Append works in the following way. Input l1 = [1, 2, 3] l1.append([4, 5]) Output...
Post a Comment
Read more

Difference between .exec() and .execPopulate() in Mongoose?

Here I answer what is the difference between .exec() and .execPopulate() in Mongoose? .exec() is used with a query while .execPopulate() is used with a document Syntax for .exec() is as follows: Model.query() . populate ( 'field' ) . exec () // returns promise . then ( function ( document ) { console . log ( document ); }); Syntax for .execPopulate() is as follows: fetchedDocument . populate ( 'field' ) . execPopulate () // returns promise . then ( function ( document ) { console . log ( document ); }); When working with individual document use .execPopulate(), for model query use .exec(). Both returns a promise. One can do without .exec() or .execPopulate() but then has to pass a callback in populate.
1 comment
Read more

Resolve: Uncaught TypeError: firebase.database is not a function

If you are getting the error: Uncaught TypeError: firebase.database is not a function Resolve it by including firebase-database.js in your html page as follows: <!-- The core Firebase JS SDK is always required and must be listed first --> <script defer src = "https://www.gstatic.com/firebasejs/6.2.4/firebase-app.js" ></script> <script defer src = "https://www.gstatic.com/firebasejs/3.1.0/firebase-database.js" ></script> That is it. Let me know if this was helpful.
Post a Comment
Read more