Ritesh Kumar Swain

Problems Solved

Arrays

1 problem solved

1. Two Sum

Easy

Strings

0 problems solved

No problems added yet. Check back soon!

Linked Lists

0 problems solved

No problems added yet. Check back soon!

Stacks & Queues

0 problems solved

No problems added yet. Check back soon!

Trees

0 problems solved

No problems added yet. Check back soon!

Graphs

0 problems solved

No problems added yet. Check back soon!

Dynamic Programming

0 problems solved

No problems added yet. Check back soon!

Sorting & Searching

0 problems solved

No problems added yet. Check back soon!

Problem Description

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]

Solution

C++

Java

Python

JavaScript

                            class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numMap;
        
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            
            if (numMap.find(complement) != numMap.end()) {
                return {numMap[complement], i};
            }
            
            numMap[nums[i]] = i;
        }
        
        return {};
    }
};
                        

                            class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            
            if (numMap.containsKey(complement)) {
                return new int[] { numMap.get(complement), i };
            }
            
            numMap.put(nums[i], i);
        }
        
        return new int[] {};
    }
}
                        

                            class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_map = {}
        
        for i, num in enumerate(nums):
            complement = target - num
            
            if complement in num_map:
                return [num_map[complement], i]
            
            num_map[num] = i
        
        return []
                        

                            /**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
 var twoSum = function(nums, target) {
    const numMap = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        
        if (numMap.has(complement)) {
            return [numMap.get(complement), i];
        }
        
        numMap.set(nums[i], i);
    }
    
    return [];
};
                        

Complexity Analysis

Time Complexity: O(n) - We traverse the list containing n elements only once. Each lookup in the hash table costs only O(1) time.

Space Complexity: O(n) - The extra space required depends on the number of items stored in the hash table, which stores at most n elements.

Approach

We use a hash map to store the numbers we've seen so far along with their indices. For each number, we calculate its complement (target - current number) and check if it exists in the hash map. If it does, we've found our answer. Otherwise, we add the current number to the hash map and continue.

External Links

View on LeetCode View on GitHub

DSA Solutions

Arrays

Strings

Linked Lists

Stacks & Queues

Trees

Graphs

Dynamic Programming

Sorting & Searching

Two Sum

Problem Description

Solution

Complexity Analysis

Approach

External Links