Two Sum problem in Javascript

General Idea

The Two Sum problem is a classic algorithmic problem. It asks you to find two numbers in an array that add up to a specific *target * that is provided and then return their indices from the given array.

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to the target. Each input will have exactly one solution, and you may not use the same element twice.

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] nums[1] = 2 7 = 9

Approach 1 Brute force

First approach to any problem could just be to get something done and the easiest thing conceptually.

Iterate through the array with two loops and check all pairs of numbers.

const twoSum = (nums, target) => {
  for(let i = 0; i 



<h3>
  
  
  Approach 1 Complexity
</h3>

<p><strong>Time Complexity</strong> is <em>O(n²)</em></p>

<ol>
<li>Nested loops checking every pair of numbers</li>
<li>Checks every possible combination</li>
<li>Becomes very slow with large arrays</li>
</ol>

<p><strong>Space Complexity</strong> is <em>O(1)</em><br>
1.We have created no new data structure</p>
<h2>
  
  
  Approach 2 More Efficient and what we want.
</h2>

<p>We will use a hash map to solve this. Let's explain this algorithm a bit</p>

<ol>
<li>We use a hash map (object in JavaScript) to store numbers we've seen</li>
<li>For each number, we calculate its complement (target - current number)</li>
<li>We check if the complement exists in our map</li>
<li>If it does, we've found our two numbers and return their indices</li>
<li>If not, we add the current number to the map</li>
</ol>

<p>So first solution could be using the regular JS object and building our HashMap that way<br>
</p>

<pre class="brush:php;toolbar:false">const twoSumOptimizedRegularObject = (nums, target) => {
  const objectStuff = {}

  // write a for loop, to go through the arr
  for (let i = 0; i 



<p>The second solution is actually using the Map Data Structure in JS.This allows for a more stricter and more robust implementations, using a Map object (introduced in ES6) and is often preferred. A Map provides explicit hash map behavior and avoids some quirks of JavaScript objects, like inheriting properties from Object.prototype.<br>
</p>

<pre class="brush:php;toolbar:false">const twoSumOptimized = (nums, target) => {
  const mapOfStuff = new Map()

  // write a for loop, to go through the arr
  for (let i = 0; i 



<h3>
  
  
  Approach 2 Complexity
</h3>

<p><strong>Time Complexity</strong> is <em>O(n)</em></p>

<ol>
<li>Single pass through the array</li>
<li>Hash map provides O(1) lookup</li>
<li>Total time scales linearly with array size</li>
</ol>

<p><strong>Space Complexity</strong> is O(n)<br>
In worst case, we might store nearly all numbers<br>
Trade-off between time and memory efficiency</p>

<h2>
  
  
  Caveats
</h2>

<ol>
<li>Empty array</li>
<li>No solution exists</li>
<li>Multiple solution are possible. In this case, ask if you return after the first iteration.</li>
</ol>


          

            
        

The above is the detailed content of Two Sum problem in Javascript. For more information, please follow other related articles on the PHP Chinese website!