📚 Problem Solving: Understanding the Two-Pointer Technique

Introduction

The two-pointer technique is a search algorithm that uses two pointers to solve various problems in computer programming. It works by maintaining two pointers that move through the data structure. The pointers can move in the same direction or opposite directions, and they can move at different speeds.

The two-pointer technique is used for pattern identification and traversal problems. In this type of problem, the goal is to find a specific pattern or sequence of elements in the data structure.

The two pointers can scan the data structure, comparing the elements at each step.

The two-pointer technique can tackle problems like:

• The 2-Sum problem.
• Determining Valid Palindromes.
• Determining cycles in a linked list.
• The Best Time to Buy and Sell Stock problem.
• 3Sum problem.
• Max Number of K-Sum Pairs problem.

among many others.

This versatile and efficient technique makes it a valuable addition to a software engineer's toolkit.

Understanding Time and Space Complexity

Before diving into the two-pointer technique, let's review time and space complexity in algorithm analysis.

Time complexity measures how an algorithm's execution time scales with increasing input data size. It helps in evaluating how efficient an algorithm is in handling larger datasets. Algorithms with high time complexity may lead to slow response times in applications. For example, an algorithm with O(n^2) time complexity implies that the execution time of the algorithm grows quadratically as the input data size increases.

Space complexity measures the memory an algorithm uses as the input data grows. For example, an algorithm with O(n) space complexity uses an amount of memory linearly proportional to the input data size, denoted as n.

For example, consider developing a mobile app that needs to run on devices with limited memory. If the algorithms that power the app have a high space complexity, they may not be able to run on some devices, resulting in a poor user experience. By understanding space complexity, you can choose algorithms that are optimized for memory usage and ensure that your applications run smoothly on a wide range of devices.

For in-depth guidance on understanding time and space complexity and to explore various algorithms and their complexities, please refer to resources such as Big-O Cheat Sheet and the references at the end of this article.

In summary, time and space complexity are not abstract concepts but practical considerations for software engineers. By evaluating time and space complexity, you can make informed choices about which algorithms to implement in your applications and how to traverse data structures when applying business rules or solving specific use cases.

The two-pointer technique in action

The two-pointer technique is a powerful tool for optimizing algorithm performance, especially when handling large datasets. It replaces nested loops with a single loop, maintaining two pointers that traverse the data structure. This method allows for linear time complexity, represented as O(n), significantly faster than the quadratic time complexity O(n^2) of nested loops.

The 2-Sum Problem

To illustrate the two-pointer technique, let's consider the two-sum problem and compare two code snippets that traverse an array using the nested loops and two-pointer technique.

Problem Statement: Given a sorted array of integers, find the two numbers in the array that add up to a specific target number. There is exactly one solution.

For example, given the array [1, 2, 4, 7, 11] and the target number 6, the two numbers that add up to 6 are 2 and 4.

Output, indices are 1 and 2.

The two-pointer technique works by maintaining two pointers, one at the beginning of the array and one at the end of the array.

The nested loops technique works by iterating over the array twice, comparing each element to every other element. If the sum of two elements is equal to the target value, the algorithm returns the indices of the two elements.

The two-pointer code snippet has a lower time complexity, O(n), than the quadratic time complexity, O(n^2) of the nested loops code snippet. The two-pointer and nested loops techniques use constant space complexity, O(1). They only use a few variables to store the current positions of the elements in the array.

 1func twoSum(nums []int, target int) []int {
 2 left, right := 0, len(nums)-1
 3 results := []int{}
 4
 5 for left < right {
 6  sum := nums[left] + nums[right]
 7
 8  // Found?
 9  if sum == target {
10   results = append(results, left, right)
11   break
12  }
13
14  // Move left pointer
15  if sum < target {
16   left++
17  } else { // Move right pointer
18   right--
19  }
20 }
21
22 return results
23}

 1func twoSum(nums []int, target int) []int {
 2 for i := 0; i < len(nums); i++ {
 3  for j := i + 1; j < len(nums); j++ {
 4   if nums[i]+nums[j] == target {
 5    return []int{i, j}
 6   }
 7  }
 8 }
 9 // If no pair is found
10 return nil
11}

Determining Valid Palindromes

The technique can also determine if a string is a valid palindrome. The two-pointer technique for palindrome problems involves using a left and right pointer to scan a string from both ends. The left pointer starts at the beginning of the string, and the right pointer starts at the end of the string. The pointers move inwards, comparing the characters at each step. The string is a palindrome if the characters at each step are the same. If the characters at any step are different, then the string is not a palindrome.

Problem Statement: Given a string s, determine if it is a palindrome. A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward.

For example: for the input string radar, the function should return true as radar is a palindrome. However, for the input string hello, the function should return false as hello is not a palindrome.

Output: Return true if the input string is a palindrome, and false otherwise.

Determining Valid Palindromes	Visualization
1func isPalindrome(s string) bool { 2 i, j := 0, len(s)-1 3 for i < j { 4 if s[i] != s[j] { 5 return false 6 } 7 i++ 8 j-- 9 } 10 return true 11}
Time Complexity: O(n), where n is the length of the input array.	Space Complexity: O(1), as it uses constant additional memory.

Detecting Cycles in Linked Lists

The two-pointer technique can also be used to detect a cycle in a linked list. In a linked list, each node points to the next node.

Problem Statement: Given a linked list, determine if it has a cycle. A linked list has a cycle if there is some node in the list that can be reached again by continuously following the next pointer.

