The brute force approach to solving the Two Sum problem is based on checking every possible pair of elements in the array to see if their sum equals the given target
.
We start from the first element and for each element, we check all other elements that come after it in the array. For each pair, we calculate their sum and compare it to the target.
If we find such a pair, we return the indices of those two numbers. Since we’re guaranteed to have exactly one solution in valid cases, we can return as soon as we find the first match.
Different Scenarios Explained:
- Normal Case: For an array like
[2, 7, 11, 15]
and target 9
, the pair 2 + 7
gives 9, so we return [0, 1]
.
- Duplicates Allowed: If an array has two identical numbers like
[3, 3]
and target is 6
, we can still use both numbers as long as they are at different indices. So, the result is [0, 1]
.
- No Valid Pair: If no two elements add up to the target, like in
[1, 2, 3, 4, 5]
with target 10
, we return an empty result []
.
- Edge Case - Empty Array: If the input array is empty
[]
, there are no elements to consider, so the result is []
.
- Edge Case - Single Element: With only one number in the array like
[5]
, we can’t form a pair, so we return []
.
Although this brute force method is simple and easy to understand, it is not the most efficient. It checks all possible combinations, resulting in a time complexity of O(n²). However, it's perfect for learning and understanding how the basic logic works.