LeetCode problem#1

Two Sum

Solved in 6 languagesPythonC++RustC#GoJava

36 lines

1# runtime O(n^2)
2# def two_sum(nums: list[int], target: int):
3#     for i in range(0, len(nums) - 1):
4#         for j in range(i + 1, len(nums)):
5#             a = nums[i]
6#             b = nums[j]
7#             if a + b == target:
8#                 return [i, j]
9
10# time O(n)
11# space O(n)  
12def two_sum(nums: list[int], target: int):
13    seen = {}
14    for i in range(len(nums)):
15        difference = target - nums[i]
16        if difference in seen:
17            return [seen[difference], i]
18        seen[nums[i]] = i
19    return [-1, -1]
20
21def test():
22    testcase1 = two_sum([2, 7, 11, 15], 9)
23    assert testcase1[0] == 0
24    assert testcase1[1] == 1
25    assert len(testcase1) == 2
26
27    testcase2 = two_sum([3, 2, 4], 6)
28    assert testcase2[0] == 1
29    assert testcase2[1] == 2
30
31    testcase3 = two_sum([3, 3], 6)
32    assert testcase3[0] == 0
33    assert testcase3[1] == 1
34
35if __name__ == '__main__':
36    test()

1#include <vector>
2#include <cassert>
3#include <map>
4
5using namespace std;
6
7// time O(n^2)
8// space O(1)
9// vector<int> twoSum(vector<int>& nums, int target)
10// {
11//     vector<int> indices = {-1, -1};
12
13//     for (int i = 0; i < nums.size() - 1; i++) {
14//         for (int j = i + 1; j < nums.size(); j++) {
15//             if (nums.at(i) + nums.at(j) == target) {
16//                 indices.at(0) = i;
17//                 indices.at(1) = j;
18//                 return indices;
19//             }
20//         }
21//     }
22
23//     return indices;
24// }
25
26// time O(n)
27// space O(n)
28vector<int> twoSum(vector<int>& nums, int target)
29{
30    vector<int> indices = {-1, -1};
31    map<int, int> seen;
32
33    for (int i = 0; i < nums.size(); i++)
34    {
35        int difference = target - nums.at(i);
36        map<int, int>::iterator it = seen.find(difference);
37        if (it != seen.end()) {
38            indices.at(0) = it->second;
39            indices.at(1) = i;
40            return indices;
41        }
42
43        seen.insert({nums.at(i), i});
44    }
45
46    return indices;
47}
48
49void test()
50{
51    vector<int> nums = {2, 7, 11, 15};
52    auto testcase1 = twoSum(nums, 9);
53    assert(testcase1[0] == 0);
54    assert(testcase1[1] == 1);
55
56    nums.assign({3, 2, 4});
57    auto testcase2 = twoSum(nums, 6);
58    assert(testcase2[0] == 1);
59    assert(testcase2[1] == 2);
60
61    nums.assign({3, 3});
62    auto testcase3 = twoSum(nums, 6);
63    assert(testcase3[0] == 0);
64    assert(testcase3[1] == 1);
65}
66
67int main()
68{
69    test();
70    return 0;
71}

1use std::collections::HashMap;
2
3impl Solution {
4    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
5        let mut hashMap = HashMap::new();
6        let mut indices = vec![-1, -1];
7
8        for (i, num) in nums.iter().enumerate() {
9            let diff = target - num;
10            if let Some(&value) = hashMap.get(&diff) {
11                indices[0] = value;
12                indices[1] = i as i32;
13                return indices;
14            }
15            else {
16                hashMap.insert(num, i as i32);
17            }
18        }
19
20        return indices;
21    }
22}

1public class Solution {
2    public int[] TwoSum(int[] nums, int target) {
3        int[] indices = new int[] { -1, -1 };
4        Dictionary<int, int> hashMap = new Dictionary<int, int>();
5
6        for (int i = 0; i < nums.Length; i++) {
7            int difference = target - nums[i];
8            if (hashMap.ContainsKey(difference)) {
9                indices[0] = hashMap[difference];
10                indices[1] = i;
11                break;
12            }
13            else if (!hashMap.ContainsKey(nums[i])) {
14                hashMap.Add(nums[i], i);
15            }
16        }
17
18        return indices;
19    }
20}

1func twoSum(nums []int, target int) []int {
2	ans := []int{-1, -1}
3	var hashMap map[int]int = make(map[int]int)
4
5	for i, num := range nums {
6		var difference int = target - num
7
8		if index, ok := hashMap[difference]; ok {
9			ans[0] = index
10			ans[1] = i
11			return ans
12		} else {
13			hashMap[num] = i
14		}
15	}
16
17	return ans
18}

1class Solution {
2    public int[] twoSum(int[] nums, int target) {
3        int[] indices = new int[] { -1, -1 };
4        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
5
6        for (int i = 0; i < nums.length; i++) {
7            int difference = target - nums[i];
8            if (hashMap.containsKey(difference)) {
9                indices[0] = hashMap.get(difference);
10                indices[1] = i;
11                return indices; // or break;
12            }
13            else {
14                hashMap.put(nums[i], i);
15            }
16        }
17
18        return indices;
19    }
20}

