Solving the Two Sum Problem with C++, Python, and Better Approaches

Introduction

In programming, we often encounter problems where we need to find a solution that satisfies certain conditions. The Two Sum problem is one such example, where given an array of integers nums and an integer target, we need to return indices of the two numbers such that they add up to target. In this blog post, we will explore three different approaches to solving the Two Sum problem using C++, Python, and a better approach.

Problem Statement

The problem statement for the Two Sum problem is as follows: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Algorithmic Approach

My Approach

The naive approach to solving the Two Sum problem is to use a nested loop to check each pair of numbers and see if they add up to the target. This approach has a time complexity of O(n^2), which is not efficient for large arrays.

Better Approach

A better approach is to use an unordered map to store the indices of visited elements in a single loop. This approach has a time complexity of O(n), which is much more efficient than the naive approach.

Testing

We can test the solution by passing in different values of the array and target to check if it returns the correct indices.

Analysis of Your Interpretation

We can see that the better approach using an unordered map in C++ and a dictionary in Python is much more efficient than the naive approach using nested loops. The better approach has a time complexity of O(n), while the naive approach has a time complexity of O(n^2 ). Therefore, it is important to choose the right data structure and algorithm to solve a problem efficiently.

Conclusion

In this blog post, we have explored three different approaches to solve the Two Sum problem using C++ and Python.

Code Implementation

My C++ Code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> Index;
        int flag=0;
        for(int i=0; i< nums.size(); i++){
            for(int j=0; j< nums.size(); j++){
                if( i==j )
                continue;
                else if((nums.at(i) + nums.at(j) ) == target){
                    Index.push_back(i);
                    Index.push_back(j);
                    flag=1;                   
                    break;
                }
            }
            if(flag)
            break;
        }
        return Index;
    }
}

Improved Approach

class Solution {
public:
    vector<int> twoSum(vector<int> &nums, int target) {
        unordered_map<int, int> visited;
        int len = nums.size();
        for (int i = 0; i < len; ++i) {
            int n = nums[i];
            int complement = target - n;
            if (visited.count(complement)) {
                return {visited[complement], i};
            }
            visited[n] = i;  
        }
        return {};
    }
};

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:

        d = {}
        for i, j in enumerate(nums):
            r = target - j
            if r in d: return [d[r], i]
            d[j] = i