Two Pointers Pattern: Efficiently Solving Array Problems

Let's continue with the Two Pointers pattern, which is widely used to solve problems involving arrays, especially for finding pairs that meet a specific condition.

Two Pointers Pattern

Concept:

The two pointers pattern involves having two pointers, usually starting at different positions (like the beginning and end of an array), and moving them toward each other to solve problems that require searching pairs or evaluating elements in relation to each other.

This pattern is widely used in problems that involve sorting, searching for pairs, or partitioning arrays, especially when working with arrays or lists.

Example Problem:

Given a sorted array of integers, find two numbers that add up to a specific target value.

Problem Statement:

You are given an array of integers arr[] sorted in non-decreasing order and an integer target. Find two numbers such that they add up to the target. Return the indices of the two numbers (1-based).

Brute Force Approach:

A simple brute force solution would involve checking each pair of elements to see if their sum equals the target. This would take O(n²) time, as it checks all pairs.

Optimized Two Pointers Approach:

We can use the two pointers approach, which will give us a time complexity of O(n).

Java Code Implementation:

public class TwoPointersExample {

    // Method to find two numbers that sum up to the target
    public static int[] findTwoSum(int[] arr, int target) {
        // Initialize two pointers
        int left = 0;
        int right = arr.length - 1;

        // Traverse the array with the two pointers
        while (left < right) {
            int sum = arr[left] + arr[right];

            // If we found the target sum, return the 1-based indices
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            } 
            // If sum is less than target, move left pointer to the right
            else if (sum < target) {
                left++;
            } 
            // If sum is greater than target, move right pointer to the left
            else {
                right--;
            }
        }
        // If no pair is found, return -1
        return new int[]{-1, -1};
    }

    // Main method to test the two pointers implementation
    public static void main(String[] args) {
        int[] arr = {2, 7, 11, 15};
        int target = 9;
        int[] result = findTwoSum(arr, target);
        if (result[0] != -1) {
            System.out.println("Indices of numbers that sum to " + target + ": " + result[0] + ", " + result[1]);
        } else {
            System.out.println("No pair found that sums to the target.");
        }
    }
}

Explanation:

1. We initialize two pointers, left starting at the beginning of the array and right starting at the end.
2. We calculate the sum of the values at these two pointers.
3. If the sum equals the target, we return the indices of the two elements.
4. If the sum is less than the target, we move the left pointer to the right to increase the sum.
5. If the sum is greater than the target, we move the right pointer to the left to decrease the sum.
6. This continues until we find the correct pair or exhaust the array.

Expected Output:

For the input array {2, 7, 11, 15} and target = 9, the output will be:

Indices of numbers that sum to 9: 1, 2

Time Complexity:

The time complexity is O(n), where n is the number of elements in the array. This is because the two pointers only traverse the array once.

Space Complexity:

The space complexity is O(1), since no extra space is used aside from a few variables.

Big O Notation Explanation:

• O(n) time complexity means that the algorithm makes at most n operations. In this case, we are traversing the array once from both ends, ensuring an efficient solution.
• O(1) space complexity indicates that the memory usage does not increase with the size of the input. We're only using constant space for a few variables like left and right.

The two pointers pattern is highly efficient for problems like this where the array is sorted, and it avoids the overhead of nested loops, offering an optimal solution.

View All Patterns Here