package com.thealgorithms.misc;

import java.util.HashMap;
import java.util.Optional;
import org.apache.commons.lang3.tuple.Pair;

public final class TwoSumProblem {
    private TwoSumProblem() {
    }

    /**
     * The function "twoSum" takes an array of integers and a target integer as input, and returns an
     * array of two indices where the corresponding elements in the input array add up to the target.
     * @param values An array of integers.
     * @param target The target is the sum that we are trying to find using two numbers from the given array.
     * @return A pair or indexes such that sum of values at these indexes equals to the target
     * @author Bama Charan Chhandogi (https://github.com/BamaCharanChhandogi)
     */

    public static Optional<Pair<Integer, Integer>> twoSum(final int[] values, final int target) {
        HashMap<Integer, Integer> valueToIndex = new HashMap<>();
        for (int i = 0; i < values.length; i++) {
            final var rem = target - values[i];
            if (valueToIndex.containsKey(rem)) {
                return Optional.of(Pair.of(valueToIndex.get(rem), i));
            }
            if (!valueToIndex.containsKey(values[i])) {
                valueToIndex.put(values[i], i);
            }
        }
        return Optional.empty();
    }
}