Python Data Structures and Algorithms Tutorial

Two Sums LeetCode Problem Solution

❮ Previous Next ❯

In this tutorial, we will explore the solution to the well-known LeetCode problem 'Two Sum'.

Problem

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]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

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

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Solution:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        my_dict = {} 
        
        for i, num in enumerate(nums):
            complement = target - num  
            
            if complement in my_dict:
                return [my_dict[complement], i]
            
            my_dict[num] = i

We opted for this approach because it's explicitly stated that the solution's time complexity must not exceed O(n^2), making the use of nested loops unsuitable.

❮ Previous Next ❯

Python Data Structures and Algorithms Tutorial

Python Data Structures and Algorithms Tutorial

Introduction to Data Structures and Algorithms

Python Lists

Popular LeetCode List Questions

Python Dictionaries

Popular LeetCode Dictionary Questions

Linear Data Structure

Non Linear Data Structure

Two Sums LeetCode Problem Solution

Important Links