How to Complete the Two Sum Challenge on Leetcode

Given Problem:

We are to find two elements in the given array, such that they add up to a specified target number.

Leetcode has stated that the array will have distinct elements and only have one solution.

Solution

Nested Loops

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = size(nums);
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if ((nums[i] + nums[j]) == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};

I tried using the ternary operator here and found out something interesting. You can’t use a initializer list in the ternary operator output argument. I mean, if I write the return statement as

return ((nums[i] + nums[j]) == target) ? {i, j} : {};

The compiler will not accept this. It will say that the ternary operator does not accept a initializer list, {i, j} here. {i, j} is an initializer because, this is first time we are specifying the size of list and the values in it, at I think so.

Time Complexity is O(n²).

Hash Map -Two Pass

class Solution {
public:
    vector<int> twoSum(vector<int> &nums, int target) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++) {
            hash[nums[i]] = i; // enters elements into hash map
        }
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            if (hash.find(complement) != hash.end() && hash[complement] != i) {
                return {i, hash[complement]}; // checks for compliment, and returns the pair if present.
            }
        }
        return {};
    }
};

Time Complexity is O(n).

Space Complexity is O(n).

it seems we can reduce the space complexity too. two pass is kinda redundant, as we can jus enter the new element after the check in the same loop.

Hash Map -One Pass

class Solution {
public:
    vector<int> twoSum(vector<int> &nums, int target) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i]; // finding the compliment of current iterated element.
            if (hash.find(complement) != hash.end()) {
                return {hash[complement], i}; // return the pair, if found.
            }
            hash[nums[i]] = i; // if not found, the current element is enetered hash map.
        }
        return {};
    }
};

Time Complexity is O(n).

Space Complexity is O(1). → cuz we are not creating another loop for entering element.

This is the solution. Hash map should be used when we need to find another element . It can also be used for storing distinct element, and we can leverage this nature implicitly.

---

C yall tmrw.