Two Sum (v2)

import java.util.Arrays;

import java.util.HashMap;

import java.util.Map;

class Main {

public static void main(String[] args) {

/**

* Problem 1: 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.

*

* Instructions:

* - Think out loud.

* - Write Java code.

* - Explain time/space complexity.

*/

int[] nums = {2, 7, 11, 15};

int target = 9;

int[] result = twoSum(nums, target);

printOutput(result, nums);

// For negative numbers it also works

nums = new int[]{-3, 4, 3, 90};

target = 0;

// Expected output: [0, 2] (-3 + 3 = 0)

result = twoSum(nums, target);

printOutput(result, nums);

// For duplicates, It also works

nums = new int[]{3, 3};

target = 6;

// Expected output: [0, 1]

result = twoSum(nums, target);

printOutput(result, nums);

// Here is the large input scenario

nums = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

target = 19;

// Expected output: [8, 9] (9 + 10 = 19)

result = twoSum(nums, target);

printOutput(result, nums);

// Zero and negative target

nums = new int[]{0, 4, 3, 0};

target = 0;

// Expected output: [0, 3] (0 + 0 = 0)

result = twoSum(nums, target);

printOutput(result, nums);

// For No value pair the current code is returning null which matches the

// expectation

nums = new int[]{1, 2, 3};

target = 7;

// Expected: No solution, handle gracefully (e.g., return null or empty array)

result = twoSum(nums, target);

printOutput(result, nums);

// for a single element array, it will be the same expecting null as result

nums = new int[]{5};

target = 10;

// Expected: No solution}

result = twoSum(nums, target);

printOutput(result, nums);

}

// Your twoSum method here

public static int[] twoSum(int[] nums, int target) {

// Implementation goes here

// This conditional handles the single element scenario to return inmediately

// the result as null

if (nums.length < 2) {

return null;

}

// We can use a loop to traverse the nums array and a HashMap to store the

// elements processed after the substraction of the current element in

// comparison and the target. complement = target - currentElement.

Map<Integer, Integer> elementsProcessed = new HashMap<>();

for (int i = 0; i < nums.length; i++) {

// We grab the current element

int currentElement = nums[i];

// We calculate the complement

int complement = target - currentElement;

// We check if the complement is present in the HashMap of elements processed

if (elementsProcessed.containsKey(complement)) {

// Then we return the result which is the value of the complement

// key found in the elements processed map and the index of the current

// element (i)

int[] result = {elementsProcessed.get(complement), i};

return result;

}

// We try to put the new key of the current elemeent if it is absent

elementsProcessed.putIfAbsent(currentElement, i);

}

// Now talking about code complexity, We have a single loop which has O(n)

// The HashMap used has O(1) so the higher complexity takes priority.

// So, the time complexity is O(n) for this function

// Now about space complexity, we have O(n) given the HashMap which is

// single "complex" data structure created in this function

// So, the space complexity is O(n)

return null; // placeholder

}

private static void printOutput(int[] result, int[] nums) {

if (result != null) {

System.out.println("Indices: " + Arrays.toString(result));

System.out.println("Values: " + nums[result[0]] + ", " + nums[result[1]]);

} else {

System.out.println("No solution found.");

}

}

}