The Two Sum problem is a classic algorithmic challenge that often appears in coding interviews and real-world applications. The task is to find two numbers in a given array that add up to a specific target. This problem tests your ability to efficiently search and manipulate arrays.
In this post, we’ll explore how to solve the Two Sum problem using Kotlin. We will cover multiple approaches, including a brute-force solution, a more optimized approach using a hash map, and edge cases to consider.
Problem Definition
Given an array of integers nums and an integer target, the goal is to find two numbers in the array that add up to the target. Return the indices of the two numbers. You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] // nums[0] + nums[1] = 2 + 7 = 9
Constraints:
- The array contains at least 2 elements.
- The array can have negative, positive, or zero values.
- There will always be exactly one solution.
Solution 1: Brute-Force Approach
Approach:
The brute-force approach involves checking all pairs of numbers to see if their sum equals the target. We use two nested loops: the outer loop picks an element, and the inner loop checks if any subsequent element forms the required sum.
Code Implementation:
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)
}
}
}
throw IllegalArgumentException("No solution found")
}
fun main() {
val nums = intArrayOf(2, 7, 11, 15)
val target = 9
val result = twoSum(nums, target)
println(result.joinToString()) // Output: 0, 1
}
Time and Space Complexity:
- Time Complexity: O(n²) due to the two nested loops.
- Space Complexity: O(1), as no additional data structures are used.
Explanation:
In this brute-force solution, we compare each element with every other element in the array. If their sum equals the target, we return their indices. If no such pair is found by the end of the loop, an exception is thrown.
Drawbacks:
This approach is inefficient for large arrays since the time complexity is O(n²). As the array size grows, the number of comparisons increases exponentially, making this method impractical for large datasets.
Solution 2: Optimized Approach Using a Hash Map
Approach:
A more efficient approach is to use a hash map (or dictionary). We can store each element in the hash map as we iterate through the array. For each element, we calculate the complement (i.e., target - current element) and check if the complement exists in the hash map. If it does, we return the indices of the current element and its complement.
Code Implementation:
fun twoSum(nums: IntArray, target: Int): IntArray {
val map = mutableMapOf<Int, Int>() // Hash map to store the indices of elements
for (i in nums.indices) {
val complement = target - nums[i]
if (map.containsKey(complement)) {
return intArrayOf(map[complement]!!, i)
}
map[nums[i]] = i
}
throw IllegalArgumentException("No solution found")
}
fun main() {
val nums = intArrayOf(2, 7, 11, 15)
val target = 9
val result = twoSum(nums, target)
println(result.joinToString()) // Output: 0, 1
}
Time and Space Complexity:
- Time Complexity: O(n) because we iterate through the array once, and hash map operations (insertion and lookup) take O(1) on average.
- Space Complexity: O(n) due to the extra space required to store the elements in the hash map.
Explanation:
In this optimized approach, we use a hash map to store the array elements and their indices as we iterate through the array. For each element, we calculate the complement (target - element) and check if it’s already in the hash map. If the complement exists, we return the indices of the complement and the current element.
Benefits:
- Efficiency: This solution has a linear time complexity, making it suitable for large datasets.
- No Need for Sorting: Unlike some other approaches, this method does not require the array to be sorted, making it more versatile.
Edge Cases
While the problem guarantees exactly one solution, you should still account for various edge cases during implementation:
-
Negative and Positive Numbers:
The array may contain both negative and positive numbers. Ensure that the solution works for both.val nums = intArrayOf(-3, 4, 3, 90) val target = 0 val result = twoSum(nums, target) println(result.joinToString()) // Output: 0, 2 -
Duplicate Values:
The array may contain duplicate values, and the solution should still return the correct indices.val nums = intArrayOf(3, 3) val target = 6 val result = twoSum(nums, target) println(result.joinToString()) // Output: 0, 1 -
Array with Only Two Elements:
Since the problem guarantees at least two elements, the array can have exactly two elements, and the solution should still work.val nums = intArrayOf(1, 4) val target = 5 val result = twoSum(nums, target) println(result.joinToString()) // Output: 0, 1 -
Zeros in the Array:
If the array contains zeros, the solution should correctly handle the target involving zero.val nums = intArrayOf(0, 4, 3, 0) val target = 0 val result = twoSum(nums, target) println(result.joinToString()) // Output: 0, 3 -
Large Inputs:
If the array contains a large number of elements, the hash map approach ensures efficiency even with significant data size.val nums = IntArray(100000) { it } val target = 199999 val result = twoSum(nums, target) println(result.joinToString()) // Output: 99998, 99999
Conclusion
In this post, we explored two different approaches to solving the Two Sum problem in Kotlin:
- Brute-force approach: Simple but inefficient with O(n²) time complexity.
- Hash map approach: The optimal solution with O(n) time complexity, making it the best choice for large datasets.
We also discussed several edge cases you should consider when solving this problem in a real-world scenario. The hash map approach is the most practical solution due to its linear time complexity and its ability to handle various edge cases efficiently.