Two Sum Problem Solution

Give me the solution for two sum problem on leetcode

The Two Sum problem on LeetCode can be approached in two different ways depending on whether the input array is sorted or not:

Pattern Recognized

1. Sorted Array: Use two pointers.
2. Unsorted Array: Use a hashmap.

Thinking Approach

1. Sorted Array:

   • Start with two pointers, one at the beginning and one at the end of the array.
   • Move the pointers based on the sum of elements at these pointers compared to the target sum.
   • If the sum is equal to the target, return the indices. If not, adjust the pointers accordingly.

2. Unsorted Array:

   • Iterate through the array, storing each element in a hashmap.
   • For each element, check if target - currentElement is present in the hashmap.
   • If it is found, return the current index and the index stored in the hashmap for the complement.

Code Snippet

For an unsorted array, the code in Java would look something like this:

java
DownloadCopy code
1boolean pairSum(int[] A, int N, int X) {
2    HashMap<Integer, Integer> map = new HashMap<>();
3    for (int i = 0; i < N; i++) {
4        if (map.containsKey(X - A[i])) {
5            return true; // Found the pair
6        }
7        map.put(A[i], i);
8    }
9    return false; // Pair not found
10}

Similar Questions

• 3Sum (LeetCode): Find three numbers in an array that add up to a given target sum.
• 4Sum (LeetCode): Find four numbers in an array that sum up to a given target.
• Two Sum II - Input Array Is Sorted (LeetCode): Variant of the Two Sum problem where the input array is sorted.

For further learning and practice, consider taking affordable courses at https://bit.ly/30dc-courses.