Google Interview Challenge: Finding Pairs that Sum Up

Question

Google Interview Challenge: Finding Pairs that Sum Up

My approach to solving this problem involved iterating through the array and checking if there exists an item such that the sum equals array[i] + item. If such a pair is found, I return true; otherwise, I return false.

Now, my main inquiry is: How can I modify the code to return not just true, but also the indices of the numbers that add up to the given sum? Can this be accomplished within the same code snippet provided below?

function hasPairsWithSum(array,sum) {
  for (let i = 0; i < array.length; i++) {
    if (array.find((item) => {return sum === array[i] + item}
    ));
    return true;
  };
  return false;
};
console.log(hasPairsWithSum([1,2,4,4],8))

Please note that the time complexity needs to be less than O(n ^ 2).

javascript arrays algorithm data-structures javascript-objects

Answer 1

Answer №1

Solving the Pair Sum Problem in JavaScript with O(n) Time Complexity.

function findPairsWithSum(arr, targetSum) {
  const numMap = new Map();
  
  for(let j = 0; j < arr.length; j++) {
    let currentNum = arr[j];
    
    if (numMap.has(currentNum)) {
      return [numMap.get(currentNum), j];
    }
    
    let difference = targetSum - currentNum;
    numMap.set(difference, j);
  }
};

console.log(findPairsWithSum([2, 2, 4, 4], 8));

Answer 2

Solving the Pair Sum Problem in JavaScript with O(n) Time Complexity.

function findPairsWithSum(arr, targetSum) {
  const numMap = new Map();
  
  for(let j = 0; j < arr.length; j++) {
    let currentNum = arr[j];
    
    if (numMap.has(currentNum)) {
      return [numMap.get(currentNum), j];
    }
    
    let difference = targetSum - currentNum;
    numMap.set(difference, j);
  }
};

console.log(findPairsWithSum([2, 2, 4, 4], 8));

Answer 3

Answer №2

Kindly review the following code snippet.

function findPairsWithSum(array,sum) {
    let result = [];
  for (let i = 0; i < array.length; i++) {
    if (array.some((item, index) => {return i === index ? false : sum === array[i] + item}))
        result.push(i);
  };
  return result;
};
console.log(findPairsWithSum([1,2,4,4],8))
console.log(findPairsWithSum([3,2,4],6))
console.log(findPairsWithSum([0,4,3,0],0))

Answer 4

Kindly review the following code snippet.

function findPairsWithSum(array,sum) {
    let result = [];
  for (let i = 0; i < array.length; i++) {
    if (array.some((item, index) => {return i === index ? false : sum === array[i] + item}))
        result.push(i);
  };
  return result;
};
console.log(findPairsWithSum([1,2,4,4],8))
console.log(findPairsWithSum([3,2,4],6))
console.log(findPairsWithSum([0,4,3,0],0))

Answer 5

Answer №3

O(n) Solution ... utilizing the mathematical concept a+b = n, where if a is present in our array then we need to determine if b = n - a is also present or not.

def hasPairsWithSum(array,sum):
    d = {} 
    for i in range(len(array)):
        if(array[i] in d):
            d[array[i]].append(i)
        else:
            d[array[i]] = [i]
    ans  = []
    for i in range(len(array)):
        val = sum - array[i]
        if(val in d):
            if(d[val][0] == i):
                if(len(d[val])  > 1):
                    ans.append((i,d[val][1]))
                    break
                else:
                    continue
            else:
                ans.append((i,d[val][0]))
                break
    return ans
print(hasPairsWithSum([4, 4, 4, 4], 8))

O(nlogn) solution ... by storing indexes with elements and sorting them by their values, followed by running a loop using the Two Pointers concept.

def hasPairsWithSum(array,sum):
    arr = []
    for i in range(len(array)):
        arr.append((array[i],i))
    arr.sort()
    i = 0
    j = len(array)-1
    ans = []
    while(i<j):
        tmp_sum = arr[i][0] + arr[j][0]
        if(tmp_sum == sum):
            ans.append((arr[i][1] , arr[j][1]))
            #add your logic if you want to find all possible indexes instead of break
            break
        elif(tmp_sum < sum):
            i = i + 1
        elif(tmp_sum > sum):
            j = j - 1
    return ans
print(hasPairsWithSum([1,2,4,4],8))

Note: If you aim to find all possible solutions, these approaches may not suffice. You can either add your own logic in the while loop or consider using binary search with traversal on every element and storing the indexes in a set (which could lead to worst-case scenario of O(n^2) as all possible values need to be found). For example, with input [4,4,4,4,4,4] and sum = 8, trying to print all possible indexes will require running it up to n^2 (why? Reason being total possible solutions are 5+4+3+2+1 = n*(n-1)/2 ≈ n^2).

Answer 6

O(n) Solution ... utilizing the mathematical concept a+b = n, where if a is present in our array then we need to determine if b = n - a is also present or not.

def hasPairsWithSum(array,sum):
    d = {} 
    for i in range(len(array)):
        if(array[i] in d):
            d[array[i]].append(i)
        else:
            d[array[i]] = [i]
    ans  = []
    for i in range(len(array)):
        val = sum - array[i]
        if(val in d):
            if(d[val][0] == i):
                if(len(d[val])  > 1):
                    ans.append((i,d[val][1]))
                    break
                else:
                    continue
            else:
                ans.append((i,d[val][0]))
                break
    return ans
