Problem Overview

The task requires identifying the indices of two specific numbers within an integer array that sum up to a defined target value. It is guaranteed that each input set contains exactly one valid solution, and the same element cannot be used twice to form the sum.

Brute Force Implementation

The most straightforward method involves iterating through the collection with nested loops. The outer loop selects a reference number, while the inner loop compares it against every subsequent number to check if they satisfy the target sum.

public int[] FindIndicesBruteForce(int[] numbers, int goal)
{
    if (numbers == null || numbers.Length < 2) return Array.Empty<int>();

    for (int i = 0; i < numbers.Length; i++)
    {
        for (int j = i + 1; j < numbers.Length; j++)
        {
            if (numbers[i] + numbers[j] == goal)
            {
                return new int[] { i, j };
            }
        }
    }
    return Array.Empty<int>();
}

This approach ensures correctness with a space complexity of O(1), as no additional data structures are allocated. However, the nested iteration results in a time complexity of O(n²), which is inefficient for large datasets.

Hash Map Optimization

To achieve linear time complexity, we can utilize a dictionary (hash map) to store numbers and their indices as we traverse the array. This allows us to check if the complementary value (target minus current number) exists in constant time.

public int[] FindIndicesOptimized(int[] numbers, int goal)
{
    if (numbers == null || numbers.Length < 2) return Array.Empty<int>();

    var valueToIndexMap = new Dictionary<int, int>();

    for (int i = 0; i < numbers.Length; i++)
    {
        int current = numbers[i];
        int complement = goal - current;

        // Check if the required partner exists in the map
        if (valueToIndexMap.TryGetValue(complement, out int foundIndex))
        {
            return new int[] { foundIndex, i };
        }

        // Store the current number and index if not already present
        if (!valueToIndexMap.ContainsKey(current))
        {
            valueToIndexMap[current] = i;
        }
    }
    return Array.Empty<int>();
}

By trading space for time, this algorithm reduces the time complexity to O(n). The space complexity increases to O(n) to accommodate the storage requirements of the dictionary.