# Leetcode 1: Two Sum Problem

In this article, you will acquire knowledge of different strategies to address the fundamental and timeless interview inquiries posed by numerous organizations.

The Two Sum problem is a classic problem, and this has been listed first as one of the basic questions one has to solve when prepping for coding interviews. This is one of the most popular questions asked in such interviews.

Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe, and many more top tech companies.

## Problem Statement

In the two-sum problem, given an array of integers, nums and an integer, return the indexes of the two numbers such that they add up to the 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 order.

Test case#1

Input: nums = [2, 7, 11, 15], target = 18

Output: [1, 2] or [2, 1]
// (because nums[1] + nums[2] == 18, we return [1, 2])

Test case#2:

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

Output: [1, 2] or [2, 1]

Test case#3:

Input: nums = [3, 3], target = 6

Output: [0, 1] or [1, 0]

## Illustration

❤️
Don't forget to hit the like button and write a comment. It supports my website a lot.

## Thought process

My first thoughts when looking at this problem and the questions I have are:

1. Are we having duplicates in the array?
2. What if two pairs match the target ? Which pair should we return? Should we return both pairs?
3. What are the constraints? At least two elements should be present in the nums array.

Once the above questions are discussed with the interviewer, I will propose different ways to solve this problem. The ones that come to my mind right now are

1. Brute force / Maths formula,
2. Hashing (key, value) approach,
1. Two-pass
2. One-pass

## Approach 1: Naive / Math formula

### Intuition

The brute force approach is simple. We need to loop through each element x and find another value that equals y. The question clearly states that two numbers add up to target.

So, the math formula becomes:

x + y = target

### Algorithm

1. Initialize two nested loops to iterate through each pair of elements in the array.
• Outer loop (i) ranges from 0 to the nums.length - 1.
• The inner loop (j) ranges from i + 1 to the nums.length - 1.
2. Within the inner loop, check if the sum of elements at indices i and j equals the target.
• If true, return a new array containing the indices [i, j] as they form a pair with the desired sum.
3. If no pair is found during the iterations, return a default array [-1, -1] to indicate that no such pair exists.
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] + nums[i] == target) {
return new int[] { i, j };
}
}
}
return new int[] { -1, -1 };
}
}
// outputs [1, 2]

Or, in simple terms, we can say we find x and y can be replaced with (target - x).

class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == target - nums[i]) {
return new int[] { i, j };
}
}
}
return new int[] { -1, -1 };
}
}
// outputs [1, 2]

### Complexity analysis

1. Time complexity: O(n2), we try to find its complement by looping through the rest of the array, which takes O(n) time. Therefore, the time complexity is O(n2), where n is the length of the elements present in the array.
2. Space complexity: O(1), as no extra space is utilized.

## Approach 2: Memoization [Accepted]

### Intuition

We will use a single for-loop instead of two for-loops to apply the same math formula from the above approach. However, this comes at the cost of having an extra space.

We will apply the same math formula from the above approach, but instead of having two for-loops, we use a single for-loop to achieve this. O(N) time and space instead O(n2) from previous naive approach.

If x is the value we are expecting, then target - x is the second element. Keeping this in mind the two elements are

x, (target - x)

So, when iterating the elements, you get X value and check if (10 - X) which is Y is present in the HashTable, isn’t that easy to find? also, this is a constant O(1) lookup time.

While iterating the array elements, check if the current element x is there a target - x element.

### Algorithm

1. Initialize a HashMap (ans) to store the elements of the array and their corresponding indices.
2. Iterate through the array using a single loop.
• For each element at index i, calculate the difference as target - nums[i].
3. Check if the calculated difference exists in the HashMap (ans).
• If true, return a new array containing the indices [ans.get(difference), i] as they form a pair with the desired sum.
4. If the difference is not found in the HashMap, add the current element (nums[i]) and its index (i) to the HashMap.
5. If no pair is found during the iterations, return a default array [-1, -1] to indicate that no such pair exists.

The following solution uses HashMap.

class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> ans = new HashMap<>();

for (int i = 0; i < nums.length; i += 1) {
int difference = target - nums[i];

if (ans.containsKey(difference)) {
return new int[] { ans.get(difference), i };
}
ans.put(nums[i], i);
}

return new int[] { -1, -1 };
}
}
// outputs [1, 2]

### Complexity Analysis

Time complexity: O(n), we traverse the list containing n elements exactly twice. Since the hash table reduces the look-up time to O(1), the time complexity is O(n).

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

Coding Interview QuestionsArraysData Structures and AlgorithmsBlind75

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Members Public

## Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Members Public

## Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Members Public

## Blind 75 LeetCode Problems: Detailed Solutions

💡More problems are on the way. Blind 75 is a curated collection of 75 coding problems commonly used by fast-paced startups and the top 1% of companies. List gained popularity among software engineers for tech interviews, especially at Google, Amazon, and Facebook (Meta). Arrays 1. Two Sum 2. Best Time