Two Sum Problem- LeetCode

Problem Statement

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice. Example:-

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Intuition

	class Solution {
	public:
	vector<int> twoSum(vector<int>& nums, int target) {
	vector<int> arr;
	for (int i=0; i < nums.size(); i++){
	int rem = target – nums[i];
	for (int j=0; j < nums.size(); j++){
	if (rem == nums[j] && j!=i){
	arr.push_back(i);
	arr.push_back(j);
	i= nums.size();
	}
	}
	}
	return arr;
	}
	};

view raw gistfile1.txt hosted with ❤ by GitHub

Brute Force Approach in C++

Complexity Analysis

• Time complexity : O(n^2). For each element, we try to find its complement by looping through the rest of array which takes O(n) time. Therefore, the time complexity is O(n^2).
• Space complexity : O(1)

Improvement

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

view raw TwoSumJava.txt hosted with ❤ by GitHub

Two- Pass Hash Table Approach

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 exactly n elements.

Explanation

An algorithm is a well defined list of steps for solving a particular problem. There are two major factors which govern the efficiency of an algorithm.

1. Space : the data storage (RAM, HDD etc.)consumed in performing a given task.
2. Time : time (computation time or response time)consumed in performing a given task.

Space-time trade-off in a general sense state that :

You can decrease the time complexity of your algorithm in exchange for greater space, or consume lesser space in exchange for slower executions. Time and space is usually calculated in terms of big O. big O notation is how an algorithm’s running time or space requirements grow as the input size grows.

Feel free to post queries.