Revise and optimize the solution for an algorithm using JavaScript

Question

Revise and optimize the solution for an algorithm using JavaScript

I recently participated in a technical interview for a software development company. The question presented to me was as follows:

Given an array of numbers (n), find two numbers that sum up to a target number (k) and display them.
Example:

Input: n = [2,6,4,5,7,1], k = 8   
Output: result=(2,6),(7,1)

Here is the solution I provided:

function findSum(n,k){
    let aux = []
    for (let i = 0; i < n.length; i++) {
        for (let j = i+1; j < n.length; j++) {
            if (n[i] + n[j] == k) {
                aux.push({ first: n[i], second: n[j] })
            }
        }
    }
    return aux;
}

After presenting my solution, they mentioned that it might be possible to solve the problem using some sort of key or mapping. Does anyone know how to achieve this with only one loop?

javascript arrays algorithm sorting

Answer 1

Answer №1

To efficiently solve a problem like this while maintaining low time complexity, it is essential to have the ability to search through the data structure effectively. Many solutions involve reorganizing the array to optimize searching. Alternatively, using a data structure with fast search capabilities can also be beneficial.

Data structures such as Sets and Maps offer O(1) time complexity for searches, making them ideal choices where efficient searching is crucial for enhanced performance.

In my approach, I utilize a new Map by traversing the array and adding each element as a key while setting the value to represent the frequency of that particular number. I opted for a map over a new Set because I wanted to keep track of the instances of each number as well.

The algorithm involves searching for pairs of numbers that sum up to a given target k, calculated as (k - num). Upon finding a valid pair, both numbers are added to the results data structure, and the value associated with the first number is decremented to indicate its usage.

In terms of time complexity, the solution operates at O(n), with memory complexity being O(2n) due to having separate keys and values stored in the Map.

function pairSums(arr, k){
    const map = new Map
    const matches = []
    for (let num of arr) {
        const search = k - num 
        if (map.get(search) > 0) {
            matches.push([num, k - num])
            map.set(search, map.get(search) - 1)
        } else if (!map.has(num)){
            map.set(num, 1)
        } else {
            map.set(num, map.get(num) + 1)
        }
    }
    return matches
}

console.log(pairSums([2, 6, 6, 6, 2, 4, 4, 4, 5, 7, 1, 4, 2], 8))

Answer 2

To efficiently solve a problem like this while maintaining low time complexity, it is essential to have the ability to search through the data structure effectively. Many solutions involve reorganizing the array to optimize searching. Alternatively, using a data structure with fast search capabilities can also be beneficial.

Data structures such as Sets and Maps offer O(1) time complexity for searches, making them ideal choices where efficient searching is crucial for enhanced performance.

In my approach, I utilize a new Map by traversing the array and adding each element as a key while setting the value to represent the frequency of that particular number. I opted for a map over a new Set because I wanted to keep track of the instances of each number as well.

The algorithm involves searching for pairs of numbers that sum up to a given target k, calculated as (k - num). Upon finding a valid pair, both numbers are added to the results data structure, and the value associated with the first number is decremented to indicate its usage.

In terms of time complexity, the solution operates at O(n), with memory complexity being O(2n) due to having separate keys and values stored in the Map.

function pairSums(arr, k){
    const map = new Map
    const matches = []
    for (let num of arr) {
        const search = k - num 
        if (map.get(search) > 0) {
            matches.push([num, k - num])
            map.set(search, map.get(search) - 1)
        } else if (!map.has(num)){
            map.set(num, 1)
        } else {
            map.set(num, map.get(num) + 1)
        }
    }
    return matches
}

console.log(pairSums([2, 6, 6, 6, 2, 4, 4, 4, 5, 7, 1, 4, 2], 8))

Answer 3

Answer №2

Identify a number y from the array and associate it with a specific key Math.max(y, k - y). Proceed to iterate through the entire array, storing each number in a hash table using this designated key. If the key you are about to add already exists in the hash table, compare the stored value with the current number to see if they add up to the desired sum.

