Author: Sakthi

1. Leetcode: Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example 1:
Input: nums = [3,2,4], target = 6
Output: [1,2]

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

public class TwoSum {
    // O(n^2) time complexity, O(1) space
    public static int[] twoSum1(int[] nums, int target) {
        for(int i = 0; i < nums.length; i++) {
            for(int j = i+1; j < nums.length; j++) {

                if(nums[i] + nums[j] == target) {
                    return new int[]{i,j};
                }
            }
        }
        return new int[]{};
    }
                 
    // O(n) time complexity, O(n) space
    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if(map.containsKey(complement)) {
                int a = i;
                int b = map.get(complement);
                return new int[]{a, b};
            }
            map.put(nums[i], i);    // takes care of duplicates since we make use of the first duplicate even before we replace it
        }
        return new int[]{};
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 4};
        int target = 6;
        int[] resultIndexes = twoSum(nums, target);

        System.out.println("Indexes: " + Arrays.toString(resultIndexes));
    }

}

Complexity Analysis:

For the method twoSum():

• 1. Time Complexity: O(n), where is the length of nums[]. We loop through the input once
  2. Space Complexity: O(n). Map would contain up to n entries, where n is the length of nums[]

Leetcode Problem Link:

https://leetcode.com/problems/two-sum/