Two Sum🎏

Photo by Crissy Jarvis on Unsplash

Question

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:

Example 2:

Example 3:

Constraints:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists.

Java Solution

I have written 3 solutions for the same problem with three different time complexities.

O(n²) or Quadratic time
This is a simple solution that uses the Brute Force method to check every possible pair in an array to find the target solution.
The outer loop compares each element to the rest of the n-1 elements, for each element in the array thus time complexity is O(n²).

Code

O(n * n/2)
The below code also uses the brute force method, but the inner loop runs only half the size of the array instead of going through the whole array each time.
Thus the time complexity of the outer loop is O(n) because it goes through the whole array, and the time complexity of the inner loop is O(n/2), combining both we get O(n * n/2) as the time complexity for the below code.

Code

O(n) or linear time
The time complexity of the below code is O(n), it goes through the whole array only once, this was possible because of the constant time complexity of hashmap for getting an item out of it.

Code

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store