Day 8 of 30 days of Data Structures and Algorithms and System Design Simplified — Two Pointer Technique
Welcome back peeps. Hope all’s well. In this post we will cover Two pointer technique as follows —
What and Why Two pointer technique(in 2–3 sentences)?
How does Two pointer technique work?
Important Patterns and Techniques in Two pointer technique Questions
Most Important Questions with Solutions
Tips and Techniques to solve Two pointer technique Questions Fast.
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Two pointer Technique
Importance : Very High
Note : New Two pointer technique questions with solutions will be added everyday. So keep checking this post everyday.
Let’s dive in!
What is Two pointer technique?
Two pointer is a technique in which two pointers ( references) are used to keep a track of array/string indices. They are streamlined so that they can iterate the two parts of the array simultaneously.
It’s a useful technique to utilize when searching for pairs in sorted array.
Using two pointer technique you can save space and time and optimize your algorithm.
Within one loop two elements are accessed and processed simultaneously. There are two approaches in two pointer technique —
Start and End Two pointers — One pointer starts from the beginning while the other pointer starts from the end , until they meet.
Slow and fast pointers— One slow-runner ( moves at slower pace) and the other fast-runner ( moves twice the speed of the slow pointer).
Examples of Two pointer technique based problems —
Remove Duplicates from Sorted Array
Find “Nth” node in the linked list
Two Sum II — Input array is sorted
Two Sum III — Input array is sorted
Reverse Words in a String II
Rotate Array
Valid Palindrome
Container With Most Water
Product of Array Except Self
How does Two pointer technique work?
Two pointer technique is a method used to solve problems involving arrays and lists by moving two pointers through the data structure, one pointer moving forward and the other moving backward. It is used to find a pair of elements that meet a certain condition, or to find the smallest or largest sub-array.
The Two pointer technique works by having a “left” pointer and a “right” pointer. The left pointer starts at the beginning of the array, and the right pointer starts at the end. The pointers are then moved towards each other based on a certain condition. The condition can be the sum of the elements at the pointers is equal to a target value or the difference between the two pointers is equal to a target value.
Start and End pointers —> Left and Right Pointers:
One pointer starts from the beginning while the other pointer starts from the end, until they meet.
Slow and Fast Pointer :
One slow-runner ( moves at slower pace) and the other fast-runner ( moves twice the speed of the slow pointer).
Important Patterns and Techniques in Two pointer Programming Questions
Important patterns and techniques in Two pointer technique questions include understanding how to use two pointers to solve problems, analyzing the time and space complexity of the solution, identifying the correct condition for moving the pointers, and handling edge cases like empty input or input with negative values.
1.End pointers — Left and Right Pointers
In case of left and right pointers, start by iterating the left pointer one element at a time from the first element and right element from the end. Evaluate the condition and increment or decrement the pointers accordingly.
2. Left and Right Pointers — Sliding window
Left and Right pointers start from the first element and keep sliding as per the requirement ( i.e based on the target condition).
3. Slow and Fast Pointer
Slow pointer moves by one element and fast pointer moves twice the speed i.e by two elements starting from the first index of the array until they meet.
Patterns → Questions like below belong to Two pointer technique ( not limited to):
Delete N Nodes After M Nodes of a Linked List
Delete the Middle Node of a Linked List
Remove Duplicates from Sorted Array
Two Sum II — Input array is sorted
Reverse Words in a String II
Rotate Array
Valid Palindrome
Container With Most Water
Product of Array Except Self etc
Most Important Questions with Solutions
Note : New two pointer technique based questions with solutions are added every day. So keep checking this post day.
Golden rule is — Learn by doing/implementing
In this we will see most important Two pointer technique based questions.
Container With Most Water
Question —
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Example :
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49Solution :
Main Logic/Idea —
The main logic is to take two pointers left ( start of the array) and right ( end of the container heights and a maxarea variable to store the current area. Calculate the area and update the maxarea pointer.
Keep incrementing left pointer/decrementing right pointer if height pointed by left pointer is less than the height pointed by the right pointer. Keep updating the maxarea.
Implementation —
def maxArea(self, height: List[int]) -> int:
left,right,ans = 0,len(height)-1, 0
while left < right :
ar = (right- left) * min(height[left],height[right])
ans = max(ans,ar)
if height[left] < height[right]:
left +=1
else:
right -=1
return ansQuestion Link
Similar Pattern —
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Remove Nth Node From End of List
Question —
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example :
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]Solution :
Main Logic/Idea —
The main idea is — take two pointers and keep incrementing till you find the one node prior to the target node ( left pointer) while right pointer will pointer will go on till the end to store the address of next node pointed by the node to be removed. Once done, point left.next to left.next.next to remove the target node.
Implementation —
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
temp =ListNode(0,head)
left = temp
right = head
while n>0 and right:
right = right.next
n -=1
while right:
left =left.next
right = right.next
left.next = left.next.next
return temp.nextQuestion Link
Similar Pattern —
Delete N Nodes After M Nodes of a Linked List
Delete the Middle Node of a Linked List
Swapping Nodes in a Linked List
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Linked List Cycle
Question —
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: trueSolution :
Main Logic/Idea —
The main logic — Take two pointers, one slow at x speed and other fast at 2x speed. Start traversing from the first node and increment slow by one node and fast pointer by two nodes. If slow pointer meets fast pointer then return True (i.e cycle exists in the linked list) else False.
Implementation —
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow, fast = head, head
while fast and fast.next :
slow= slow.next
fast = fast.next.next
if slow == fast:
return True
return FalseQuestion Link
Similar Pattern —
Keep Multiplying Found Values by Two
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Tips and Techniques to solve Two pointer Questions Fast —
To solve the Two pointer technique based questions fast —
- Know how to iterate/move the indexes efficiently.
- Learn the patterns as covered in this post above.
- Refer to sliding window post to understand how to use two pointers to move along the slide.
Most important two pointer technique based questions —
That’s it for now. Day 9: Recursion coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time and Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
