ugur elveren's blog

What Is The Two Pointer Technique?

The two-pointer is an easy technique used to solve some array-related problems. It involves using two pointers, one starting from the beginning of the array and the other starting from the end of the array, to traverse the array and find a solution. This technique is helpful because it reduces the time complexity of the algorithm and increases its efficiency.

The two-pointer technique is used in various solutions such as finding the sum of two numbers in an array that equals a given target, finding the length of the longest subarray with a given sum, and finding the shortest subarray with a given sum. The basic idea behind this technique is to start from the two ends of the array and move the pointers towards each other until a solution is found or it becomes clear that a solution does not exist.

Two Sum Problem

Two Sum, one of the famous interview questions can be solved with two pointers technique.

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

The Solution of Two Sum Problem with Two Pointers Technique

We initialize two pointers left and right to the start and end of the array, respectively. We calculate the sum of the numbers at left and right and compare it with the target. If the sum is equal to the target, we have found two numbers that add up to the target, so we return their indices. If the sum is less than the target, we increment the left pointer. If the sum is greater than the target, we decrement the right pointer. If the loop ends without finding a solution, we throw an exception.

public int[] TwoSum(int[] nums, int target) 
{
    int left = 0, right = nums.Length - 1;
    while (left < right) 
    {
        int sum = nums[left] + nums[right];
        if (sum == target) 
        {
            return new int[] { left, right };
        } 
        else if (sum < target) 
        {
            left++;
        } 
        else 
        {
            right--;
        }
    }
    throw new ArgumentException("No two sum solution");
}

“Two-pointer technique” and its application to problems involving two arrays

The two-pointer technique can also be applied to problems involving two arrays. In this scenario, the two pointers are used to traverse the two arrays simultaneously, with one pointer moving through each array. The goal is to find a solution that satisfies a given condition, such as finding a pair of elements with a given sum or finding the common elements between two arrays.

The Intersection Question

Let's consider an example of finding the common elements between two sorted arrays. In this problem, we are given two sorted arrays, and our goal is to find the elements that are common to both arrays. To solve this problem using the two-pointer technique, we start with two pointers, one at the beginning of each array, and compare the elements pointed to by the two pointers. If the elements are equal, we have found a common element, and both pointers are advanced one step. If the element in one array is greater than the element in the other array, the pointer pointing to the greater element is advanced one step. The process continues until one of the pointers reaches the end of its array.

The Solution of Intersection Problem with Two Pointers Technique

public List<int> Intersection(int[] nums1, int[] nums2)
{
    int i = 0, j = 0;
    List<int> result = new List<int>();
    while (i < nums1.Length && j < nums2.Length)
    {
        if (nums1[i] == nums2[j])
        {
            result.Add(nums1[i]);
            i++;
            j++;
        }
        else if (nums1[i] < nums2[j])
        {
            i++;
        }
        else
        {
            j++;
        }
    }
    return result;
}

Note: Assumes that the input arrays are already sorted.

Initialize two-pointers i and j: The two-pointers, i and j, are initialized to zero. They will be used to traverse the arrays nums1 and nums2, respectively. Create a result list result: A list result is created to store the elements that belong to both arrays. Start a while loop: The loop starts with the condition that both i and j are less than the length of their respective arrays. Compare the elements: Inside the loop, the elements pointed by i and j are compared. If they are equal, the element is added to the result list and both pointers are incremented. If the element pointed by i is less than the element pointed by j, only i is incremented. If the element pointed by j is less, only j is incremented. Repeat the loop: The loop continues until either i or j reaches the end of the array. Return the result: Finally, the result list is returned as the result.

Conclusion

In conclusion, the two-pointer technique is a highly effective algorithm for solving a variety of problems in computer science. It involves using two pointers that traverse a data structure, such as an array or list, in opposite directions to search for a solution. By utilizing this technique, developers can efficiently find solutions to problems with linear time complexity, making it an ideal method for optimizing performance and streamlining problem-solving. With its versatility and ease of use, the two-pointer technique is an indispensable tool for any C# developer, allowing them to quickly and effectively tackle complex challenges with confidence.

#Tech