Home | Projects | Notes > Problem Solving > LC - E - 1. Two Sum

LC - E - 1. Two Sum

Solutions in C++

Solution 1

Brute-force approach - Checking all possible combinations with two nested loops.

Complexity Analysis:

• T = O(n²)

• S = O(1)

Solution:

19
1
class Solution {
2
public:
3
    vector<int> twoSum(vector<int>& nums, int target) {
4
        int n = nums.size();
5
        for (int i = 0; i < n - 1; ++i)
6
        {
7
            for (int j = i + 1; j < n; ++j)
8
            {
9
                if (nums[i] + nums[j] == target)
10
                {
11
                    return {i, j};
12
                }   
13
            }
14
        }
15

16
        // No solution found
17
        return {};
18
    }
19
};

Solution 2

Instead of checking all possible combinations with two nested loops (O(n²)), this solution uses a hash table (unordered_map) to reduce the time complexity to O(n).

Complexity Analysis:

• T = O(n)

• S = O(1)

Solution: Two-pass

x
1
class Solution {
2
public:
3
    vector<int> twoSum(vector<int>& nums, int target) {
4
        unordered_map<int, int> um;
5
        int n = nums.size();
6

7
        // Build the hash table to map values to indices
8
        for (int i = 0; i < n; ++i)
9
        {
10
            um[nums[i]] = i;
11
        }
12

13
        // Find the complement
14
        for (int i = 0; i < n; ++i)
15
        {
16
            int complement = target - nums[i];
17
            
18
            if (um.count(complement) && um[complement] != i)
19
            {
20
                return {i, um[complement]};
21
            }
22
        }
23

24
        // No solution found
25
        return{};
26
    }
27
};

Solution: One-pass

1
22
1
class Solution {
2
public:
3
    vector<int> twoSum(vector<int>& nums, int target) {
4
        unordered_map<int, int> um;
5
        int n = nums.size();
6

7
        for (int i = 0; i < n; ++i)
8
        {
9
            int complement = target - nums[i];
10

11
            if (um.count(complement))
12
            {
13
                return {um[complement], i};
14
            }
15

16
            um[nums[i]] = i;
17
        }
18

19
        // No solution found
20
        return{};
21
    }
22
};