Finding the pair with a given sum a C++ solution for the question asked in the Amazon interview mentioned in the Leetcode. Given a list of positive integers nums and an int target, return indices of the two numbers such that they add up to a target - 30.
Conditions:
- You will pick exactly 2 numbers.
- You cannot pick the same element twice.
- If you have muliple pairs, select the pair with the largest number.
Example 1:
Input: nums = [1, 10, 25, 35, 60], target = 90
Output: [2, 3]
Explanation:
nums[2] + nums[3] = 25 + 35 = 60 = 90 - 30
Example 2:
Input: nums = [20, 50, 40, 25, 30, 10], target = 90
Output: [1, 5]
Explanation:
nums[0] + nums[2] = 20 + 40 = 60 = 90 - 30
nums[1] + nums[5] = 50 + 10 = 60 = 90 - 30
You should return the pair with the largest number.A question asked in Amazon interviews. A leet code problem at https://leetcode.com/discuss/interview-question/356960
The brute force solution is as follows (in C++):
For an optimal solution with a time complexity of O(n), I followed the steps:
- Create a key value map with value of the vector and index
- Subtract the target with each element in the vector and look for the remaining number in the map. If it matches and the max number is the current one then update the tuple.
Implementation is as below, I added only the code snipped which can be replaced with the algorithm above:
Look for more such algorithms here