Two Sum

from typing import List

class Solution:
    # 1. Optimized Approach: Time O(n), Space O(n) - Dictionary/Hash Map
    def twoSum_optimized(self, nums: List[int], target: int) -> List[int]:
        num_map = {}
        
        for i, num in enumerate(nums):
            complement = target - num
            
            if complement in num_map:
                return [num_map[complement], i]
            
            num_map[num] = i
            
        return [] # Should not be reached

    # 2. Brute Force Approach: Time O(n^2), Space O(1)
    def twoSum_brute(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return [] # Should not be reached
    
    # Default entry point (use the optimized one for general use)
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        return self.twoSum_optimized(nums, target)

import java.util.HashMap;
import java.util.Map;

class Solution {

    // 1. Optimized Approach: Time O(n), Space O(n) - HashMap
    public int[] twoSum_optimized(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            
            if (numMap.containsKey(complement)) {
                return new int[] { numMap.get(complement), i };
            }
            
            numMap.put(nums[i], i);
        }
        
        return new int[0]; // Should not be reached
    }

    // 2. Brute Force Approach: Time O(n^2), Space O(1)
    public int[] twoSum_brute(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] { i, j };
                }
            }
        }
        return new int[0]; // Should not be reached
    }
    
    // Default entry point (use the optimized one for submissions)
    public int[] twoSum(int[] nums, int target) {
        return twoSum_optimized(nums, target);
    }
}

#include <vector>
#include <unordered_map>
#include <iostream>

class Solution {
public:
    // 1. Optimized Approach: Time O(n), Space O(n) - Hash Map
    std::vector<int> twoSum_optimized(std::vector<int>& nums, int target) {
        std::unordered_map<int, int> numMap;
        int n = nums.size();

        for (int i = 0; i < n; i++) {
            int complement = target - nums[i];
            
            if (numMap.count(complement)) {
                return {numMap.at(complement), i};
            }
            
            numMap[nums[i]] = i;
        }
        return {}; // Should not be reached
    }

    // 2. Brute Force Approach: Time O(n^2), Space O(1)
    std::vector<int> twoSum_brute(std::vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {}; // Should not be reached
    }
    
    // Default entry point (use the optimized one for submissions)
    std::vector<int> twoSum(std::vector<int>& nums, int target) {
        return twoSum_optimized(nums, target);
    }
};