Problem 1: Summation Of Weights

You have a list of items in a warehouse and we need to find two items whose combined weight equals a specific target weight. For example, imagine you are managing an inventory of various products at a distribution center.

Given a list of product weights [2kg, 3kg, 8kg, 6kg, 4kg] and a target weight of 9kg, your task is to find the indices of the two products whose combined weight equals the target. In this case, the output would be [1, 3] because the items at positions 1 and 3 (3kg and 6kg) add up to the target weight of 9kg.

Another example could be a list of product weights [2kg, 3kg, 4kg] with a target weight of 9kg. The output would then be [0, 1, 4], since the items at positions 0, 1, 4 and 2 (2kg, 3kg, 4kg) add up to the target weight.

In some cases, you might have duplicate product weights in your inventory. For example, given a list of product weights [3kg, 3kg] with a target weight of 6kg, the output would be [0, 1].

The constraints in this problem ensure that there are no duplicates within the input and only one solution exists for each input.

In terms of complexity, the algorithm should ideally have less than O(n^2) time complexity. One way to achieve this is by iterating through the list once and keeping track of the complement (target - current number). If we find a complement that matches any previously seen product weight, it means we’ve found the two products whose combined weight equals the target.

This approach reduces the problem from quadratic to linear time complexity while still maintaining readability and simplicity.

Example 1:

Input: weights = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because weights[0] + weights[1] == 9, we return [0, 1].

Example 2:

Input: weights = [3,2,4], target = 6 Output: [1,2]

Example 3:

Input: weights = [3,3], target = 6 Output: [0,1]

Constraints:

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

Java Solution

class Solution {
  public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> numToIndex = new HashMap<>();

    for (int i = 0; i < nums.length; ++i) {
      if (numToIndex.containsKey(target - nums[i]))
        return new int[] {numToIndex.get(target - nums[i]), i};
      numToIndex.put(nums[i], i);
    }

    throw new IllegalArgumentException();
  }
}

The algorithm leverages a hash map (unordered_map in C++, HashMap in Java, dictionary in Python, and Map in JavaScript). It iterates through the given 'nums' array and calculates the complementary value (target - current value). If the complementary value is already in the hash map, it means that we found a solution, and we return those indices. If the complement is not in the hash map, we store the current element in the hash map with its index. If the algorithm doesn't find the solution, it returns an empty array or throws an exception (in Java).

This approach has a time complexity of O(n) and a space complexity of O(n) as well.

C++ Solution

class Solution {
 public:
  vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> numToIndex;

    for (int i = 0; i < nums.size(); ++i) {
      if (const auto it = numToIndex.find(target - nums[i]);
          it != numToIndex.cend())
        return {it->second, i};
      numToIndex[nums[i]] = i;
    }

    throw;
  }
};

The algorithm leverages a hash map (unordered_map in C++, HashMap in Java, dictionary in Python, and Map in JavaScript). It iterates through the given 'nums' array and calculates the complementary value (target - current value). If the complementary value is already in the hash map, it means that we found a solution, and we return those indices. If the complement is not in the hash map, we store the current element in the hash map with its index. If the algorithm doesn't find the solution, it returns an empty array or throws an exception (in Java).

This approach has a time complexity of O(n) and a space complexity of O(n) as well.

Python Solution

class Solution:
  def twoSum(self, nums: list[int], target: int) -> list[int]:
    numToIndex = {}

    for i, num in enumerate(nums):
      if target - num in numToIndex:
        return numToIndex[target - num], i
      numToIndex[num] = i

The algorithm leverages a hash map (unordered_map in C++, HashMap in Java, dictionary in Python, and Map in JavaScript). It iterates through the given 'nums' array and calculates the complementary value (target - current value). If the complementary value is already in the hash map, it means that we found a solution, and we return those indices. If the complement is not in the hash map, we store the current element in the hash map with its index. If the algorithm doesn't find the solution, it returns an empty array or throws an exception (in Java).

This approach has a time complexity of O(n) and a space complexity of O(n) as well.

JavaScript Solution

function twoSum(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
    return [];
}

The algorithm leverages a hash map (unordered_map in C++, HashMap in Java, dictionary in Python, and Map in JavaScript). It iterates through the given 'nums' array and calculates the complementary value (target - current value). If the complementary value is already in the hash map, it means that we found a solution, and we return those indices. If the complement is not in the hash map, we store the current element in the hash map with its index. If the algorithm doesn't find the solution, it returns an empty array or throws an exception (in Java).