Java Coding Test Course, Two Pointers

Today, we will learn about the “Two Pointers” technique, which is one of the important techniques in solving algorithm problems using Java.
This technique uses two pointers when traversing arrays or lists and is mainly used for finding specific conditions in sorted data.

What is Two Pointers?

The two pointers technique is a method of scanning an array with two pointers (or indices).
One pointer points to the start of the array, and the other pointer points to the end of the array.
This method can often solve problems with a time complexity of O(n), making it useful for writing efficient algorithms.

Problem Description

Now let’s solve the following problem.
Given an integer array nums and an integer target,
the problem is to find the indices of two numbers in the array that sum up to target.
There is always a solution for each input, and the same element is not used twice.

Problem Approach

To solve the problem, we follow these steps:

1. Sort the array.
2. Start the first pointer at the beginning of the array and the second pointer at the end of the array.
3. Calculate the sum of the two values pointed to by the two pointers.
4. If the sum equals target, return the respective indices.
5. If the sum is less than target, move the first pointer to the right (to find a larger number).
6. If the sum is greater than target, move the second pointer to the left (to find a smaller number).
7. Repeat this process.

Java Code Implementation

Now let’s implement the above algorithm in Java.
The code below is an example of solving the problem using the two pointers approach explained earlier.

import java.util.HashMap;

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        // Create a hash map to store results
        HashMap map = new HashMap<>();
        
        // Traverse the nums array and store each element's index in the hash map
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            // Check if the complement exists in the hash map
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i }; // Return the two indices
            }
            map.put(nums[i], i); // Store the current element's index in the hash map
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    public static void main(String[] args) {
        TwoSum ts = new TwoSum();
        int[] nums = { 2, 7, 11, 15 };
        int target = 9;
        int[] result = ts.twoSum(nums, target);
        System.out.println("Result: [" + result[0] + ", " + result[1] + "]");
    }
}

Code Explanation

The above code solves the problem using a hash map.
It checks for a complement that, when added to the current element, equals target while iterating through each element.
If the complement is found, the corresponding index is returned.
This approach is different from the two pointers technique, but using a hash map is also useful.

Complexity Analysis

The time complexity of this algorithm is O(n) because it traverses the array only once.
The space complexity is O(n) as it uses a hash map to store all the elements.
While the two pointers approach is not used here, the two pointers technique is also a useful method with low time complexity.

Conclusion

Today, we learned about the two pointers approach in solving algorithm problems using Java.
This technique helps efficiently solve problems that meet specific conditions in arrays or lists.
Practicing with various problems using this technique will greatly aid in preparing for job-related algorithm tests.

Next time, we will look at specific problems further and tackle application forms.
Furthermore, we will also consider other types of problems that utilize the two pointers technique.