Arrays - Two Sum

Question: Find a pair of index from given array where sum of numbers present at those indices is equal to given target number?

input [4,2,5,8,9,6]
target 7
output [1,2]  

Constraints need to ask because solution may change according to given constraints

Question: If the given array only contains positive numbers or negative can be present?
Answer: Only Positive numbers.

Question: What would be output, If target number is not sum of any pair present in array?
Answer: null

Question: What will be output if only one integer present in given array, because question asked for pair of numbers?
Answer: null

Question: What is the output when given array is empty?
Answer: null

Question: Is there any duplicate number present in array?
Answer: No

Question: If multiple pair can have target sum, what will be output?
Answer: First pair you get.

Solution using JAVA language.

Brute Force algorithm - In brute force solution, we try to check each and every possible combination through array. This is a approach in which 2 for loops are involved and polynomial time complexity.

import java.util.Arrays;

public class Solution {
    
    public static Integer[] findTwoNumSum(Integer[] arr, Integer target) {
        int length = arr.length;
        Integer[] result = new Integer[2];
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (target == arr[i] + arr[j]) {
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return null;
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{4, 2, 5, 8, 9, 6};
        int target = 7;
        Integer[] result = Solution.findTwoNumSum(arr, target);
        if (result != null) {
            System.out.println(Arrays.toString(result));
        } else {
            System.out.println("null");
        }
    }

}

Output: [1, 2]

Time Complexity: O(N²)

Space Complexity: O(1)

Optimal Solution - Above solution works well but that is not the efficient solution because it has polynomial time complexity. So, we will try to reduce the time complexity to linear. We need to think like if can use any data structure which can help us. Let's try to think about using Map and below we have a solution.

import java.util.Arrays;
import java.util.HashMap;

public class Solution {
    
    public static int[] findTwoSum(int[] arr, Integer target) {
        int length = arr.length;
        int[] result = new int[2];
        HashMap map = new HashMap<>(length);
        for (int i = 0; i < length; i++) {
            if (map.containsKey(arr[i])) {
                result[0] = map.get(arr[i]);
                result[1] = i;
                return result;
            } else {
                int numToFind = target - arr[i];
                map.put(numToFind, i);
            }
        }
        return null;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 2, 5, 8, 9, 6};
        int target = 7;
        int[] result = Solution.findTwoSum(arr, target);
        if (result != null) {
            System.out.println(Arrays.toString(result));
        } else {
            System.out.println("null");
        }
    }
}

Output: [1, 2]

Time Complexity: O(N)

Space Complexity: O(N)

Note: Find Question at Leetcode