print(hasPairsWithSum([4, 4, 4, 4], 8))

O(nlogn) solution ... by storing indexes with elements and sorting them by their values, followed by running a loop using the Two Pointers concept.

def hasPairsWithSum(array,sum):
    arr = []
    for i in range(len(array)):
        arr.append((array[i],i))
    arr.sort()
    i = 0
    j = len(array)-1
    ans = []
    while(i<j):
        tmp_sum = arr[i][0] + arr[j][0]
        if(tmp_sum == sum):
            ans.append((arr[i][1] , arr[j][1]))
            #add your logic if you want to find all possible indexes instead of break
            break
        elif(tmp_sum < sum):
            i = i + 1
        elif(tmp_sum > sum):
            j = j - 1
    return ans
print(hasPairsWithSum([1,2,4,4],8))

Note: If you aim to find all possible solutions, these approaches may not suffice. You can either add your own logic in the while loop or consider using binary search with traversal on every element and storing the indexes in a set (which could lead to worst-case scenario of O(n^2) as all possible values need to be found). For example, with input [4,4,4,4,4,4] and sum = 8, trying to print all possible indexes will require running it up to n^2 (why? Reason being total possible solutions are 5+4+3+2+1 = n*(n-1)/2 ≈ n^2).

Answer 7

Answer №4

To find the indexes of elements in an array that add up to a specified sum, you can iterate through each element and compare it with the rest of the elements in the array like this:

function findIndexes(array, sum) {
    const result = [];

    for (let i = 0; i < array.length -1; ++i) {
        for (let j = i + 1; j < array.length; ++j) {
            if ((array[i] + array[j]) === sum)  {
                result.push([i, j]);
            }
        }
    }

    return result;
}

console.log(findIndexes([1, 2, 4, 4], 8));
console.log(findIndexes([3, 2, 4], 6));

Update:

Another approach to achieve linear O(n) complexity is by using a Map structure to store indexes of elements equal to the target sum like below:

function findIndexes(array, sum) {
    const map = new Map();
    const result = [];

    for (let i = 0; i < array.length; ++i) {
        const a = array[i];
        const b = sum - a;
        
        if (map.has(b)) {
            for (const index of map.get(b)) {
                result.push([index, i]);
            }
        }
        
        const l = map.has(a) ? map.get(a) : [];
        l.push(i);
        map.set(a, l);      
    }

    return result;
}


console.log(findIndexes([1, 2, 4, 4], 8));
console.log(findIndexes([3, 2, 4], 6));
console.log(findIndexes([1, 1, 1], 2));

Answer 8

To find the indexes of elements in an array that add up to a specified sum, you can iterate through each element and compare it with the rest of the elements in the array like this:

function findIndexes(array, sum) {
    const result = [];

    for (let i = 0; i < array.length -1; ++i) {
        for (let j = i + 1; j < array.length; ++j) {
            if ((array[i] + array[j]) === sum)  {
                result.push([i, j]);
            }
        }
    }

    return result;
}

console.log(findIndexes([1, 2, 4, 4], 8));
console.log(findIndexes([3, 2, 4], 6));

Update:

Another approach to achieve linear O(n) complexity is by using a Map structure to store indexes of elements equal to the target sum like below:

function findIndexes(array, sum) {
    const map = new Map();
    const result = [];

    for (let i = 0; i < array.length; ++i) {
        const a = array[i];
        const b = sum - a;
        
        if (map.has(b)) {
            for (const index of map.get(b)) {
                result.push([index, i]);
            }
        }
        
        const l = map.has(a) ? map.get(a) : [];
        l.push(i);
        map.set(a, l);      
    }

    return result;
}


console.log(findIndexes([1, 2, 4, 4], 8));
console.log(findIndexes([3, 2, 4], 6));
console.log(findIndexes([1, 1, 1], 2));

Google Interview Challenge: Finding Pairs that Sum Up

Answer №1

Answer №2

Answer №3

Answer №4

Similar questions

Looping through a JSON array

Create a new JSON file to preserve the value of a JSON object

What is the correct way to change the v-model value of a child component within a parent component

What is the best way to retrieve values from a nested array?

Ways to eliminate existing information when conducting a search

Tips for confirming schedule accuracy

Tips for locating and substituting a string in Javascript

Two separate ajax functions executed sequentially both yield identical results

verified firebase/firestore requests

How to pass an item as a parameter to a computed property in Vue.js, and have it return a sorted child array within a

CrossBrowser - Obtain CSS color information

Is AngularJS known for its ability to bind variables across different components effortlessly

Is it possible to change %20 in a URL to a hyphen?

I am experiencing an issue with my service provider when it comes to displaying multiple navigator stacks

Is there a way to reset useQuery cache from a different component?

Fetch data dynamically with jQuery AJAX

Can you provide instructions on how to display data in two lines within a mat-select field?

What is the best way to determine the operational schedule of online stores that have varying business days?

Can you rely on a specific order when gathering reactions in a discord.js bot?

The issue with Array.prototype.join in Internet Explorer 8