Two Sum

Try to solve the Two Sum problem.

We'll cover the following

Statement#

For the given array of integers arr and a target t, you have to identify the two indices that add up to generate the target t. Moreover, you can’t use the same index twice, and there will be only one solution.

Note: We will assume that the array is zero-indexed and the output order doesn’t matter.

Constraints:

  • 2≤2 \leq arr.length ≤103\leq 10^3
  • −109≤-10^9 \leq arr[i] ≤109\leq 10^9
  • −109≤-10^9 \leq t ≤109\leq 10^9
  • Only one valid answer exists.

Examples#

Created with Fabric.js 3.6.6 Input Output Sample example 1 arr 1 10 8 4 9 target 17 [2, 4]

1 of 3

Created with Fabric.js 3.6.6 Output Input Sample example 2 arr 5 12 15 21 6 17 target 33 [1, 3]

2 of 3

Created with Fabric.js 3.6.6 Output Input Sample example 3 arr -2 2 11 15 -3 target 8 [2, 4]

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Two Sum

1

What is the output for the following input?

arr = [3, 9, 11, 12, 17, 21]

t = 26

A)

[0, 5]

B)

[1, 4]

C)

[2, 3]

D)

[3, 5]

Question 1 of 30 attempted

Try it yourself#

Implement your solution in main.py in the following coding playground.

The optimal solution to this problem runs in O(n) time and takes O(n) space.

Python
usercode > main.py
Input #1
Input #2
%0 node_01 2 node_11 4 node_21 6 node_31 8 node_41 10 node_51 19
Visualization for Input #1
Two Sum

You might want to go over the Knowing What To Track pattern again.

Solution: Ransom Note

Solution: Two Sum