So I am a beginner in Competitive Coding and started practicing Leetcode questions.
The question 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. 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]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
I followed a simple approach or you can call a brute force approach:
def twosum(nums,target): for i in range(0,len(nums)): for j in range(0,len(nums)): if i != j and nums[i] + nums[j] == target: return i,jWhat can I do to make my code efficient and better?
15 Answers
You can create a dict to store the values and their indices, and check by subtracting (target - current_value) in the dict; since dictionary lookups are constant time, in that way you can find the solution in one go:
def twosum_O_n(number, target): hsh={} # Use enumerate to get both current index, and value for i, curr_value in enumerate(number): # calculate how much it is off target other_part = target - curr_value # check if that part is in the dictionary if other_part in hsh: # if it is, return that value, and current_index return [hsh[other_part], i] else: # otherwise store the current index with current value as key hsh[curr_value] = i
>>> twosum_O_n([2,7,11,15], target = 9)
[0, 1]
>>> twosum_O_n([0, 5, 11, 4], target=11)
[0, 2]
>>> twosum_O_n([5, 10, -2, 12], target=8)
[1, 2]Some timings:
>>> num = list(range(10000))
>>> target = num[-1] + num[-2]
>>> %timeit twosum(num, target)
12.3 s ± 276 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit twosum_O_n(num, target)
1.44 ms ± 21.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)As a general rule if you need indexes, use enumerate not range(len(..))
def twosum(nums,target): for ind1, i in enumerate(nums): for ind2, j in enumerate(nums): if ind1 != ind2 and i + j == target: return ind1, ind2That will be more efficient I think.
I would personally go one step further and use itertools.product():
import itertools
def twosum(nums,target): for (ind1,i), (ind2,j) in itertools.product(enumerate(num), repeat=2): if ind1 != ind2 and i + j == target: return ind1, ind2Here's how to go about this:
- Step 1: Iterate through the list from left to right
- Step 2: Check if the value in the list is less than or equal to 9. If it is more than 9, ignore the element. Any number greater than 9 when added will NOT give us the desired result. If you expect negative numbers in your list, then skip the less than or equal to 9 check.
- Step 3: If number is less than or equal to 9, then check if the difference (9-the number) is available in the list (from current index + 1 to end of list). If the answer is yes, then you have a match
- Step 4: Print the current index (item #1), and the new index for the remainder value of 9-the number. The index for the second one will be: current index + 1 + index of (9-the number) when you check from [index+1:].
The code for this is:
nums = [2,7,11,15]
target = 9
for i,n in enumerate(nums): if n <= 9 and i < len(nums)-2 and ((9 - n) in nums[i+1:]): print ('Index of the two integers are: ', i, i+1+nums[i+1:].index((9 - n))) break else: print ('No Match')A simple way to find matching pairs of values is to use set intersection between values and their complement to the target. This will directly give the pair of values that add up to the target and only leaves one special case which is the presence of a single value that is half of the target (handled using min/max on matches).
def twosum(nums,target): values = set(nums).intersection(target-n for n in nums) # matching values v1,v2 = min(values),max(values) # complementary values i1 = nums.index(v1) # indexes of 1st value i2 = nums.index(v2,(i1+1)*(v1==v2)) # index of second value return i1,i2output:
nums = [2,7,11,15]
target = 9
print(twosum(nums,target))
# 0 1Processing small amounts of data is faster with simpler / less operations on the data, if the array is in the millions it will be worth it to convert it into a tuple.
from random import randint
long_list = []
for _ in range(10000): long_list.append(randint(0, 500))
target = max(long_list)
def n_of_two_in(num_list, n): for i in range(len(num_list)): if num_list[i] < n: comp_val = n - num_list[i] if comp_val in num_list: return i, num_list.index(comp_val, i)
if __name__ == '__main__': print(n_of_two_in(long_list, target))Sayandip's timings are a big surprising, my function and his run in average of 3 µs, with mins of 1µs and maxs of 6µs depending on the array generation.
