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.");
}
}
}
