mediumMixed
Find Pair With Target Sum Solution
Problem Statement
You are given an array of distinct integers `nums` and an integer `target`. Your task is to find two distinct indices `i` and `j` in the array such that `nums[i] + nums[j] == target`. If multiple such pairs exist, return any one of them as an array of two indices `[i, j]`. If no such pair exists, return an empty array `[]`.
Examples
Example 1:
Input:nums = [2, 7, 11, 15], target = 9
Output:[0, 1]
Explanation: Because nums[0] + nums[1] == 2 + 7 == 9, we return [0, 1].
Example 2:
Input:nums = [3, 2, 4], target = 6
Output:[1, 2]
Explanation: Because nums[1] + nums[2] == 2 + 4 == 6, we return [1, 2].
Example 3:
Input:nums = [1, 5, 8, 3], target = 10
Output:[]
Explanation: No two distinct elements in the array sum up to 10.
Constraints
- 2 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- All elements in `nums` are distinct.
- You may return the answer in any order (e.g., `[0, 1]` or `[1, 0]` are both valid for the same pair).
Time: O(N) Space: O(N)
A more efficient approach uses a hash map (or dictionary) to store numbers and their indices as we iterate through the array. For each number `num` we encounter, we calculate its `complement` (which is `target - num`). We then check if this `complement` already exists in our hash map. If it does, we've found our pair; otherwise, we add `num` and its index to the hash map. This significantly reduces the time complexity.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
def find_pair_with_target_sum(nums, target):
"""
Finds two distinct indices i and j in the array such that nums[i] + nums[j] == target.
If multiple such pairs exist, returns any one of them as an array of two indices [i, j].
If no such pair exists, returns an empty array [].
"""
num_map = {} # Stores num -> index
for i, current_num in enumerate(nums):
complement = target - current_num
if complement in num_map:
# Found the pair
return [num_map[complement], i]
# Store the current number and its index
num_map[current_num] = i
# No pair found
return []
if __name__ == '__main__':
# Read nums from the first line
nums_str = sys.stdin.readline().strip()
nums = list(map(int, nums_str.split()))
# Read target from the second line
target = int(sys.stdin.readline().strip())
result = find_pair_with_target_sum(nums, target)
print(result)