LeetCode Problem 1 Solution in Python

Discussing the approach for an optimal solution to Two Sum problem in LeetCode

Dec 8, 2021

3 min read

Interview Questions

Photo by Ashley West Edwards on Unsplash

Introduction

LeetCode is a platform that gives access to thousands of programming problems and helps users enhance their skills and get prepared for technical interviews that are usually part of the recruitment process for Engineering and ML positions.

In today’s short guide we will explore the first problem called Two Sum and attempt to solve it in an optimal way. In technical interviews, it’s not only important to derive a solution for a particular problem but the time complexity is also something you will usually be questioned about.

The 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]
Output: 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.

Source: LeetCode

A not so..optimal solution

The most simple approach would require two nested loops where the outer loop iterates over all the elements of the list and the inner loop iterates from the current index of the outer loop up to the end of the list.

from typing import List

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

The time complexity of the above solution is O(n²) which is pretty..bad.

Solving the problem in O(n)

This problem would be solved more efficiently if we could somehow iterate over the list of numbers just once. To do so, we can take advantage of a dictionary.

In the solution below, we first create an empty dictionary where we are going to store the value and the index of each list element as a key-pair respectively. Then we iterate through the indices and values of the list containing our numbers. If the difference between the target and the current value in the list is already included as a key in the dictionary, then it means that the current value and the value stored in the dictionary is the solution to our problem.

Otherwise, we simply add the value and index as a key-value pair in our dictionary and keep iterating until we find the solution we are looking for.

from typing import List

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        values = {}
        for idx, value in enumerate(nums):
            if target - value in values:
                return [values[target - value], idx]
            else:
                values[value] = idx

In the solution above, we iterate over our list of numbers just one and thus the time complexity of the algorithm is O(n) which is way better than the solution implemented previously!

Final Thoughts

In today’s short article we discussed a couple of approaches around the Two Sum problem in LeetCode. Initially, we created a simple solution that would result in a poor performance, but we then took advantage of Python dictionaries in order to implement a solution with time complexity O(n).

Become a member and read every story on Medium. Your membership fee directly supports me and other writers you read. You’ll also get full access to every story on Medium.