Katkat
Back

Determine Whether Two Integers Sum to a Target

Hudson River TradingSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests proficiency with hash sets to achieve linear time complexity and emphasizes defensive programming practices like input validation and immutability.

Problem Statement

Given an array of integers nums and an integer target, write a function that returns True if there exist two distinct indices i and j such that nums[i] + nums[j] == target. Otherwise, return False.

Requirements

  • Input Validation: The function should return False if nums is null, has fewer than two elements, or if any element in nums is not an integer.
  • Immutability: You must not mutate the input array.
  • Efficiency: The solution should run in O(n) time complexity and O(n) space complexity.

Function Signature

def has_two_sum(nums: list, target: int) -> bool:

Examples

Example 1:

  • Input: nums = [10, 15, 3, 7], target = 17
  • Output: True
  • Explanation: 10 + 7 = 17.

Example 2:

  • Input: nums = [3, 3], target = 6
  • Output: True
  • Explanation: The two 3s at index 0 and 1 sum to 6.

Edge Cases

  • Arrays with fewer than 2 elements.
  • Arrays with negative numbers.
  • Arrays containing duplicates that sum to the target (e.g., [5, 5] target 10).
  • Very large integer values.

Hints

Hint 1

Consider using a hash set to keep track of the numbers you have already encountered while iterating through the array.

Hint 2

For every number `x` in the array, check if `target - x` exists in your set of seen numbers.

Hint 3

Perform the input type checking and length validation at the very beginning of the function before starting the loop.

Follow-up questions

  • How would you modify the function to return the actual indices of the two numbers instead of a boolean?
  • If the input array were already sorted, how could you optimize the space complexity to O(1)?
  • What changes would be necessary if you were required to find the sum of three numbers instead of two?