Master the Basics of Two Pointers : A Comprehensive Guide for Beginners.
From Introduction to Advanced Techniques: Unlock the Power of Two Pointers in Programming.
What is a pointers ?
In this technique, the pointer represents either the index or iteration attribute in an array.
Form above picture we have an array array it contains five elements i.e.., 1,2,3,4,5 and these values are accessing by using their index’s i.e.., 0,1,2,3,4.
A pointer helps us to keep track of the current position.
What is a Single pointer ?
Single pointer is not a useful and effective technique typically to solve problems involving collections such as arrays, Strings and Lists. Why because means we are keep tracking in one direction only i.e.., start to end or end to start.
Example :-
question :- Write a program to reverse an array ?
example : [ 1,2,3,4,5 ]
output : [ 5,4,3,2,1 ]Basic approach with a single-pointer :-
First of all we need to create an new array to store the values. Later, we are starting at arr.length-1 means last element in an array later we are are accessing arr elements and assigning that value to new array starting form index “0“. then later we are returning the new array.
Program or code :-
What is mean by two pointers ?
Two-pointer’s is a useful and effective technique typically to solve problems involving collections such as arrays, Strings and Lists. The main idea is to iterate two different parts of the array simultaneously to solve the problem efficiently.
Why and How Two-pointers technique is efficient ?
Two-pointer is just a tool or strategy to solve problems. The main idea is to iterate two different parts of the array simultaneously to solve the problem efficiently.
While we are manipulating the array in place, this approach works in constant space. Like most algorithm problems, there are usually multiple ways to solve them. The two-pointer technique appears to be a good starting point for optimization when dealing with an array or list problems.
Here are some thoughts to follow when you are implementing the two-pointer approach, depends on what you are trying to achieve:
Pointers Initializing — Your starting points. The indexes that you want to compare with.
Movement Judging — The movement affects the coverage of comparison. There should be a solid condition to judge the pointer’s movement whether to move forward or pause.
Stop condition — condition to stop the pointer movement. Usually stops at the end of array iteration or when two-pointer meet intersection.
Example :-
question :- Write a program to reverse an array ?
example : [ 1,2,3,4,5 ]
output : [ 5,4,3,2,1 ]Basic approach with a Two-pointer’s :-
First of we need to create two pointers like start, end assigning two pointers with 0 and Array.length - 1. we need check weather start is less than are equal to end in looping condition or statement when ever it fail’s then we will stop that loop.
otherwise condition is true then it will execute our code . basic idea in reversing of an array problem is we need to swap the two variable start and end by using temporary variable.
Program or code :-
Comparison between single-pointer and Two-pointer’s :-
By using single pointer we can solve problems in brute approach’s only (Means step by step) but it will take so much time and also space.
In every program to reduce time and space is very most important that’s why only we are moving towards optimize our solution.
Two-pointer’s technique is useful and important technique to solve problems in more efficient way.
In above problems we are using constant space means Big-O(1)
where as in single pointer we are taking Big-O(n).
Time complexity also reduces in Two-pointer’s when compared to single pointer.
please make a comment what is the time taken to run an single-pointer and also Two-pointer’s for above problem ?
In next article we are using some more examples to understand more about two pointer’s technique ?