How it works

The two_sum problem is a classic algorithmic challenge often encountered in coding interviews and competitive programming. The goal of the problem is to find two distinct indices in an array (nums) such that the values at those indices add up to a specified target.

Let's break down the two different approaches presented in the solution.

O(n^2) Solution:

1def two_sum(nums: list[int], target: int):
2    for i in range(0, len(nums) - 1):
3        for j in range(i + 1, len(nums)):
4            a = nums[i]
5            b = nums[j]
6            if a + b == target:
7                return [i, j]

Brute Force Approach:
- This implementation uses a nested loop to check every possible pair of numbers in the list.
- The outer loop iterates through the list starting from index 0 to len(nums) - 1.
- The inner loop iterates from i + 1 to len(nums), ensuring that we are checking every unique pair (nums[i], nums[j]).
- For each pair, it checks if their sum equals the target. If it finds such a pair, it returns their indices [i, j].
Time Complexity:
- The time complexity of this approach is O(n^2) because for each element we are potentially checking against all the other elements.
Space Complexity:
- The space complexity is O(1) because we are not using any extra data structures that grow with the input size.

O(n) Solution:

1def two_sum(nums: list[int], target: int):
2    seen = {}
3    for i in range(len(nums)):
4        difference = target - nums[i]
5        if difference in seen:
6            return [seen[difference], i]
7        seen[nums[i]] = i
8    return [-1, -1]

Using Hash Map (Dictionary):
- This solution leverages a hash map (or dictionary in Python) to keep track of the numbers we've seen and their corresponding indices.
- As we iterate through nums, for each number at index i, we calculate the difference (i.e., what we would need to find to reach target from the current number).
- We then check if this difference has already been seen and stored in the seen dictionary.
- If it has been seen, it means we have found a pair of numbers that add up to the target, and we can return their indices: the index of the difference stored in seen and the current index i.
- If difference is not in seen, we store the current number nums[i] with its index i in the seen dictionary for future reference.
Time Complexity:
- The time complexity of this algorithm is O(n) because we go through the list only once and lookups in a dictionary are O(1) on average.
Space Complexity:
- The space complexity is O(n) in the worst case because we are storing all the numbers in the dictionary.

Testing

The test function verifies that the two_sum function works as expected with a few test cases:

In the first test case, it finds that indices 0 and 1 correspond to values 2 and 7, which sum to 9.
In the second case, it finds indices 1 and 2 with values 2 and 4 that sum to 6.
The last test case checks for two instances of the number 3, confirming they are correctly identified as indices 0 and 1.

If you run the test function under the if __name__ == '__main__': block, all assertions will pass, confirming that the function is working correctly.

Written by AI from the code above, so double-check anything important.

How it works

The provided code is an implementation of the "Two Sum" problem, which is a common algorithmic challenge on platforms like Leetcode. The goal is to find two distinct indices in a list of integers such that the numbers at those indices add up to a specific target value.

Let's break down the code step by step:

The Problem Statement:

Given an array of integers nums and an integer target, you need to find indices i and j such that nums[i] + nums[j] == target and return the indices in a vector. The numbers in nums can be assumed to be unique, and there will always be exactly one solution.

Solution Overview:

The solution uses two methods (one is commented out) to solve the problem. The second method is more efficient in terms of time complexity and is the one that is active in the code.

First Method (Commented Out):

Time Complexity: O(n^2)
Space Complexity: O(1)
Approach:
- Use a nested loop to check every combination of two numbers.
- For every pair of indices (i, j), check if nums[i] + nums[j] == target.
- If found, store the indices and return them.
- This method is straightforward but inefficient for larger arrays since it checks every pair.

Second Method (Active Code):

Time Complexity: O(n)
Space Complexity: O(n)
Approach:
- This method uses a single loop and a hash map (implemented using the STL map).
- As you iterate through the nums array, calculate the difference between the target and the current number: difference = target - nums[i].
- Check if this difference exists in the seen map (which keeps track of the numbers seen so far and their respective indices).
- If it exists, it means we've already encountered a number which, together with the current number, sums to the target. In this case, extract the corresponding index and return both indices.
- If it doesn't exist, insert the current number and its index into the seen map for future reference.
- This method only requires a single pass through the array and uses additional space for the hash map.

Testing:

The function test() verifies the correctness of the twoSum function by:

Creating several test cases with known outputs.
Using assert statements to ensure that the returned indices match the expected results.

Main Function:

The main() function simply invokes the test() function and returns 0 indicating successful execution.

Summary:

The code offers a solution to the two-sum problem with significant efficiency gains by utilizing a hash map to store previously seen numbers and their indices.
The first method is naïve and less efficient, while the second is optimized and able to handle larger inputs effectively.

Written by AI from the code above, so double-check anything important.

All problems

Problem statements belong to LeetCode and are on leetcode.com. We're not affiliated with LeetCode.