LeetCode 1: Two Sum

Question

This is an easy level LeetCode question, obviously not much code to review. I'm posting C++/Java/Python here. If you'd like to review, please do so. Thank you!

Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

C++

class Solution {
public:
 vector<int> twoSum(vector<int> &nums, int target) {
 unordered_map<int, int> index_map;
 for (int index = 0;; index++) {
 auto iter = index_map.find(target - nums[index]);
 if (iter != index_map.end())
 return vector<int> {index, iter -> second};
 index_map[nums[index]] = index;
 }
 }
};

Java

class Solution {
 public int[] twoSum(int[] nums, int target) {
 int[] indices = new int[2];
 Map<Integer, Integer> map = new HashMap<>();
 for (int index = 0; index < nums.length; index++) {
 if (map.containsKey(target - nums[index])) {
 indices[1] = index;
 indices[0] = map.get(target - nums[index]);
 return indices;
 }
 map.put(nums[index], index);
 }
 return indices;
 }
}

Python

class Solution:
 def twoSum(self, nums, target):
 index_map = {}
 for index, num in enumerate(nums):
 if target - num in index_map:
 return index_map[target - num], index
 index_map[num] = index

Reference

• LeetCode 1: Two Sum
• LeetCode 1 Discussion Board

Answer 1

In the C++ solution, the map should be from int to std::size_t, since that's the standard data type for indexes.

The method signature looks strange: nums should be a const reference, and the return type should just be a std::pair. But that's probably the fault of LeetCode. Or more generally: Don't blindly assume that these coding challenges provide good code to begin with.

• Jörg W Mittag: ... or that they require good coding skills. (Many of them are basically puzzles, and not even programming puzzles but math puzzles.)
• greybeard: Then again, many resource limits are carefully crafted such that the bigger problem instances don't stand a chance to meet the constraints with (notably) sub-optimal asymptotic requirements.

Answer 2

I'm answering about java code, your method signature is the following:

public int[] twoSum(int[] nums, int target) {}

In this way you are bound to create an instance of your Solution class to call the method, without modifying the internal state of your Solution object. It would be better to use static and call the method like this:

public class Solution {
 public static int[] twoSum(int[] nums, int target) { ... your body method }
}
//in another class
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = Solution.twoSum(nums, target);

In the Leetcode contest if I understand well it has been guaranteed there is always a solution to the problem, so you will always find a couple of indexes in the for loop meeting the conditions. In a more general situation where finding a solution cannot be guaranteed it could be better return a couple of indexes like [-1, -1]. Then your method could be rewritten in the following way mantaining the same signature of the original method:

public static int[] twoSum(int[] nums, int target) {
 Map<Integer, Integer> map = new HashMap<>();
 for (int index = 0; index < nums.length; index++) {
 final int key = target - nums[index];
 if (map.containsKey(key)) {
 return new int[] {map.get(key), index};
 }
 map.put(nums[index], index);
 }
 return new int[] {-1, -1};
}

• dariosicily: @Emma You are welcome and I'm agree with you, Leetcode in this case could define the problem in a better way.

Answer 3

Just to add on to the C++ answer.

• You're assuming that a solution exists, due to lack of break condition in the loop. That may work for Leetcode; however, that is not a reasonable assumption. If a solution doesn't exist, you're in Undefined Behavior Land by accessing the array out of bounds.

• You don't need return vector<int>{index, iter-second};. Just return {index, iter->second}; works due to implicit construction of vector from an initializer list.

• Assuming it's possible that a solution doesn't exist, you might want to return an empty vector or a std::optional.

Answer 4

Methods vs. Functions

None of your three solutions are object-oriented. Note: there is nothing wrong with that, in fact, the problem domain is really anemic, so there is not much to model with objects anyway.

However, not being object-oriented, there is no need for objects here. In all three versions you use instance methods (or member functions as C++ calls them). The defining characteristics of instance methods are that they are dispatched ad-hoc (often dynamically) and thus allow for (runtime) ad-hoc polymorphism, and that they have privileged access to the internal representation of the object (via their invisible zeroth this argument, or in Python the very much visible first argument). But, you are not using either of those two features, so there is no need for those instance methods to be ... well ... instance methods. They should just be functions (or in the case of Java static methods), somewhat like this:

vector<int> twoSum(vector<int> &nums, int target) { /* ... */ }

class Solution {
 public static int[] twoSum(int[] nums, int target) { /* ... */ }
}

def twoSum(nums, target):
 // ...

Data types

There is no restriction in the problem description about the size of the numbers, nor the size of the array. In Java, int can only store numbers from -2147483648 to [phone]. In C++, int is only guaranteed to be able to store numbers from -32767 to +32767, so if your array is longer than ~30000 items or any of the numbers in the array or the target number are outside of that range, it is not guaranteed to work!

Python int can be arbitrarily large, so there is no problem, but for Java, you should use java.math.BigInteger. C++ doesn't have a suitable type, unfortunately, but you can use third-party libraries such as Boost.Multiprecision.

• Emma X: A bit of nitpicking: Member functions in C++ are statically dispatched unless declared virtual. I think your generalization over the three languages is a bit inaccurate there. The conclusion remains nonetheless the same.
• Jörg W Mittag: @EmmaX: Thanks, clarified.

Answer 5

I have one suggestion for the Java version.

Instead of using java.util.Map#containsKey, you can use java.util.Map#get.

In your code, you can make it short and faster by fetching the value and checking the nullity.

Before

if (map.containsKey(target - nums[index])) {
 //[...]
 indices[0] = map.get(target - nums[index]);
 //[...]
}

After

Integer value = map.get(target - nums[index]);
if (value != null) {
 //[...]
 indices[0] = value;
 //[...]
}