For example, the following input linked list [3,2,1,0] has a cycle where the tail node is connected to the second node.

Output, true if the linked list has a cycle, false otherwise

source: LeetCode, Linked List Cycle

A cycle occurs when, during traversal, the two pointers (p1 slow and p2 fast) converge, indicating that the linked list has a cycle.

The two-pointer technique can be used to detect a cycle in the linked list [3,2,1,0] by moving two pointers p1 and p1, called the slow pointer p1 and the fast pointer p2, through the linked list. The slow pointer moves one node p1.Next at a time, while the fast pointer moves two nodes p2.Next.Next at a time.

The pointers detect a cycle when p1 and p2 point to the same node in the linked list. In this specific example, that condition occurs during the third iteration. During the third iteration, both p1 and p2 point to the node with a value of 1, indicating the presence of a cycle in the linked list.

Detecting Cycles in Linked Lists	Visualization
1func hasCycle(head *ListNode) bool { 2 if head == nil || head.Next == nil { 3 return false 4 } 5 6 p1, p2 := head, head.Next 7 8 for p2 != nil && p2.Next != nil { 9 if p1 == p2 { 10 return true 11 } 12 13 p1 = p1.Next 14 p2 = p2.Next.Next 15 } 16 17 return false 18}
Time Complexity: O(n), where n is the length of the input array.	Space Complexity: O(1), as it uses constant additional memory.

LeetCode: The Best Time to Buy and Sell Stock Problem

The two-pointer technique can also be used to find the entry and exit point indexes for the largest difference between any two elements in an array. In the prices array [7,1,5,3,6,4], the largest difference is 6 - 1 = 5, which occurs between the array's first and fourth elements. The entry point index is 1, and the exit point index is 4. Note that buying on day 2 and selling on day 1 is prohibited because you must buy (enter) before selling (exit).

Problem Statement: Given an array of stock prices, where each price represents the price of the stock on a given day. The goal is to maximize your profit by >buying one share of the stock on one day and selling it on a different day in the future. If you cannot make any profit, return 0.

For example, given the array [7, 1, 5, 3, 6, 4], the maximum profit you can make is 5. You can buy on day 2 (price = 1) and sell on day 5 (price = 6), for a profit of 6 - 1 = 5.

Note that you cannot buy on day 2 and sell on day 1, because you must buy before you sell.

Output:, 5 The maximum profit that can be achieved from this transaction.

source: LeetCode, Best Time to Buy and Sell Stock

The Best Time to Buy and Sell Stock problem seeks to maximize profit by identifying optimal moments to buy and sell stocks. This is accomplished using a two-pointer technique with left and right pointers:

The Best Time to Buy and Sell Stock Problem	Visualization
1func maxProfit(prices []int) int { 2 l, r, profit := 0, 1, 0 3 4 for r < len(prices) { 5 if prices[l] < prices[r] { 6 potentialProfit := prices[r] - prices[l] 7 8 profit = max(profit, potentialProfit) 9 10 r++ 11 } else { 12 l = r 13 r++ 14 } 15 } 16 17 return profit 18} 19 20// max returns the maximum of two integers, a and b. 21func max(a, b int) int { 22 if a > b { 23 return a 24 } 25 return b 26}
Time Complexity: O(n), where n is the length of the input array.	Space Complexity: O(1), as it uses constant additional memory.

Use two pointers, left l and right r, which move in the same direction through the prices array [7,1,5,3,6,4]. The l pointer tracks the potential buying point, and the r pointer explores the possible selling point. They start at positions 0 and 1, respectively, and move towards the end of the array.

As the algorithm traverses the array, it calculates potential profits when the price at the right pointer r is greater than the price at the left pointer l. It updates the profit variable with the maximum profit found in this process. If the condition is not met, meaning the price at the left pointer l is not less than the price at the right pointer r, the algorithm updates the left pointer l to the current position of the right pointer r and moves the right pointer r up by one position. This ensures that the left pointer l represents a potential buying point. The loop continues until the entire array is traversed, allowing the algorithm to find the maximum profit.

Conclusion

The two-pointer technique is a versatile tool for efficiently solving a wide range of problems. In this article, we have explored the fundamental concepts behind the two-pointer technique and its application. We have seen how it can be used to:

• The 2-Sum problem.
• Determining Valid Palindromes.
• Determining cycles in a linked list.
• The Best Time to Buy and Sell Stock problem.

Remember that the two-pointer technique is just one of many valuable tools in your toolkit. Its simplicity and efficiency make it an excellent choice for various challenges, but it's important to recognize when it's the right tool for the job.

By making informed decisions about which techniques to employ, you can create a more responsive and efficient software solution that meets the needs of your users.

References

• Sedgewick, Robert (Author), Wayne, Kevin (Author). (Year). Algorithms (4th Edition) 4th Edition.
• Kubica, Jeremy. (2022). Data Structures the Fun Way: An Amusing Adventure with Coffee-Filled Examples. Nov 8, 2022.
• Cormen, Thomas H. (Author), Leiserson, Charles E. (Author), Rivest, Ronald L. (Author), Stein, Clifford (Author). (Year). Introduction to Algorithms, fourth edition 4th Edition.
• Bakariya, Dr. Brijesh. Data Structures and Algorithms Implementation Through C: Let's Learn and Apply.
• Big-O Cheat Sheet
• LeetCode Problems