# Find pair that sums up to "k" Written by Senthil Nayagan on  - 2 Mins Read

# Problem: Find pair that sums up to “k”

## Description

Given an array of integers `nums` and an integer `k`, create a boolean function that checks if there are two elements in `nums` such that we get `k` when we add them together.

### Example 1

• Input: nums = [4, 1, 5, -3, 6], k = 11
• Output: true
• Explanation: 5 + 6 is equivalent to 11

### Example 2

• Input: nums = [4, 1, 5, -3, 6], k = -2
• Output: true
• Explanation: 1 + (-3) is equivalent to -2

## Solution 1 (Brute force solution)

This solution follows brute force approach.

``````# Brute-force approach
def find_pair(nums, k):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == k:
return True
return False

if __name__ == "__main__":
nums = [4, 1, 5, -3, 6]

print(find_pair(nums, 11)) # True
print(find_pair(nums, -4)) # False
print(find_pair(nums, -2)) # True

``````

### Complexity

• Time complexity: `O(n``2``)`
• Space complexity: `O(1)`

Let’s find a better solution than this one.

## Solution 2

This approach begins by sorting the numbers and then reduces the amount of traversal needed. Since the numbers are sorted in ascending order, then:

• `nums[i] >= nums[i-1]`
• `nums[i] <= nums[i+1]`

This approach uses the left index and the right index. If we increasing the left index, the `sum` value (`k`) will either increase or remain the same. In a similar manner, decreasing the right index will either bring about a reduction in the `sum` value (`k`) or cause it to stay unchanged.

``````def find_pair(nums, k):
nums.sort()
left_idx = 0
right_idx = len(nums) - 1

while left_idx < right_idx:
if nums[left_idx] + nums[right_idx] == k:
return True
elif nums[left_idx] + nums[right_idx] < k:
left_idx += 1
else:
right_idx -= 1
return False
``````

### Complexity

• Time complexity: `O(n log n)`
• Space complexity: Depends on the sorting algorithm we use. For example, if it’s `O(log n)`, then the space complexity of this algorithm is `O(long n)`.

Let’s find a better solution than this one.

## Solution 3 (Using hash table. It’s the most optimal solution)

This solution uses hash table. The hash table is a powerful tool when solving coding problems because it has an `O(1)` lookup on average, so we can get the value of a certain key in `O(1)`. Also, it has an `O(1)` insertion on average, so we can insert an element in `O(1)`.

``````def find_pair(nums, k):
visited = {}  # Dictionary as hash table

for element in nums:
if visited.get(k - element):  # O(1) for lookup
return True
else:
visited[element] = True  # O(1) for insertion
return False
``````

### Complexity

• Time complexity: `O(n)`
• Space complexity: `O(n)` - We are using additional space for a hash table that can contain `n` elements in the worst case.

The lookup and insertion are constant on average in this case. Hence, the `O(n)`.