This is quite similar to the Two Sum puzzle.

Given a collection of numbers, write a function that finds a pair that will sum to a given value. For example, the sum we are looking for is 10 and the collection may be [2, 0, 11, 9, 7] or [5, 2, 1, 5]. The function need only return a boolean on whether any pair within the collection satisfies the condition, so False and True for the first and second collection in the example, respectively. You can assume all numbers are integers.

Assume the collection is UNORDERED. Try to find a solution that minimizes the TIME complexity.

What is the time complexity of your solution? Use big-O notation.
What is the memory complexity of your solution? Use big-O notation.

The following is the C++ psue-do code. The idea is to use a hash set that reduces the lookup time to O(1). We need to take care of the duplicate numbers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// O(n) space and O(n) time
bool findPair(const vector<int> &nums, int sum) {
    unordered_set<int> hash;
    // enter all these numbers in a hash table
    for (const auto &n: nums) {
        if (!hash.count(n)) {
            hash.include(n);
        } else {
            if (sum - n == n) { // make sure duplicate number sums.
                return true;
            }
        }
    }
    for (const auto &n: nums) {
        // if the other is existent
        if (hash.count(sum - n)) {
            return true;
        }
    }
    return false;
}

// O(n) space and O(n) time
bool findPair(const vector<int> &nums, int sum) {
    unordered_set<int> hash;
    // enter all these numbers in a hash table
    for (const auto &n: nums) {
        if (!hash.count(n)) {
            hash.include(n);
        } else {
            if (sum - n == n) { // make sure duplicate number sums.
                return true;
            }
        }
    }
    for (const auto &n: nums) {
        // if the other is existent
        if (hash.count(sum - n)) {
            return true;
        }
    }
    return false;
}

Given a collection of numbers, write a function that finds a pair that will sum to a given value. For example, the sum we are looking for is 10 and the collection may be [2, 0, 11, 9, 7] or [5, 2, 1, 5]. The function need only return a boolean on whether any pair within the collection satisfies the condition, so False and True for the first and second collection in the example, respectively. You can assume all numbers are integers.

Assume the collection is ORDERED. Try to find a solution that minimizes the TIME AND MEMORY complexity.

What is the time complexity of your solution? Use big-O notation.
What is the memory complexity of your solution? Use big-O notation.

If the collection is sorted, we can use two pointers starting at both ends, moving towards each other depending on the sum comparison.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// O(N) - time, and O(1) space
bool findPair(const vector<int> nums, int sum) {
    auto i = 0;
    auto j = nums.size() - 1;
    while (i < j) {
        if (nums[i] + nums[j] == sum)    {
            return true;
        }
        if (arr[i] + arr[j] < sum) {
            i ++;
        } else {
            j --;
        }
    }
    return false;
}

// O(N) - time, and O(1) space
bool findPair(const vector<int> nums, int sum) {
    auto i = 0;
    auto j = nums.size() - 1;
    while (i < j) {
        if (nums[i] + nums[j] == sum)    {
            return true;
        }
        if (arr[i] + arr[j] < sum) {
            i ++;
        } else {
            j --;
        }
    }
    return false;
}

–EOF (The Ultimate Computing & Technology Blog) —