Leetcode two sum solution python

LeetCode #1 — Two Sum

Hello happy people 👋! Today we are going to discuss the very first problem on the LeetCode.

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.

So, we have to find two numbers among all the numbers in an array such that when they are added, they give us a third number equals to target .

If nums = [2,7,11,15] and target = 9, then we should return 2 and 7 because 2 + 7 = 9

In simpler words, we need to find —

c = a + b where, c => target a and b => elements from the given array

Also, the given constraints suggest that there is only ONE valid answer along with the ranges of the elements in the array and the target.

After we have analyzed our problem, now it’s time to think about the solution.

The first solution that comes to mind is —

• Take one element
• Add this element with every other element
• After adding, compare the sum with the given target
• If the sum is equal to the target, return the indices of these two elements
• If the sum is not equal to the target, we check for the next pair

Pretty simple, eh 😉? Let’s analyze the time and space complexities.

Let’s say the array has n elements then —

For 1st element - we will check for (n - 1) elements For 2nd element - we will check for (n - 2) elements For 3rd element - we will check for (n - 3) elements and so on. Thus, the total iterations would be - [(n - 1) + (n - 2) + (n - 3) + . + 2 + 1]

If we simplify the above expression we will get —

Thus, our time complexity would be — O(n 2 ).

Since we are not using any extra data structure hence our space complexity would be O(1).

This approach is simple and intuitive but it takes quadratic time which is bad for large inputs. Let’s see if we have any efficient approach to solve this problem. As a matter of fact, we do 😄!

In the earlier approach, we did what naturally came to us. But let’s try to really think through this problem. Hmm… 🤔

When we were analyzing the problem, we came across the following equation

but can we write the above equation as —

Of course we can. We are mathematicians after all 😁.

The benefit of writing this equation is that now we can iterate through the array only once and calculate the difference of target (c) and the current element (a) and find the other element (b) . The idea is as follows —

• Loop through the array
• Check if we have encountered the current element before
• If we have, we will return the index of this element and the index of the difference of the target and the current element . We will only encounter this element before only if we have saved the difference of target and the element which when added to the current element gives the target itself. This is confusing I know but once it clicks, it’s very obvious.
• If we haven’t, the we will save the difference of the target and current element .
• Repeat the process

Since we need to store our difference , we need a data structure which can store the difference and its corresponding index. So what do you think, which data structure can help us? Of course, we need a Map where we will store the difference as key and the corresponding index as value .

Since we are iterating the array only once, the time complexity would be O(n).

Since we need a Map of the size of the array, the space complexity would be O(n).

Now we have an approach to solve this problem, let’s write some code —

package org.redquark.tutorials.leetcode; import java.util.Arrays; import java.util.HashMap; import java.util.Map; public class TwoSum  public int[] twoSum(int[] nums, int target)  // Array to store result int[] result = new int[2]; // This map will store the difference and the corresponding index MapInteger, Integer> map = new HashMap>(); // Loop through the entire array for (int i = 0; i  nums.length; i++)  // If we have seen the current element before // It means we have already encountered the other number of the pair if (map.containsKey(nums[i]))  // Index of the current element result[0] = i; // Index of the other element of the pair result[1] = map.get(nums[i]); > // If we have not seen the current before // It means we have not yet encountered any number of the pair else  // Save the difference of the target and the current element // with the index of the current element map.put(target - nums[i], i); > > return result; > >

from typing import List def twoSum(nums: List[int], target: int) -> List[int]: # List to store results result = [] # Dictionary to store the difference and its index index_map = > # Loop for each element for i, n in enumerate(nums): # Difference which needs to be checked difference = target - n if difference in index_map: result.append(i) result.append(index_map[difference]) break else: index_map[n] = i return result

var twoSum = function (nums, target)  // Array to store the result result = []; // Map to store the difference and its index index_map = new Map(); // Loop for each element in the array for (let i = 0; i  nums.length; i++)  let difference = target - nums[i]; if (index_map.has(difference))  result[0] = i; result[1] = index_map.get(difference); break; > else  index_map.set(nums[i], i); > > return result; >;

package org.redquark.tutorials.leetcode fun twoSum(nums: IntArray, target: Int): IntArray  // Array to store result val result = IntArray(2) // This map will store the difference and the corresponding index val map: MutableMapInt, Int> = HashMap() // Loop through the entire array for (i in nums.indices)  // If we have seen the current element before // It means we have already encountered the other number of the pair if (map.containsKey(nums[i]))  // Index of the current element result[0] = i // Index of the other element of the pair result[1] = map[nums[i]]!! break > else  // Save the difference of the target and the current element // with the index of the current element map[target - nums[i]] = i > > return result >

I hope you liked this post. Here, we solved the very first problem on LeetCode in O(n) time and O(n) space.

You can find the complete source code on GitHub. If you find it useful, consider giving it a star ⭐.

• Java
• Python
• JavaScript
• Kotlin Feel free to share your thoughts about this post in comments’ section. I’d love to hear your feedback.

Happy coding 😄 and Namaste 🙏!

Источник

LeetCode Problem 1 Solution in Python

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

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.

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

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

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

Constraints:

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.

