# Find pair of numbers in an array with a given sum

There are multiple ways to find the pair of numbers in a given array. The numbers in the array can be in two ways.

1. Sorted
2. Unsorted

If the numbers are sorted then we can get easily with the complexity of O(n). The brute force approach will be easily applicable for both the sorted and unsorted array of numbers.

### Brute force:

Brute force approach will check each and every number to determine if it equals to the given sum. The complexity of this approach is O(n²).

### Sorted:

In this approach, we need to sort the unsorted array(if needed). In this case, the complexity depends on the complexity of the sorting algorithm. If we choose a sorting algorithm of complexity O(n) we can solve this problem in O(n) complexity.

### Hash / Flag:

In this approach, we can get the pairs in O(n) complexity. We can use hashmap or flag array to set counter for each value and check using negation from the given sum.

In this way, we will get the pairs twice. Because in each occurrence it will check with the hashmap and make a pair. We can add a set to get unique pairs.

### Metrics:

I tried to run these to get some metrics. Sharing those might help to get some understanding.

10000 100000 1000000
Brute force 22ms 1453ms Too long
Sorted O(n log(n)) 4ms 20ms 293ms
Hashmap 8ms 44ms 276ms