TWO SUM JAVA PROGRAM

If we given an array , one target value, we should return the indices of 2 no.s , whatever they match up with target.

For Ex: 1. arr={1,3,5,7}, target =8
We supposed to return [1,2] indices
Because : arr[1]+arr[2]= 3+5= 8, so the target is matched

Remember: We should not use same element twice, and should exactly only one solution should be there.


class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int val = target - nums[i];
            if (map.containsKey(val)) {
                return new int[] { map.get(val), i };
            }
            map.put(nums[i], i);
        }
        return new int[] {};
    }
}

We iterate through the array and for each number, we calculate how much more is needed to reach the target.
We check if that “needed number” is already in the map:

If yes, we return the current index and the index of that number from the map.
If not, we store the current number and its index in the map for future use.

Space Complexity: O(n)
Time Complexity: O(n)

Frequency: APPEARED IN LAST 3 Months (HIGH)

TOPICS: ARRAY LIST
LP Num: 01
Type: Easy

Without DataStructure


class Solution {
    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[] {}; // No solution found
    }
}

Sometimes, few of the interviewer may ask solve this problem without using data structure. At that time, it’s just to know purpose we are updating here. It’s a brute-force method.