function calculateSum(n, k){
  let hashTable = {};
  for(let j = 0; j < n.length; ++j){
    let y = n[j], newKey = Math.max(y, k - y);
    if((newKey in hashTable) && hashTable[newKey] + y == k)
      return [hashTable[newKey], y];
    else hashTable[newKey] = y;
  }
}

Answer 4

Identify a number y from the array and associate it with a specific key Math.max(y, k - y). Proceed to iterate through the entire array, storing each number in a hash table using this designated key. If the key you are about to add already exists in the hash table, compare the stored value with the current number to see if they add up to the desired sum.

function calculateSum(n, k){
  let hashTable = {};
  for(let j = 0; j < n.length; ++j){
    let y = n[j], newKey = Math.max(y, k - y);
    if((newKey in hashTable) && hashTable[newKey] + y == k)
      return [hashTable[newKey], y];
    else hashTable[newKey] = y;
  }
}

Answer 5

Answer №3

When it comes to tasks like this, the level of complexity is entirely up to you. Take a look at the following solution:

const findPairs = (arr, target) => {
    return arr.reduce((pairs, current, index) => pairs.concat(
        arr.slice(index + 1)
            .filter(num => current + num === target)
            .map(num => [current, num])
    ),
    []
);
}

If you input [2, 6, 4, 5, 7, 1] and 8, the output will be [[2, 6], [7, 1]].

Answer 6

When it comes to tasks like this, the level of complexity is entirely up to you. Take a look at the following solution:

const findPairs = (arr, target) => {
    return arr.reduce((pairs, current, index) => pairs.concat(
        arr.slice(index + 1)
            .filter(num => current + num === target)
            .map(num => [current, num])
    ),
    []
);
}

If you input [2, 6, 4, 5, 7, 1] and 8, the output will be [[2, 6], [7, 1]].

Answer 7

Answer №4

According to a source from this website:

Arranging the array in ascending order is the first step.
Start by identifying two index variables for pinning down potential elements within the sorted array. Assign l as the leftmost index: l = 0, and set r to be the rightmost index: r = n.length - 1
Continue iterating while l < r.
1. If (n[l] + n[r] == k), then return 1
2. Else if( n[l] + n[r] < k ), increment l++
3. Or, decrement r--
If no contenders found throughout the whole array - return 0

Answer 8

According to a source from this website:

Arranging the array in ascending order is the first step.
Start by identifying two index variables for pinning down potential elements within the sorted array. Assign l as the leftmost index: l = 0, and set r to be the rightmost index: r = n.length - 1
Continue iterating while l < r.
1. If (n[l] + n[r] == k), then return 1
2. Else if( n[l] + n[r] < k ), increment l++
3. Or, decrement r--
If no contenders found throughout the whole array - return 0

Answer 9

Answer №5

If you're looking to achieve this, sorting could be the way to go.

var n = [2,6,4,5,7,1];
var k = 8 ;
n.sort();


let start = 0, end = n.length-1;
while(start < n.length && end >= 0) {
    let current_sum = (n[start] + n[end]);
    if(current_sum == k) {
        console.log('Found sum with '+ n[start] +' and '+ n[end]);
        break;
    }
    else if(current_sum > k) {
        end--;
    } else {
        start++;
    }
}
if(start == n.length || end < 0) {
    console.log('Not Found');
}

However, during the process of writing this code, I stumbled upon another approach as well.

const set = new Set([2,6,4,5,7,1]);
var k = 8;
let found = false;
for (let item of set) {
    let another = k - item;
    if(set.has(another)){ 
        console.log('found with '+item +' and ' +another);
        found = true;   
        break;
    }
}
if(!found) {
    console.log('Not found');
}

Answer 10

If you're looking to achieve this, sorting could be the way to go.

var n = [2,6,4,5,7,1];
var k = 8 ;
n.sort();


