// https://leetcode.com/problems/two-sum/description/?source=submission-ac

class Solution {

    // Time complexity: O(nlogn)
    // Dry runs
    // Example 1: [1, 2, 3, 4, 5], target = 7
    // Example 2: [5, 6, 3, 1] , target = 7

    // Below solution works for scenario where we are looking for two numbers that add upto target but not for indices
    // This is because we are sorting and that would change the indices
    // public int[] twoSum(int[] nums, int target) {
    //     Arrays.sort(nums);
    //     int i = 0, j = nums.length - 1;

    //     while(i < j) {
    //         if (nums[i] + nums[j] == target) {
    //             return new int[]{nums[i], nums[j]};
    //         }
    //         else if (nums[i] + nums[j] > target) {
    //             j--;
    //         }
    //         else {
    //             i++;
    //         }
    //     }

    //     return new int[]{};
        
    // }

    // Time complexity: O(n)
    // Space complexity: O(n)
    // I initially though below solution would not work for duplicates however that assumption was wrong
    // public int[] twoSum(int[] nums, int target) {
    //     HashMap map = new HashMap<>();

    //     for(int i = 0; i < nums.length; i++) {
    //         map.put(nums[i], i);
    //     }

    //     for(int i = 0; i < nums.length; i++) {
    //         if(map.get(target - nums[i]) != null) {
    //             int j = map.get(target - nums[i]);
    //             if (i == j) continue;
    //             return new int[]
    //                 {i, map.get(target - nums[i])};
    //         }
    //     }

    //     return new int[]{};
    // }

    // Brute force
    // Time Complexity: O(n^2)
    // Space Complexity: O(1)
    // public int[] twoSum(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[]{};
    // }

    // Time complexity: O(n)
    // Space complexity: O(n)
    // Two pass hash table
    // public int[] twoSum(int[] nums, int target) {
    //     Map map = new HashMap<>();
    //     for (int i = 0; i < nums.length; i++) {
    //         map.put(nums[i], i);
    //     }

    //     for (int i = 0; i < nums.length; i++) {
    //         int complement = target - nums[i];

    //         if(map.containsKey(complement) && map.get(complement) != i) {
    //             return new int[] {i, map.get(complement)};
    //         }
    //     }

    //     return new int[]{};
    // }

    // Time complexity: O(n)
    // Space complexity: O(n)
    // One pass hash table
    public int[] twoSum(int[] nums, int target) {
        Map map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if(map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }

            map.put(nums[i], i);
        }

        return new int[]{};
    }

}