<aside> 💡 Beware sometimes the test cases are so extreme even time taken for logging (for debugging purpose) might lead to TLE. Try doing Koko Eating Banana using binary search if you wanna try.

</aside>

Two Pointers

Introduction

There are majorly 4 big categories and many sub categories in it.

  1. Running from both ends of an array: The first type of problems are, having two pointers at left and right end of array, then moving them to the center while processing something with them.
  2. Slow & Fast Pointers: This type uses two pointers with different movement speed. Typically they starts from the left end, then the first pointer advances fast and give some feedback to the slow pointer and do some calculation.
  3. Running from beginning of 2 arrays / Merging 2 arrays: In this category, you will be given 2 arrays or lists, then have to process them with individual pointers.
  4. Split & Merge of an array / Divide & Conquer: The last one is similiar to previous category but there is one thing is added. First, you need to split the given list into 2 separate lists and then do two pointers approach to merge or unify them. There aren't many tasks here.

Summary

Description: This method uses two pointers to traverse an array or a list from different ends or directions.

Usage: It's particularly useful for ordered data structures, where we can make intelligent decisions based on the position of the pointers.

Problems: 'Pair with Target Sum', 'Remove Duplicates', 'Squaring a Sorted Array'.

Practice

Q No. Problem Difficulty Detailed Solution My Takeaway
1 https://leetcode.com/problems/two-sum/ ⭐ Brute Force Approach is For each element find the second pair with Sequential search and if the array is sorted we can use binary search.
In case of unsorted arrays we can use a HashMap.
Given a sorted array we can use 2 pointers.
2 https://leetcode.com/problems/remove-duplicates-from-sorted-array/ ⭐ We can use set/map as we only want the length of the array.
Using 2 Pointers we can do this one pointer to iterate and other that point at the position where next non dup can be placed.
3 https://leetcode.com/problems/remove-element/ ⭐
4 https://leetcode.com/problems/squares-of-a-sorted-array/
5 https://leetcode.com/problems/3sum/
6 https://leetcode.com/problems/3sum-closest/
7 https://leetcode.com/problems/3sum-smaller/
8 https://leetcode.com/problems/subarray-product-less-than-k/
9 https://leetcode.com/problems/sort-colors/
10 https://leetcode.com/problems/4sum/
11 https://leetcode.com/problems/backspace-string-compare/
12 https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/

Island (Matrix Traversal)

Introduction

Summary

Description: It involves traversing a matrix to find 'islands' or contiguous groups of elements.

Usage: It's generally used in grid-based problems, especially when we need to group connected elements together.