1. Two Sum – Solution [Brute-Force to Best]

Here’s the question link on LeetCode 1. Two Sum:

https://leetcode.com/problems/two-sum/description

Brute Force O(n²)

The simplest approach is to try every possible pair.

I can use two nested loops, pick one element, and check every element after it to see if their sum equals the target.

If it does, return their indices.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();

        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 {};
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();

        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 {};
    }
};

Better O(n log n) – Sorting + Two Pointers

Can we do better than checking every pair?

What if we sort the array and use two pointers?

If the sum is smaller than the target, move the left pointer forward.
If the sum is greater than the target, move the right pointer backward.
If the sum equals the target, we’ve found our pair!

But there’s one catch: we need to return the original indices, not the sorted indices.

So, I’ll store each number along with its original index before sorting.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();

        vector<pair<int, int>> arr;

        for(int i = 0; i < n; i++) {
            arr.push_back({nums[i], i});
        }

        sort(arr.begin(), arr.end());

        int left = 0, right = n - 1;

        while(left < right) {
            int sum = arr[left].first + arr[right].first;

            if(sum == target) {
                return {arr[left].second, arr[right].second};
            }
            else if(sum < target) {
                left++;
            }
            else {
                right--;
            }
        }

        return {};
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();

        vector<pair<int, int>> arr;

        for(int i = 0; i < n; i++) {
            arr.push_back({nums[i], i});
        }

        sort(arr.begin(), arr.end());

        int left = 0, right = n - 1;

        while(left < right) {
            int sum = arr[left].first + arr[right].first;

            if(sum == target) {
                return {arr[left].second, arr[right].second};
            }
            else if(sum < target) {
                left++;
            }
            else {
                right--;
            }
        }

        return {};
    }
};

Optimal O(n) – Hash Map

Can we avoid sorting altogether?

Think about it. For every number, we already know exactly what number we need to find.

If the current number is nums[i], then the number we need is:

\[ complement = target – nums[i] \]

So, instead of searching the entire array for this complement, what if we store the numbers we’ve already visited in a hash map?

We can store number -> index.

For every element:

Calculate its complement.
Check if the complement already exists in our hash map.
If yes, return both indices.
Otherwise, store the current number and its index.

That’s it!

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;

        for(int i = 0; i < nums.size(); i++) {

            int complement = target - nums[i];

            if(mp.find(complement) != mp.end()) {
                return {mp[complement], i};
            }

            mp[nums[i]] = i;
        }

        return {};
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;

        for(int i = 0; i < nums.size(); i++) {

            int complement = target - nums[i];

            if(mp.find(complement) != mp.end()) {
                return {mp[complement], i};
            }

            mp[nums[i]] = i;
        }

        return {};
    }
};

That’s it; see you in the next one.