let start = 0, end = n.length-1;
while(start < n.length && end >= 0) {
    let current_sum = (n[start] + n[end]);
    if(current_sum == k) {
        console.log('Found sum with '+ n[start] +' and '+ n[end]);
        break;
    }
    else if(current_sum > k) {
        end--;
    } else {
        start++;
    }
}
if(start == n.length || end < 0) {
    console.log('Not Found');
}

However, during the process of writing this code, I stumbled upon another approach as well.

const set = new Set([2,6,4,5,7,1]);
var k = 8;
let found = false;
for (let item of set) {
    let another = k - item;
    if(set.has(another)){ 
        console.log('found with '+item +' and ' +another);
        found = true;   
        break;
    }
}
if(!found) {
    console.log('Not found');
}

Answer 11

Answer №6

If all the numbers in the array are non-negative and the target value falls within the JavaScript array limit:

function findSums(arr, target){
    var results = [];
    var hashTable = [];
    arr.forEach(function(num){
      if(num <= target){
        if(hashTable[target - num]){
          results.push([target - num, num]);
        }
        hashTable[num] = true;
      }
    });
    return results;
}

console.log(findSums([2, 6, 4, 5, 7, 1], 8));

A similar strategy could also be implemented using a bitfield or a sparse array of bitfields.

Answer 12

If all the numbers in the array are non-negative and the target value falls within the JavaScript array limit:

function findSums(arr, target){
    var results = [];
    var hashTable = [];
    arr.forEach(function(num){
      if(num <= target){
        if(hashTable[target - num]){
          results.push([target - num, num]);
        }
        hashTable[num] = true;
      }
    });
    return results;
}

console.log(findSums([2, 6, 4, 5, 7, 1], 8));

A similar strategy could also be implemented using a bitfield or a sparse array of bitfields.

Answer 13

Answer №7

Here is a condensed version that closely resembles @Andrew's solution, but under the assumption that all numbers are greater than 0:

var findPairs = (array, target) => array.reduce((accumulator, number) => 
  (accumulator[number - target]-- ? accumulator.push([number, target - number]) : accumulator[-number] = accumulator[-number] | 0 + 1, accumulator), []);

console.log(JSON.stringify( findPairs([2,6,4,5,7,1], 8) ));

Answer 14

Here is a condensed version that closely resembles @Andrew's solution, but under the assumption that all numbers are greater than 0:

var findPairs = (array, target) => array.reduce((accumulator, number) => 
  (accumulator[number - target]-- ? accumulator.push([number, target - number]) : accumulator[-number] = accumulator[-number] | 0 + 1, accumulator), []);

console.log(JSON.stringify( findPairs([2,6,4,5,7,1], 8) ));

Revise and optimize the solution for an algorithm using JavaScript

Answer №1

Answer №2

Answer №3

Answer №4

Answer №5

Answer №6

Answer №7

Similar questions

Having trouble with the pagination feature while filtering the list on the vue-paginate node

Guide to incorporating a jade file into a node.js application after executing an Ajax request

Employ Javascript to display a list of all messages sent through Twilio

Guide on importing a React.Component from a Content Delivery Network (CDN) and displaying it within a separate React

Unable to retrieve the parent element using jQuery

In React js, automatically insert a new row into a table once the Dialog window has

What causes inability for JavaScript to access a property?

What could be causing the issue with my validation for alphabetical input?

Utilizing Object-Oriented Programming in jQuery/JavaScript to effectively pass a value out of a function that is compatible across different browsers

Set the style of the mat-select element

"An error occurred while trying to access the data for a new user on the snapshot object while navigating to the screen. It seems that the object is

What is the best way to manage the browser tab close event specifically in Angular, without it affecting a refresh?

Having Trouble with Your Instafeed Script

What makes it possible for Vue v3 to handle variables that are undefined?

javascript retrieving JSON data through an API request from a redirected URL

Sending a file stream with specific file name and extension in NodeJS: A comprehensive guide

Dynamic content in a CSS animation that rolls credits as they scroll

Events for focusing and blurring top level windows

The controller in ng-controller returns an undefined error when loaded using RequireJs

Are the charts missing from the Django admin interface?