Two Sum

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.

• Each input will have exactly one solution.
• You may not use the same element twice.
• The answer can be returned in any order.

Solve Here: Two Sum

Examples

Input	Output
nums = [2,7,11,15], target = 9	[0, 1]
nums = [3,2,4], target = 6	[1, 2]
nums = [3,3], target = 6	[0, 1]

Edge Cases

1. Multiple identical numbers: The array may have duplicate numbers, but only one solution exists.
2. Small arrays: For example, nums = [1, 2], target = 3, where only two elements exist.

Solution Approaches

1. Brute Force Approach

• Description: Iterate through each pair of numbers and check if they sum up to the target.
• Time Complexity: O(n²) – Nested loops checking every pair.
• Space Complexity: O(1) – No additional data structures used.

fun twoSum(nums: IntArray, target: Int): IntArray {
    for (i in nums.indices) {
        for (j in i + 1 until nums.size) {
            if (nums[i] + nums[j] == target) {
                return intArrayOf(i, j)
            }
        }
    }
    return intArrayOf()
}

2. Using HashMap

• Description: Use a HashMap to store the difference between the target and each number as you iterate through the array. If the difference is found in the map, you have your solution.
• Time Complexity: O(n) – Single pass through the array.
• Space Complexity: O(n) – Extra space for the HashMap.

fun twoSum(nums: IntArray, target: Int): IntArray {
    val prevMap = HashMap<Int, Int>()
    for (i in nums.indices) {
        val num = nums[i]
        val diff = target - num
        if (prevMap.containsKey(diff)) {
            return intArrayOf(prevMap[diff]!!, i)
        }
        prevMap[num] = i
    }
    return intArrayOf()
}

Complexity Comparison

Approach	Time Complexity	Space Complexity
Brute Force	O(n²)	O(1)
Using HashMap	O(n)	O(n)

Conclusion

While the brute force method is simple and easy to understand, it has poor performance for large arrays due to its O(n²) time complexity. The HashMap approach is much more efficient with O(n) time complexity, making it the preferred solution for most cases.