Источник

Разбор задачи 1 Two Sum LeetCode.com

Учитывая массив целых чисел nums и целое число target , верните индексы двух чисел так, чтобы они составляли в сумме target .

Вы можете предположить, что каждый вход будет иметь ровно одно решение , и вы не можете использовать один и тот же элемент дважды.

Вы можете вернуть ответ в любом порядке.

Ограничения:
2 -10 9 -10 9 Существует только один правильный ответ.

Для решения этой задачи можно использовать хэш-таблицу, чтобы хранить уже просмотренные числа. Мы проходим по массиву чисел и для каждого числа проверяем, существует ли число, которое, в сумме с текущим числом, даст нам целевое число. Если такое число существует, мы возвращаем индексы текущего числа и числа из хэш-таблицы. Если такое число не существует, мы добавляем текущее число и его индекс в хэш-таблицу и продолжаем итерацию по массиву.

Этот алгоритм имеет временную сложность O(n), так как мы проходим только один раз по массиву чисел, и для каждого числа выполняем константное количество операций (проверка, существует ли число в хэш-таблице, добавление текущего числа и его индекса в хэш-таблицу). Это значительно быстрее, чем O(n2), которая была бы необходима, если бы мы проверяли все возможные пары чисел в массиве.

Решение Two Sum LeetCode пример кода на Python

class Solution: # метод twoSum принимает на вход список nums и целевое значение target # и возвращает список из двух индексов чисел в nums, сумма которых равна target def twoSum(self, nums: List[int], target: int) -> List[int]: # словарь для хранения уже просмотренных чисел seen = <> # проходимся по всем числам в списке nums с индексами for i, num in enumerate(nums): # вычисляем "комплемент" - значение, которое должно быть в списке, чтобы получить target complement = target - num # если комплемент уже был просмотрен, то нашли нужные индексы чисел if complement in seen: return [seen[complement], i] # сохраняем текущее число и его индекс в словарь seen seen[num] = i # если не найдено нужных индексов, возвращаем None return None

Решение Two Sum LeetCode пример кода на Java

class Solution < public int[] twoSum(int[] nums, int target) < // создание хэш-таблицы для хранения чисел и их индексов Mapmap = new HashMap<>(); // перебор массива чисел for (int i = 0; i < nums.length; i++) < // нахождение разности между целевым числом и текущим числом int complement = target - nums[i]; // если такая разность уже есть в хэш-таблице, значит мы нашли пару чисел if (map.containsKey(complement)) < // возвращаем индексы двух чисел return new int[] < map.get(complement), i >; > // добавляем текущее число и его индекс в хэш-таблицу map.put(nums[i], i); > // если не нашли пару чисел, выбрасываем исключение throw new IllegalArgumentException("No two sum solution"); > >

Решение Two Sum LeetCode пример кода на C++

class Solution < public: vectortwoSum(vector& nums, int target) < // создание unordered_map для хранения чисел и их индексов unordered_mapmp; for(int i = 0; i < nums.size(); i++) < // находим число-дополнение int complement = target - nums[i]; // если находим дополнение в unordered_map if(mp.find(complement) != mp.end()) < // возвращаем его индекс и текущий индекс return < mp[complement], i >; > // добавляем текущее число и его индекс в unordered_map mp[nums[i]] = i; > // если нет решения, выбрасываем исключение throw invalid_argument("No two sum solution"); > >;

Решение Two Sum LeetCode пример кода на JavaScript

/** * Функция twoSum принимает на вход массив чисел nums и целевое число target. * Она возвращает массив с двумя индексами элементов, сумма которых равна целевому числу. * @param nums - массив чисел * @param target - целевое число * @returns - массив с двумя индексами элементов * @throws - если решение не найдено */ const twoSum = function(nums, target) < // Создаем хэш-таблицу для хранения элементов и их индексов const map = new Map(); // Итерируемся по массиву nums for (let i = 0; i < nums.length; i++) < // Вычисляем разность целевого числа и текущего элемента const complement = target - nums[i]; // Если элемент-дополнительное слагаемое уже находится в хэш-таблице, // значит, мы нашли пару, сумма которой равна целевому числу if (map.has(complement)) < // Возвращаем массив с индексами элементов return [map.get(complement), i]; >// Иначе, добавляем текущий элемент и его индекс в хэш-таблицу map.set(nums[i], i); > // Если не было найдено пары элементов, сумма которых равна целевому числу, // выбрасываем исключение throw new Error('No two sum solution'); >;

Решение Two Sum LeetCode пример кода на c#

public class Solution < public int[] TwoSum(int[] nums, int target) < Dictionarymap = new Dictionary(); // создание словаря for (int i = 0; i < nums.Length; i++) < // цикл по массиву int complement = target - nums[i]; // вычисление разности между целевым значением и текущим элементом массива if (map.ContainsKey(complement)) < // проверка наличия элемента-дополнения в словаре return new int[] < map[complement], i >; // возвращение пары индексов, если элемент-дополнение найден > map[nums[i]] = i; // добавление текущего элемента в словарь > throw new ArgumentException("No two sum solution"); // выброс исключения, если решение не найдено > >

Источник