# Two Sum - Solution to LeetCode Problem #1

While this is an extremely simple problem, it has been asked in Apple, Amazon, Adobe, Google, Microsoft, Meta and tons of other companies.

## Problem Statement

Given an array of integers `nums` and an integer `target`, return the 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.

## Examples

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

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

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

## Approach 1

The simplest, and the most straightforward approach is to have nested loops, the outer loop having an iterative variable `i` starting from `0` to `n-2`, and the inner loop with `j` from `i+1` to `n-1`  where n is the length of the array `nums`. Check if `nums[i] + nums[j] == target` and if true, return `(i, j)`.

Since we know that we would always have a solution, we do not need to explicitly handle a case where this would not have a solution. But, it would be recommended to return something like `(-1, -1)` or `null` just to impress your recruiters (obviously after asking them about what you're expected to return if there is no solution).

This approach has a Time Complexity of O(N2) and a Space Complexity of O(1). So, let's look at a few other solutions that are a bit more efficient.

## Approach 2 When in doubt, throw in a HashMap 😁😁

HashMap provides access to its contents in O(1) time. So, we can have an HashMap called `hmap` where the key would be the element and the value would be its index in the `nums` array.

We then iterate through the `nums` array with `i` from `0 to n-1` where n is the length of the array. For each `nums[i]`, check if `target - nums[i]` is present in `hmap`. If it is present, return `(i, hmap[target - nums[i]])`, else add `nums[i], i` to the HashMap and continue.

This approach has a time complexity of O(N) and space complexity of O(N), which is miles ahead when compared to our previous approach.

## A Similar Question

Suppose the interviewer asks you for the integers in the array instead of their indices, then this is another way you can solve the problem ⬇.

We can start by sorting our array and then have two pointers, one at the beginning `start`, another at the end called `end` and then add the values at these positions and compare the value with `target`.

If it's greater than `target`, we could move the pointer `end`, one step to the left. If it's lesser than `target`, we could move the pointer `start`, one step to the right.

We repeat this process till `nums[start] + nums[end] = target`. Assuming we use a decent sorting algorithm, we would get a time complexity of O(N log N) for the sorting part, and complexity of O(N) for moving the pointers. By the rules of Big O notation, the time complexity would be O(N log N + N) = O(N log N).

Hope you enjoyed this article. If this helped you, please do subscribe for more.

We're always looking for feedback, and would be happy if you could share the same over here.