Here’s a Python implementation of the two_sum_less_than_k function:

from typing import List

def two_sum_less_than_k(nums: List[int], k: int) -> int:
    # Sort the array
    nums.sort()

    # Initialize maximum sum
    max_sum = -1

    # Initialize pointers
    left, right = 0, len(nums) - 1

    # Iterate with two pointers
    while left < right:

        # Calculate the current sum
        current_sum = nums[left] + nums[right]

        # If current sum is less than k, update max_sum
        if current_sum < k:

            # Update the maximum sum if the current sum is greater
            max_sum = max(max_sum, current_sum)

            # Move the left pointer to increase the sum
            left += 1
        else:

            # Move the right pointer to decrease the sum
            right -= 1

    return max_sum

# Example usage:
nums = [36, 23, 1, 24, 75, 33, 54, 8]
k = 60
result = two_sum_less_than_k(nums, k)
print(result)  # Output: 59

nums = [10, 20, 30]
k = 15
result = two_sum_less_than_k(nums, k)
print(result)  # Output: -1

nums = [10]
k = 15
result = two_sum_less_than_k(nums, k)
print(result)  # Output: -1

Explanation:

  • We sort the array nums in ascending order to facilitate the two-pointer approach.
  • We initialize two pointers left and right at the beginning and end of the sorted array, respectively.
  • We iterate with the two pointers towards each other, calculating the sum of elements pointed to by the pointers.
  • If the current sum is less than k, we update max_sum if necessary and move the left pointer to the right.
  • If the current sum is greater or equal to k, we move the right pointer to the left.
  • We continue this process until the pointers meet or cross each other.
  • Finally, we return max_sum, which represents the maximum possible sum less than k found during the iteration.

Time Complexity:

The time complexity of this solution is O(n log n) due to the sorting step, where n is the length of the input array nums. The two-pointer traversal takes linear time O(n), where n is the length of the array.

Space Complexity:

The space complexity is O(1) because we are using only a constant amount of extra space regardless of the input size.