Skip to main content

Two Pointer Technique


The two-pointer technique is a simple and effective technique that is used in competitive programming. It helps programmer to efficiently solve array problem. In two-pointer we take two pointer at the start and the end. That pointers started to iterate the whole array and solve problem according to a programmer.

Suppose, we have an array n which consists m number of values. Now, if we want to sum all the element of the array then we have to iterate the whole array and sum all the element. Which will take O(n) time.

n = [4, 5, 2, 4, 9, 4]

But, in two-pointer technique we can solve this problem in O(n/2) time. Which is more efficient than traditional way.


In the code, we used two variable st which point at first element of the array and en which point at the last element of the array. After this, we take a while loop which condition is st should be less than en. If the condition does not meet the value, then loop will break. In the loop, we summed the first value and last value that are pointed. After that, we increases st variable value and decrease en values. By this technique, we can iterate the whole array in O(n) time.

Time Complexity: O(n)

Labels:

Comments

Post a Comment

Popular posts from this blog

Easiest way to find out which power of number is big?

If you are given two number with its power and told you which number is big. How do you calculate it. For, instance you would say binary exponentiation technique. But this is bit harder when the test case number is bigger. There is also an easy way to solve this problem. Suppose you are given 2^18 and 6^12. Then, you just take logarithm in both numbers. Then it will become 18*log2 and 12*log6. Logarithm function will break this number and make it a little number. which can be compare easily. But for this you have to Double number type, or you will get an error message. Problem:  Problem - 987B - Codeforces Code: void solve() {    ll a,b;    cin>>a>>b;    double num1 = b*log(a);    double num2 = a*log(b);    if(num1==num2) cout<<'='<<endl;    else if(num1>num2) cout<<'>'<<endl;    else cout<<'<'<<endl; }
Post a Comment
Read more

Upper bound and Lower bound!

Lower bound: In binary search, the lower bound is the lowest position where the value could be inserted without breaking the ordering. In the C++ standard library, this bound will be represented by an iterator referencing the element before which the value could be inserted.  STL: int lower = lower_bound(vec.begin(), vec.end(), target); That function will return a int value, where we can put the target value with the compromising the sorted system. Upper bound: In binary search, the upper bound is the highest position where the value could be inserted without breaking the ordering. In the C++ standard library, this bound will be represented by an iterator referencing the element after which the value could be inserted.  STL: int upper = upper_bound(vec.begin(), vec.end(), target); That function will return a int value, where we can put the target value with the compromising the sorted system.
Post a Comment
Read more

How Sliding window works?

Sliding window is a problem solving technique by which we can find the maximum sum of k consecutive values in an n size array or array type data structure. This method usually uses a one-way for loop. Suppose we are given an array of size n=9 and we need to extract Here is the maximum value of 4 consecutive numbers. n = [ 5, 7, 1, 4, 3, 6, 2, 9, 2] If we want to solve this problem by brute force method. In that case our time complexity can be O(n2) or O(n3). Which is very time consuming. In this case we can use sliding window technique. which can give us the expected answer in O(n) time. As you can see from the above code, we first extract the sum of the first 4 numbers of the array and put it in max_sum. In the next loop, we add the next numbers and subtract the last number from that sum. Through which we got the sum of every 4 consecutive numbers in the loop.   Suppose, the max_sum variable contains the sum of the first four numbers [5, 7, 1, 4]. Now if we add the 5th value of n...
Post a Comment
Read more