Two sum LeetCode problem explained in simple terms using Dictionary

on

 


leetcode-day3

Two Sum

Problem

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]
Output: 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]

Let’s start

As usual, our main goal is to solve the problem and at the same time achieve the best time complexity with minimal space complexity. If you are a beginner to problem solving or trying data structure problems, I suggest you start with a brute force approach and then try to optimize your solution to the best time/space complexity.

Analysis

  1. Before jumping into a solution or pseudocode, read the problem statement a couple of times and make sure to understand it well.
  2. To start with, we can check each number in the array by comparing its sum with all other numbers. This will give O(\( n^2 \)) complexity with a simple brute force approach.
  3. Let’s see how we can do this better. Let’s assume the two numbers we need to find are A and B. If A is the current element in our loop iteration. B is the other number in the same array.
    A + B = target. then, B = target - A.
  4. How about if we could store/keep track of (target - A ) in a data structure, when we traverse each number in the array? We will only store the difference in a set, if it doesn’t already exist. If it exists already, then the current indice and stored value indice are the answer. We will just return it.
  5. Dictionary is the best data structure candidate for our solution in C#. In Java, we can go with Hashtable.

Difference between Hashtable and Dictionary in C#

Dictionary is a generic collection which is generally used to store key/value pairs. Dictionary is defined under System.Collection.Generics namespace. It is dynamic in nature which means the size of the dictionary is growing according to the need.

A Hashtable is a collection of key/value pairs that are arranged based on the hash code of the key. It is the non-generic type of collection which is defined in System.Collections namespace.

Algorithm | Pseudocode

  • Create a Dictionary to store the (target - currentelement)'s value in the array.
  • Iterate each element in the array and get the difference with target.
  • If the difference value already exists in the dictionary, that is our answer. Return the indices of the current element and the corresponding difference value stored in the dictionary.
  • Else, store the difference value in the dictionary .
  • At the end, throw exception “No solution found” if we don’t have the difference element in our dictionary.

Let’s start writing the solution.

Loop through the elements in the array. If we find the difference element in the dictionary that matches that sums up the target. That’s it. That is our answer.

Given Array contains the two indices that sums up the target !

Solution (in C#)


    class Solution {
       public int[] TwoSum(int[] nums, int target) {
       Dictionary<int,int> dict = new Dictionary<int,int>();
        for(int i=0;i<nums.Length;i++)
        {
            int diff = target-nums[i];
            if(dict.ContainsKey(diff))
                return new int[]{dict[diff],i};
            if(!dict.ContainsKey(nums[i]))
                dict.Add(nums[i],i);
        }
        throw new Exception("No solution found");
    }
    }

Complexity

Time Complexity => O(n) => Traverse the array one time. Dictionary Add() ContainsKey operations are O(1) time.
Space Complexity => O(n) => Dictionary stores at most n number of key-value pairs.

Conclusion

This problem is a very good example of Hashtable/Dictionary Data structure usage to reduce the complexity from O(\( n^2 \)) to O(n) Do check out more examples in this category for further learning.

References

The LeetCode Problem in this article:

https://leetcode.com/problems/two-sum/

Thanks for reading this post!

I hope this article is informative and helpful in some way. If it is, please like and share! Follow me on Twitter | LinkedIn for related content.

Happy learning!

Comments

Post a Comment