1. Two Sum - Leetcode Easy

Problem statement

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]

Approach 1

Iterate through the array, select each element and check if there is any other element in the remaining array which when added to the first one gives the target value. It is guaranteed that one such pair exists. So, we need to return their indices.

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

        return [-1, -1]

Time complexity - O(n^2) - due to nested for loops.
Space complexity - O(1).

Approach 2

Iterate through the array and check for each element if the required number to sum up to target is already present in the hashmap. If there is one, return an array with both of it's indices. Else, add current item to the hashmap with it's index as value and item as key.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashMap = {}
        for i in range(len(nums)):
            if target - nums[i] in hashMap: # If present in hashmap
                return [hashMap[target-nums[i]], i]
            else:
                hashMap[nums[i]] = i # Add item as key and index as value into hashmap

        return [-1, -1]

Conclusion

Do let me know if I missed any other approach.

Do follow me for more such explanations.
Let's connect on: Twitter LinkedIn Showwcase