DEV Community

Sahil Bondre
Sahil Bondre

Posted on

2 1

Interview Prep #3: Two Sum

Problem

We are given an array of integers and another a target integer. We'd like to find the indices of two numbers in that array such that the sum of these integers add up to the target. We cannot use the same number in the array twice and there is exactly one solution. This problem is on leetcode.

Example

input:[2, 7, 11, 15], target = 9,
output: [0, 1]
Enter fullscreen mode Exit fullscreen mode

Solution

The first thing that came to my mind is to sort the arrays. But sorting would not work because as soon as we sort the array we change the original indices of the array.

The correct solution involves the use of hash maps. We iterate over the array and store the number in a map along with the index. We also check in the map if we can find a pair for the current number to get the sum to the target.
If we can, we return the current index along with the index of the complement number from the hash map. This takes linear time complexity ie. O(n)

pair<int, int> find_sum(vector<int>& nums, int target) {
  map<int, int> m;
  for (auto i = 0; i < nums.size(); ++i) {
    int c = target - nums[i];
    if (m.find(c) != m.end()) {
      // pair found
      return {m[c], i};
    }
    m.insert({nums[i], i});
  }
  // If we cannot find a pair
  return {-1, -1};
}
Enter fullscreen mode Exit fullscreen mode

References: Leetcode
Have a beautiful day 🤗

Hostinger image

Get n8n VPS hosting 3x cheaper than a cloud solution

Get fast, easy, secure n8n VPS hosting from $4.99/mo at Hostinger. Automate any workflow using a pre-installed n8n application and no-code customization.

Start now

Top comments (1)

Collapse
 
denizbabat profile image
Deniz Babat •

good implementation but if you use this function like this @pair& find_sum(const vector& nums,const int& target)@ it will be effecincy more

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more