The two-pointer approach is a popular algorithmic technique used in programming to solve problems involving iterating over arrays, lists or linked lists. It uses two pointers (or indices) to traverse the data structure to achieve a specific goal.
In this approach, one pointer (or index) is used to track the current position in the array, while another pointer is conceptually used to track the required position based on the problem. This approach is useful for problems like finding pairs that sum to a target value, reversing a list, detecting cycles in linked lists, sliding window techniques related problems, merging two sorted lists, removing duplicates in-place, etc.
This approach helps in reducing time complexity, eg. from O(n²) to O(n *log n).
Variations of Two Pointers
Two pointer approach is a constructive algorithm, pointers can move any way based on the requirement. These pointers can be initialized in various ways. There are different variations of initializing and moving the pointers. Below are some of these variations:
- Starting from both ends of the array, a left pointer at the start (0) and a right pointer at the end of the array.
- Slow and fast pointer, one pointer moving slow (1 step for instance) and another moving fast (2 steps or variable number of steps).
- Starting from 2 different arrays, used for merging etc.
- Split array and then start a pointer from each.
- 2 slow pointers starting from the beginning of the array, variable / sliding window technique.
The solution to the above problem in Rust:
- There are two pointers ii and nzp. nzp is the position of the non-zero values. ii is the current variable to iterate through nums vector.
- In Rust, there is no concept of classes like in C++ or Java. Rust provides similar functionality using struct (structures) and impl (associated methods) blocks.
- “&mut Vec<i32>” is a mutable reference to the integer vector to modify in-place.
Vec type is used to create a vector, and elements are added using vec! macro.
eg. let mut nums: Vec<i32> = vec![1,2,3,4,5,0,6,0];
These vectors can be passed to functions by reference, by mutable reference, or by value.
- for loop iterates over indices of 0 to nums.len().
In Rust for loop can be used over a range of indices:
eg. for ii in 0..10
for loop can be used over arrays or vectors:
eg. for num in &nums
for loop can be used to iterate with indices and values:
eg. for (ii, num) in nums.iter().enumerate()
Here’s the solution in Rust:
In this solution, right pointer starts from the end of the array and left pointer starts from the beginning. Based on the sum value, left or right pointers are updated.
Note:
- In Rust, if we try to define two variables in the same line, it gives compilation errors.
- If we also define the result vector without data types as vec![(left+1), (right+1)], it results in compilation errors.
Below is the Go solution:
- There is while keyword in Go language.
Another 2-pointer technique related problem:
Here is the solution:
This solution has two pointers left and right. right pointer is for iterating over the elements. cur is incremented with each element value. If cur > total amount, it is decremented with books[left] and left pointer incremented. ans is updated with max value of right — left + 1.
Subarray related problem:
Below is the solution:
- left pointer is incremented once each sum is evaluated.
Introducing Jyo Services — Your Go-To Partner for Tech Solutions
Are you looking to boost your career or bring your tech ideas to life? Jyo Services offers a range of specialized solutions tailored just for you:
- One-on-One Interview Preparation: Tailored coaching for freshers and professionals with up to 7 years of software development experience.
- Custom Software Development: Expertise in embedded technologies, AI/ML, Gen AI, Cyber Security, Linux-based applications, and network protocol developments.
- Patent Assistance: Comprehensive support for drafting, filing and maintaining patents in India.
- College Projects: Professional guidance for Engineering students on academic projects.
Unlock your potential with Jyo Services! Contact us today to get started.
DM me at: www.linkedin.com/in/jyothivs or jyos.v.s@gmail.com
