AlgoDaily - Sorted Two Sum

Sorted Two Sum (Medium)

Good morning! Here's our prompt for today.

You may see this problem at Microsoft, Square, Symantec, Roblox, Flatiron Health, Hashicorp, Canva, Automation Anywhere, Sprinklr, Sumo Logic, and Smartsheet.

The setup is the same as Two Sum-- you're given an array of numbers, and a "goal" number.

Write a method to return an array of the indexes of the two elements in the array that sum up to the goal. If there are no such elements, return an empty array.

The caveat here is that the numbers are guaranteed to be sorted.

So let's say our goal number was 10. Our numbers to sum to it would be 3 and 7, and their indices 1 and 2 respectively.

JAVASCRIPT

1let arr = [1, 3, 7, 9, 11];
2let goal = 10;
3twoSum(arr, goal);
4// [1, 2]

Is there an efficient way to figure this out?

Constraints

Length of the array <= 100000
The array will always contain integer values between -1000000000 and 1000000000
The required sum is will be well within the integer range
Expected time complexity : O(n)
Expected space complexity : O(1)

xxxxxxxxxx
​
 
var assert = require('assert');
​
function sortedTwoSum(nums, goal) {
  return nums;
}
​
let arr = [1, 3, 7, 8, 11];
let goal = 10;
console.log(sortedTwoSum(arr, goal));
​
try {
  assert.deepEqual(sortedTwoSum([3, 6, 13, 14], 16), [0, 2]);
​
  console.log(
    'PASSED: <code>sortedTwoSum([3, 6, 13, 14], 16)</code> should return <code>[0, 2]</code>'
  );
} catch (err) {
  console.log(err);
}
​
try {
  assert.deepEqual(sortedTwoSum([1, 9, 13, 20, 47], 67), [3, 4]);
​
  console.log(
    'PASSED: <code>sortedTwoSum([1, 9, 13, 20, 47], 67)</code> should return <code>[3, 4]</code>'
  );
} catch (err) {

OUTPUT

Results will appear here.