Given an array nums of integers and an integer k, find two distinct indices i and j in the array such that nums[i] + nums[j] is the maximum possible value less than k. If no such indices exist, return -1.

Function Signature:

from typing import List

def two_sum_less_than_k(nums: List[int], k: int) -> int:
    """
    Find two distinct indices i and j in the array such that nums[i] + nums[j] is the maximum possible value less than k.

    Parameters:
    - nums: List of integers.
    - k: Integer.

    Returns:
    - int: Maximum possible value less than k (or -1 if no such indices exist).
    """
    # Your code here

Example:

# Input: nums = [36, 23, 1, 24, 75, 33, 54, 8], k = 60
# Output: 59
# Explanation: The maximum possible value less than 60 is achieved by adding nums[2] + nums[7] = 1 + 54 = 55.

# Input: nums = [10, 20, 30], k = 15
# Output: -1
# Explanation: There are no two distinct indices such that the sum is less than 15.

# Input: nums = [10], k = 15
# Output: -1
# Explanation: The array contains only one element.

Note:

  • The length of the array is at most 1000.
  • Each element in the array is between -10^9 and 10^9.
  • The value of k is between -10^9 and 10^9.

Instructions:

  • Write the two_sum_less_than_k function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