Leetcode 1. Two Sum

Problem

You are given an array of integers and a target integer value. Your task is to locate two different elements in the array that add up to exactly the target value, then return their positions in the array.

You may assume that every input will have exactly one valid answer, and you cannot use the same array element twice (the two indices must be different).

Requirements

1. Return an array containing exactly two indices
2. The two indices must point to different positions in the input array
3. The values at those two indices must sum to the target
4. The order of the returned indices does not matter
5. Exactly one solution is guaranteed to exist for each test case

Constraints

• 2 ≤ nums.length ≤ 10⁴
• -10⁹ ≤ nums[i] ≤ 10⁹
• -10⁹ ≤ target ≤ 10⁹
• Exactly one valid solution exists
• Aim for better than O(n²) time complexity

Examples

Example 1:

Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Explanation: The values at index 0 and index 1 are 2 and 7, which sum to 9.

Example 2:

Input: nums = [3, 2, 4], target = 6 Output: [1, 2] Explanation: The values at index 1 and index 2 are 2 and 4, which sum to 6.

Example 3:

Input: nums = [3, 3], target = 6 Output: [0, 1] Explanation: Both elements have the value 3, and they sum to 6. We return their different indices.

Hint 1: Brute Force Approach The most straightforward approach is to check every possible pair of elements. Use two nested loops: the outer loop picks the first element, and the inner loop checks if any subsequent element combines with it to reach the target. This works but has O(n²) time complexity.

Hint 2: Complement Strategy For each element you examine, think about what value would need to be paired with it to reach the target. If the current element is x and the target is t, then you need to find t - x somewhere in the array. Can you store information as you iterate to quickly check if you've seen the complement before?

Hint 3: Hash Table Use a hash table (dictionary/map) to remember values you've already seen along with their indices. As you iterate through the array, check if the complement of the current element exists in your hash table. If it does, you've found your pair. If not, store the current element and its index, then continue.

Full Solution ` def findPairIndices(nums, target): # Dictionary to store value -> index mapping seen = {}

# Iterate through the array with indices
for i, num in enumerate(nums):
    # Calculate what value we need to find
    complement = target - num
    
    # Check if we've seen the complement before
    if complement in seen:
        # Found the pair! Return both indices
        return [seen[complement], i]
    
    # Store current value and its index for future lookups
    seen[num] = i

# Should never reach here given problem constraints
return []

`

Explanation:

The optimal solution uses a hash table to achieve O(n) time complexity with O(n) space complexity.

Algorithm:

1. Create an empty dictionary to store values we've encountered mapped to their indices

2. Iterate through each element in the array with its index

3. For each element, calculate its complement (target - current value)

4. Check if the complement exists in our dictionary:

   • If yes: we've found our pair! Return the stored index and current index
   • If no: store the current value and index in the dictionary

5. Continue until we find the pair

Why This Works:

Instead of checking all possible pairs (which takes O(n²) time), we make a single pass through the array. For each element, we perform a constant-time lookup to see if its complement has already been seen. This reduces the time complexity to O(n).

Time Complexity: O(n) where n is the length of the array. We make at most one pass through the array, and dictionary operations (insert and lookup) are O(1) on average.

Space Complexity: O(n) in the worst case, where we might store almost all elements in the dictionary before finding the pair.