Stuck on a two-sum algorithm

Question

I am working through a two-sum problem where I pass in an unsorted array, and a target, k, and I return the the highest sum of any two numbers that are less than k. If there's no possible sum less than k, then return -1.

I think I am on the right path by sorting the array and then using a 2-pointer technique but I am stuck now. If my sum of numbers is greater than the target, then I decrement the end pointer...that seems definitive. The else though, I am not sure if I am doing correctly.

var twoSumLessThanK = function(nums, k) {
  // [1,8,23,23,33,34,54,75] 60
  nums.sort((a, b) => a - b)
  let start = 0;
  let end = 0;
  let max = -1;


  while (start < end) {
    if (nums[start] + nums[end] >= k) {
      end--
    } else if (nums[start] + nums[end] < k) {
      max = Math.max(max, nums[start] + nums[end])
      start++
    }

  }
  return max;
};

console.log(twoSumLessThanK([1,8,23,23,33,34,54,75], 60));

Answer 1

You could check the sum of two values and decrement the right index if greater or equal than k or store the sum, if greater than the max value and increment the left index.

  1   8  23  23  33  34  54  75   sum    max < 60
  >                           <    76
  >                       <        55 -> max
      >                   <        62
      >               <            42
          >           <            57 -> max
              >       <            57
                  >   <            67
                

const
    twoSumLessThanK = function(nums, k) {
        nums.sort((a, b) => a - b);
        let left = 0,
            right = nums.length -1,
            max = -Number.MAX_VALUE;

        while (left < right) {
            let sum = nums[left] + nums[right];
            if (sum >= k) {
                right--;
                continue;
            }
            if (max < sum) max = sum;
            left++;
        }
        return max;
    };

console.log(twoSumLessThanK([1, 8, 23, 23, 33, 34, 54, 75], 60));

Answer 2

it wasn't so hard to code...?

const twoSumLessThanK = (nums, k) =>
  {
  let max = -1
    , arr = nums.reduce((a,c)=> // decrase order values < k
      {
      if (c < k)
        {
        let p = a.findIndex(x=>x < c) 
        if (p<0) p = a.length
        a.splice( p,0,c)
        }
      return a
      }
      ,[])
    ;
  if (arr.length<2) return max
  for(i=arr.length;--i;)
  for(j=i;j--;)
    {
    let sum = arr[i] + arr[j]
    if (sum >= k && i === j+1) return max
    if (sum < k && sum > max ) max = sum
    }
  return max
  }

console.log(twoSumLessThanK([33,1,8,23,23,34,54,75], 60))

Answer 3

An alternative could be a nested for loop, this way you do't have to handle start and end manually

const twoSumLessThanK = function(nums, k)
  {
  let max   = -1;
  const len = nums.length - 1

  for (let start = 0; start < len; start++) 
    {
    for (let end = len; end > start; end--)
      {
      if (nums[start] + nums[end] < k) max = Math.max(max, nums[start] + nums[end])
      }
    }
  return max;
  };

console.log(twoSumLessThanK([1,8,23,23,33,34,54,75], 60)); // Logs 57

A different option would be the following:

const twoSumLessThanK = function(nums, k)
  {
  nums.sort((a, b) => a - b)
  let max      = -1;
  let greatest = null
  
  while (nums.length > 1 && max < k - 1)
    {
    greatest = nums.pop()
    for (let i = nums.length - 1; i >= 0; i--)
      {
      if (greatest + nums[i] < k)
        {
        max = Math.max(max, greatest + nums[i])
        break
        }
      }
    }
  return max;
  };

Or you can just fix your version if you want:

const twoSumLessThanK = function(nums, k)
  {
  // [1,8,23,23,33,34,54,75] 60
  nums.sort((a, b) => a - b)
  const len = nums.length - 1
  let start = 0;
  let max   = -1;
  let end   = len;

  while (start < len)
    {
    if (nums[start] + nums[end] < k)
      {    
      max = Math.max(max, nums[start] + nums[end])
      start++
      end = len;
      }
    else end--
    }
  return max;
  };