Two-Pointer Technique in Java

The two-pointer technique in Java involves using two indices (or pointers) to traverse an array or a list. This approach is particularly useful for solving problems related to searching for pairs, merging sorted arrays, and maintaining a sliding window of elements.

Key Concepts

1. Initialization: You set two pointers (usually integers) at the start, end, or specific positions in the data structure.
2. Traversal: Depending on the problem, you move the pointers toward each other or in a particular direction.
3. Condition Checking: At each step, check conditions based on the problem’s requirements.
4. Termination: The loop continues until the pointers meet or a specific condition is satisfied.

Common Use Cases with Java Examples

1. Finding Pairs with a Given Sum

This example finds two numbers in a sorted array that sum to a specific target.

import java.util.Arrays;

public class TwoSumSorted {
    public static int[] twoSum(int[] arr, int target) {
        int left = 0, right = arr.length - 1;

        while (left < right) {
            int currentSum = arr[left] + arr[right];

            if (currentSum == target) {
                return new int[] { arr[left], arr[right] };
            } else if (currentSum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[] {}; // Return empty array if no pair found
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 6};
        int target = 6;
        int[] result = twoSum(arr, target);
        System.out.println(Arrays.toString(result)); // Output: [2, 4]
    }
}

Get Yodgorbek Komilov’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

2. Reversing a String

You can reverse a string in place using two pointers.

public class ReverseString {
    public static String reverse(String s) {
        char[] chars = s.toCharArray();
        int left = 0, right = chars.length - 1;

        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
        return new String(chars);
    }

    public static void main(String[] args) {
        String s = "Hello, World!";
        String reversed = reverse(s);
        System.out.println(reversed); // Output: !dlroW ,olleH
    }
}

3. Merging Two Sorted Arrays

This example merges two sorted arrays into one sorted array.

import java.util.Arrays;

public class MergeSortedArrays {
    public static int[] merge(int[] arr1, int[] arr2) {
        int[] merged = new int[arr1.length + arr2.length];
        int i = 0, j = 0, k = 0;

        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] < arr2[j]) {
                merged[k++] = arr1[i++];
            } else {
                merged[k++] = arr2[j++];
            }
        }

        // Copy remaining elements
        while (i < arr1.length) {
            merged[k++] = arr1[i++];
        }
        while (j < arr2.length) {
            merged[k++] = arr2[j++];
        }

        return merged;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5};
        int[] arr2 = {2, 4, 6};
        int[] merged = merge(arr1, arr2);
        System.out.println(Arrays.toString(merged)); // Output: [1, 2, 3, 4, 5, 6]
    }
}

4. Finding the Longest Substring Without Repeating Characters

This example finds the length of the longest substring without repeating characters.

import java.util.HashSet;

public class LongestUniqueSubstring {
    public static int longestUniqueSubstring(String s) {
        HashSet<Character> charSet = new HashSet<>();
        int left = 0, maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            while (charSet.contains(s.charAt(right))) {
                charSet.remove(s.charAt(left));
                left++;
            }
            charSet.add(s.charAt(right));
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        int length = longestUniqueSubstring(s);
        System.out.println(length); // Output: 3 (the substring is "abc")
    }
}

Advantages of the Two-Pointer Technique

• Efficiency: Reduces time complexity from O(n2)O(n²)O(n2) to O(n)O(n)O(n) for many problems, as it avoids nested loops.
• Simplicity: Provides a clear and structured way to traverse arrays or lists.

Conclusion

The two-pointer technique is a powerful and efficient strategy for solving a variety of problems in Java. Understanding and implementing this approach can greatly enhance your algorithmic skills and problem-solving capabilities.