Leetcode two sum

Question

I'm currently learning c++ coming from a python background, so I'll include a solution in python and in c++ for the following problem statement:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Example 2:

Input: nums = [3,2,4], target = 6

Output: [1,2]

I would like to hear your feedback / suggestions for performance improvements / other suggestions. Here's the link

two_sum.py

def two_sum(nums: list, target: int):
    for i, n in enumerate(nums):
        match = target - n
        if match in (rest := nums[i + 1:]):
            match_at = rest.index(match)
            return i, match_at + i + 1


if __name__ == '__main__':
    if result := two_sum([2, 7, 11, 15], 22):
        print(f'Indices:\n{result}')
    else:
        print('No matches found')

Leetcode stats:

Runtime: 772 ms, faster than 36.98% of Python online submissions for Two Sum. Memory Usage: 14.4 MB, less than 49.82% of Python online submissions for Two Sum.

two_sum.h

#ifndef LEETCODE_TWO_SUM_H
#define LEETCODE_TWO_SUM_H
#include <iostream>
#include <vector>
using std::vector;
using std::cout;
using std::endl;


vector<int> two_sum_solution(vector<int> &nums, int target) {
    vector <int> results;
    for (int i = 0; i < nums.size(); ++i) {
        int match = target - nums[i];
        for (int j = i + 1; j < nums.size(); ++j) {
            if (nums[j] == match) {
                for (int index_match : {
                            i, j
                        })
                    results.push_back(index_match);
            }

        }
    }
    return results;
}
#endif //LEETCODE_TWO_SUM_H

main.cpp

#include <vector>
#include "two_sum.h"
using std::vector;


int main() {
    vector<int> v1{2, 7, 11, 15};
    vector<int> v = two_sum_solution(v1, 22);
    if (!v.empty()) {
        cout << "Indices:" << endl;
        for (auto i: v)
            cout << i << " ";
    }
    else (cout << "No matches found");
}

Leetcode stats:

Runtime: 384 ms, faster than 34.03% of C++ online submissions for Two Sum. Memory Usage: 9.3 MB, less than 12.99% of C++ online submissions for Two Sum.

Answer 1

I am not an expert in C++ but I can give a feedback about the Python solution.

Your current solution runs in \$O(n^2)\$. Basically, for each number n of the input nums, find target - n in nums. How to improved it?

The second part of the algorithm can be improved from \$O(n)\$ to \$O(1)\$. Instead of looking up target - n in a list, you can use a dictionary:

def two_sum(nums: list, target: int):
    num_index = {}
    for i, n in enumerate(nums):
        match = target - n
        if match in num_index:
            return num_index[match], i
        num_index[n] = i
    return -1

Results:

Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB

Answer 2

Only include the header files that you need

In your two_sum.h file, you don't need iostream, since you're not using any of its functionality. Remember that #include literally copy-pastes the file, so if you're including this header file in multiple files, it might potentially slow down your compilation times.

Split declarations and definitions

Typically, you would split your files into two parts: the header file (normally ending with *.h, *.hpp, *.hh) and the source file (normally ending with *.cpp, *.cc). The header file only consists of the declarations and the source file contains the implementation.

So in your case, your header file will look like this:

two_sum.h

#ifndef LEETCODE_TWO_SUM_H
#define LEETCODE_TWO_SUM_H

#include <vector>

std::vector<int> two_sum_solution(std::vector<int> &nums, int target);

#endif // LEETCODE_TWO_SUM_H

and your source file will look like this:

two_sum.cpp

#include "two_sum.h"
std::vector<int> two_sum_solution(std::vector<int> &nums, int target)
{
     ...
}

In fact, if you try to include your two_sum.h (with the implementation) into multiple files, you would be breaking the One-Definition Rule. Your source files would contain multiple definitions of the same function, and the linker will spit out an error. One way to get around is to mark the functions inline, but you most likely want to do the former.

No using namespace in the header files

Don't do using namespace or any of its variant in a header file. Since the header file is copy pasted throughout multiple source files, it has a potential to cause annoying errors. See here

Use const reference

Since two_sum_solution is not modifying the nums vector, pass it by const reference.

size_t vs int for array indices

Consider using size_t instead of int for array indices

Use auto as much as possible

There are a couple of instances in your code where you can use auto instead of specifying the type. Examples:

auto match = target - nums[i]; auto v = two_sum_solution(v1, 22);

The inner-most loop is pointless

Simply do

results.push_back(i);
results.push_back(j);

Also, once you've found the solution, you might want to return the result immediately.

Answer 3

You can perhaps improve the performance by creating a map of value -> index in the first iteration over the given array.

Currently, Your program does the following (time complexity):

1. iterate over all index, value pairs of the array (\$ O(n) \$)
2. search for target - value in the array (\$ O(n) \$)
3. lookup index of target - value (\$ O(n) \$)

And since these are all nested, you get to \$ O(n^2) \$ (it isn't \$ n^3 \$ because last lookup is not being done for each iteration).

---

My proposed solution:

1. Create a map/dict of {value: index} (\$ O(n) \$)
2. Iterate over index, value of array (\$ O(n) \$)
3. Lookup and return index from the map/dict (\$ O(1) \$)

---

def two_sum(numbers: list[int], target: int):
    lookup: dict = {
        value: index
        for index, value in enumerate(numbers)
    }
    for index, value in enumerate(numbers):
        match = target - value
        if search_index := lookup.get(match):
            return index, search_index
    return None

Answer 4

This is interesting to me because I come from a C background and started using Python the past few years for work, so I've had the reverse path as you. When I started Python, I greatly preferred solutions like yours because looping through lists is so explicit and clear.

However, I since learned that more proficient Python programmers at work understand my code better when I use the standard library. Once I began to invest in learning those tools, it had the double effect of 1) making my code more succinct and 2) being more efficient in time and/or space.

In this case, I would solve the problem with combinations from the itertools package:

from itertools import combinations

def two_sum(nums, target):
    pairs_with_indices = combinations(enumerate(nums), 2)

    # result is a generator comprehension.
    winning_pairs = ((index_i, index_j)
                     for (index_i, i), (index_j, j) in pairs_with_indices
                     if sum((i, j)) == target)

    # Insert as much error checking as you need...
    return next(winning_pairs)

There's probably an even better more succinct and clear solution using Numpy, which is effectively standard library in my line of work (data science) but that's not true everywhere.

One thing that's different than your code: there is no room for off-by-one-errors. In my experience, code like this

if match in (rest := nums[i + 1:]):
        match_at = rest.index(match)
        return i, match_at + i + 1

is easy for me to write, hard to read and maintainability spans the whole gambit from easy to impossible. In other words, managing indices manually in Python gives me just enough rope to hang myself with, and standard library functions have been a great alternative.

Answer 5

Know your containers

std::unordered_map is your friend in this problem. Whenever you've never previously seen a number, simply use the operator[] or insert function to add the number and its index. When using find, it will return an iterator, which is a key-value pair.

eg: auto location = m.find(numToFind);

location->first is your key, and location->second is your value

When you return, don't use push_back

You can simply return an initializer list like: {i,j}.