Daily Coding Problem 1

Problem

Good morning! Here's your coding interview problem for today.
This problem was recently asked by Google.
Given a list of numbers and a number k, return whether any two numbers from the list add up to k.
For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17. Bonus: Can you do this in one pass?

Solution 1: Sorting and Two-Pointers technique.

Approach: A tricky approach to solve this problem can be to use the two-pointer technique. But for using two pointer technique, the array must be sorted. Once the array is sorted the two pointers can be taken which mark the beginning and end of the array respectively. If the sum is greater than the sum of those two elements, shift the right pointer to decrease the value of required sum and if the sum is lesser than the required value, shift the left pointer to increase the value of the required sum. Let’s understand this using an example.

Let an array be {1, 4, 45, 6, 10, -8} and sum to find be 16
After sorting the array
A = {-8, 1, 4, 6, 10, 45}
Now, increment ‘l’ when the sum of the pair is less than the required sum and decrement ‘r’ when the sum of the pair is more than the required sum.
This is because when the sum is less than the required sum then to get the number which could increase the sum of pair, start moving from left to right(also sort the array) thus “l++” and vice versa.
Initialize l = 0, r = 5
A[l] + A[r] ( -8 + 45) > 16 => decrement r. Now r = 4
A[l] + A[r] ( -8 + 10) increment l. Now l = 1
A[l] + A[r] ( 1 + 10) increment l. Now l = 2
A[l] + A[r] ( 4 + 10) increment l. Now l = 3
A[l] + A[r] ( 6 + 10) == 16 => Found candidates (return 1)

Note: If there is more than one pair having the given sum then this algorithm reports only one. Can be easily extended for this though.

Algorithm:

1. hasArrayTwoCandidates (A[], ar_size, sum)
2. Sort the array in non-decreasing order.
3. Initialize two index variables to find the candidate elements in the sorted array.

• 1. Initialize first to the leftmost index: l = 0
• 2. Initialize second the rightmost index: r = ar_size-1

4. Loop while l < r.

• 1. If (A[l] + A[r] == sum) then return 1
• 2. Else if( A[l] + A[r] < sum ) then l++
• 3. Else r–

5. No candidates in the whole array – return 0

// Javascript program to check if given array
// has 2 elements whose sum is equal
// to the given value

// Function to check if array has 2 elements
// whose sum is equal to the given value
function hasArrayTwoCandidates(nums: number[], target: number): boolean {
  nums = nums.sort((a: number, b: number) => a - b);
  let i = 0,
    j = nums.length - 1;
  while (i <= j) {
    if (nums[i] + nums[j] === target) {
      return true;
    } else if (nums[i] + nums[j] > target) {
      j -= 1;
    } else {
      i += 1;
    }
  }
  return false;
}

/* Driver program to test above function */
const A = [1, 4, 45, 6, 10, -8];
const n = 16;
// Function calling
if (hasArrayTwoCandidates(A, n))
  console.log('Array has two elements with the given sum');
else console.log("Array doesn't have two elements with the given sum");

Output:

Array has two elements with the given sum

Time Complexity: Depends on what sorting algorithm we use.

• If Merge Sort or Heap Sort is used then (-)(nlogn) in the worst case.
• If Quick Sort is used then O(n^2) in the worst case.

Auxiliary Space: This too depends on sorting algorithm. The auxiliary space is O(n) for merge sort and O(1) for Heap Sort.

Solution 2: Using hash-table

Approach: This problem can be solved efficiently by using the technique of hashing. Use a hash_map to check for the current array value x(let), if there exists a value target_sum-x which on adding to the former gives target_sum. This can be done in constant time. Let’s look at the following example.

arr[] = {0, -1, 2, -3, 1}
sum = -2
Now start traversing:
Step 1: For ‘0’ there is no valid number ‘-2’ so store ‘0’ in hash_map.
Step 2: For ‘-1’ there is no valid number ‘-1’ so store ‘-1’ in hash_map.
Step 3: For ‘2’ there is no valid number ‘-4’ so store ‘2’ in hash_map.
Step 4: For ‘-3’ there is no valid number ‘1’ so store ‘-3’ in hash_map.
Step 5: For ‘1’ there is a valid number ‘-3’ so answer is 1, -3

Algorithm:

1. Initialize an empty hash table s.
2. Do following for each element A[i] in A[]

• 1. If s[x – A[i]] is set then print the pair (A[i], x – A[i])
• 2. Insert A[i] into s.

function twoSum(nums: number[], target: number): number[] {
  const hash: Record<number, number> = {};
  const length = nums.length;
  for (let i = 0; i < length; i += 1) {
    const n = nums[i];
    if (hash[target - n] !== undefined) {
      return [hash[target - n], i];
    }
    if (!hash[n]) {
      hash[n] = i;
    }
  }
  return [];
}

let A = [1, 4, 45, 6, 10, 8];
let n = 16;
console.log(twoSum(A, n));

Output

[3, 4]

Time Complexity: O(n).
As the whole array is needed to be traversed only once.

Space Complexity: O(n).
A hash map has been used to store array elements.

Note: If the range of numbers includes negative numbers then also it will work fine.