What is 2 Ptr ALgo
Whenever there’s a requirement to find two data elements in an array that satisfy a certain condition, the two pointers pattern should be the first strategy to come to mind.
The pointers can be used to iterate through the data structure in one or both directions, depending on the problem statement
Problem Pattern for 2 Ptr ?
Linear data structure: The input data can be traversed in a linear fashion, such as an array, linked list, or string.
Process pairs: Process data elements at two different positions simultaneously. Dynamic pointer movement: Both pointers move independently of each other according to certain conditions or criteria. In addition, both pointers might move along the same or two different data structures.
Valid Palindrome
Hint : Alpha numeric , With Spaces
Time O(N).
Space O(1)
public class Solution {
public static boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
left++;
}
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
right--;
}
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}3 Sum
Hint: Array can hold duplicates
Statement
Given an integer array, nums, find and return all unique triplets [nums[i], nums[j], nums[k]], such that i ≠= j, i ≠= k, and j ≠= k and nums[i] + nums[j] + nums[k] ==0==0.
ON2 / O1
public class Solution {
public static List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n - 2; ++i) {
if (nums[i] > 0)
break;
if (i == 0 || nums[i] != nums[i - 1]) {
int low = i + 1, high = n - 1;
while (low < high) {
int sum = nums[i] + nums[low] + nums[high];
if (sum < 0)
\++low;
else if (sum > 0)
--high;
else {
result.add(Arrays.asList(nums[i], nums[low], nums[high]));
\++low;
--high;
while (low < high && nums[low] == nums[low - 1])
\++low;
while (low < high && nums[high] == nums[high + 1])
--high;
}
}
}
}
return result;
}Remove Nth Node from End of List
Hint: Move right Pointer to Nth place.
public static ListNode removeNthLastNode(ListNode head, int n) {
ListNode right = head;
ListNode left = head;
for (int i = 0; i < n; i++) {
right = right.next;
}
if (right == null) {
return head.next;
}
while (right.next != null) {
right = right.next;
left = left.next;
}
left.next = left.next.next;
return head; }Given an array, colors, which contains a combination of the following three elements:
0 (Representing red) 1 (Representing white) 2 (Representing blue)
Sort the array in place so that the elements of the same color are adjacent, and the final order is: red (0), then white (1), and then blue (2).
Start - Tracks Red, Current Moves on From Start to End keeping white together, End tracks blue and decrements
public static int[] sortColors(int[] colors) {
int start = 0;
int current = 0;
int end = colors.length - 1;
while (current <= end) {
if (colors[current] == 0) {
int temp = colors[start];
colors[start] = colors[current];
colors[current] = temp;
current++;
start++;
}
else if (colors[current] == 1) {
current++;
}
else {
int temp = colors[current];
colors[current] = colors[end];
colors[end] = temp;
end--;
}
}
return colors;
}Reverse Words in a String
You are given a string sentence that may contain leading or trailing spaces, as well as multiple spaces between words. Your task is to reverse the order of the words in the sentence without changing the order of characters within each word. Return the resulting modified sentence as a single string with words separated by a single space, and no leading or trailing spaces.
public static String reverseWords(String sentence) {
sentence = sentence.trim();
String[] words = sentence.split(“\s+”);
int left = 0, right = words.length - 1;
while (left < right) {
String temp = words[left];
words[left] = words[right];
words[right] = temp;
left++;
right--;
}
return String.join(" ", words);
}Valid Word Abbreviation
The word “internationalization” can also be abbreviated as “i18n”
Keep in mind, number can be more than single digit number
public static boolean validWordAbbreviation(String word, String abbr) {
int wordIndex = 0, abbrIndex = 0;
while (abbrIndex < abbr.length()) {
if (Character.isDigit(abbr.charAt(abbrIndex))) {
if (abbr.charAt(abbrIndex) == '0') {
return false;
}
int num = 0;
while (abbrIndex < abbr.length() && Character.isDigit(abbr.charAt(abbrIndex))) {
num = num * 10 + (abbr.charAt(abbrIndex) - '0');
abbrIndex++;
}
wordIndex += num;
} else {
if (wordIndex >= word.length() || word.charAt(wordIndex)!= abbr.charAt(abbrIndex)) {
return false;
}
wordIndex++;
abbrIndex++;
}
}
return wordIndex == word.length() && abbrIndex == abbr.length();
}Strobogrammatic Number
Try to solve the Strobogrammatic Number problem.
Statement
Given a string num representing an integer, determine whether it is a strobogrammatic number. Return TRUE if the number is strobogrammatic or FALSE if it is not.
- Keep a map of numbers which match when turned around 180
- check with 2 ptr
// Function to check if a number is strobogrammatic
public static boolean isStrobogrammatic(String num) {
Map<Character, Character> dict = new HashMap<>();
dict.put(‘0’, ‘0’);
dict.put(‘1’, ‘1’);
dict.put(‘8’, ‘8’);
dict.put(‘6’, ‘9’);
dict.put(‘9’, ‘6’);
int left = 0;
int right = num.length() - 1;
while (left <= right) {
if (!dict.containsKey(num.charAt(left)) || dict.get(num.charAt(left)) != num.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}Minimum Number of Moves to Make Palindrome
Given a string s, return the minimum number of moves required to transform s into a palindrome. In each move, you can swap any two adjacent characters in s.
Note: The input string is guaranteed to be convertible into a palindrome.
The main strategy for solving this problem is to use a two-pointer approach to progressively match characters from the outer ends of the string toward the center, while minimizing adjacent swaps to transform the string into a palindrome. For each character on the left side, the algorithm searches for its matching counterpart on the right side and moves it into place by repeatedly swapping adjacent characters. If a match is found, the right-side pointer moves inward; if no match is found, it indicates that the character is the center of an odd-length palindrome and is positioned accordingly.
// Convert string to list for easier manipulation
char[] chars = s.toCharArray();
// Counter to keep track of the total number of swaps
int moves = 0;
// Loop to find a character from the right (s[j]) that
// matches with a character from the left (s[i])
for (int i = 0, j = chars.length - 1; i < j; ++i) {
int k = j;
for (; k > i; --k) {
// If a matching character is found
if (chars[i] == chars[k]) {
// Move the matching character to the correct position on the right
for (; k < j; ++k) {
// Swap characters
char temp = chars[k];
chars[k] = chars[k + 1];
chars[k + 1] = temp;
// Increment count of swaps
\++moves;
}
// Move the right pointer inwards
--j;
break;
}
}
// If no matching character is found, it must be moved to the center of palindrome
if (k == i) {
moves += chars.length / 2 - i;
}
}
return moves;
}Next Palindrome Using Same Digits
Given a numeric string, numStr, representing a palindrome (composed only of digits). Return the smallest palindrome larger than numStr that can be created by rearranging its digits. If no such palindrome exists, return an empty string “”.
https://www.educative.io/courses/grokking-coding-interview/solution-next-palindrome-using-same-digits
public class Solution {
public static boolean findPerm(List<Character> left) {
int i = left.size()-2;
while(i >=0 && left.get(i) >= left.get(i+1)) i--;
if(i < 0) return false;
int j = left.size()-1;
while(i >=0 && left.get(j) <= left.get(i)) j--;
Collections.swap(left, i, j);
Collections.reverse(left.subList(i + 1, left.size()));
return true;
}
public static String findNextPalindrome(String numStr) {
int n = numStr.length();
boolean odd = n%2 ==1 ? true : false;
ArrayList<Character> left = new ArrayList<>();
for(int i =0; i < n/2; i++)left.add(numStr.charAt(i));
if(!findPerm(left)) return "";
StringBuilder sb = new StringBuilder();
for(char c : left)sb.append(c);
String mid = odd ? String.valueOf(numStr.charAt(n/2)) : "";
return sb.toString() + mid + sb.reverse().toString();
}
}Lowest Common Ancestor of a Binary Tree III
You are given two nodes, p and q. The task is to return their lowest common ancestor (LCA). Both nodes have a reference to their parent node. The tree’s root is not provided; you must use the parent pointers to find the nodes’ common ancestor
This solution finds the lowest common ancestor (LCA) of two nodes in a binary tree using a smart two-pointer approach. We start by placing one pointer at node p and the other at node q. Both pointers move up the tree at each step by following their parent pointers. If a pointer reaches the root (i.e., its parent is None), it jumps to the other starting node. This process continues until the two pointers meet. The key idea is that by switching starting points after reaching the top, both pointers end up traveling the same total distance, even if p and q are at different depths. When they meet, that meeting point is their lowest common ancestor.
public static EduTreeNode LowestCommonAncestor(EduTreeNode p, EduTreeNode q) {
EduTreeNode ptr1 = p;
EduTreeNode ptr2 = q;
while (ptr1 != ptr2) {
if (ptr1.parent != null) {
ptr1 = ptr1.parent;
}
else {
ptr1 = q;
}
if (ptr2.parent != null) {
ptr2 = ptr2.parent;
} else {
ptr2 = p;
}
}
return ptr1;
}Count Pairs Whose Sum is Less than Target
You are given a 0-indexed integer array, nums, of length nn, and an integer target. Your task is to determine the number of distinct pairs of indexes (i,j)(i,j) such that:
0≤i<j<n0≤i<j<n (i.e., ii comes before jj in the array) The sum of the elements of the indexes (i,j)(i,j), (i.e., nums[i]+nums[j]nums[i]+nums[j]), is strictly less than the target.
public static int countPairs(List<Integer> nums, int target) {
Collections.sort(nums);
int count = 0;
int low = 0, high = nums.size() - 1;</Integer>
while (low < high) {
if (nums.get(low) + nums.get(high) < target) {
count += (high - low);
low++;
} else {
high--;
}
}
return count;
}Count Subarrays With Fixed Bounds
Given an integer array, nums, and two integers minK and maxK, return the number of fixed-bound subarrays.
A subarray in nums is called a fixed-bound subarray if it satisfies the following conditions:
The smallest value in the subarray equals minK. The largest value in the subarray equals maxK.
On/O1
long countFixedBoundSubarrays(int[] nums, int minK, int maxK) {
int lastMin = -1, lastMax = -1, lastBad = -1;
long ans = 0;
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
// Out of range -> reset window
if (x < minK || x > maxK) {
lastBad = i;
}
if (x == minK) lastMin = i;
if (x == maxK) lastMax = i;
int leftMostValid = Math.min(lastMin, lastMax);
if (leftMostValid > lastBad) {
ans += leftMostValid - lastBad;
}
}
return ans; }Get the Maximum Score
You are given two sorted arrays of distinct integers, nums1 and nums2.
A valid path is constructed according to the following rules:
You start at the index 00 of either nums1 or nums2. From there, you must traverse the chosen array from left to right. Suppose you encounter a number in both arrays (a common element, not necessarily at the same index). In that case, you may choose to switch to the other array at that element and continue the traversal from that point forward. A common element can only be counted once in the total path score, regardless of the array it appears.
The score of a path is defined as the sum of all unique elements visited during traversal. Your task is to return the maximum possible score achievable by any valid path. As the answer may be too large, return the maximum score modulo 109+7109+7.
On O1
Approach (3 steps)
Parallel traversal: p1, p2 advance through nums1, nums2 Track paths: sum1, sum2 = max sums if currently following each array Merge at commons: When nums1[p1] == nums2[p2], sum1 = sum2 = max(sum1,sum2) + common
public static int maxSum(int[] nums1, int[] nums2) {
int pointer1 = 0, pointer2 = 0;
int len1 = nums1.length, len2 = nums2.length;
long sum_path1 = 0, sum_path2 = 0;
int MOD = 1_000_000_007;
while (pointer1 < len1 || pointer2 < len2) {
if (pointer1 < len1 && (pointer2 == len2 || nums1[pointer1] < nums2[pointer2])) {
sum_path1 += nums1[pointer1++];
} else if (pointer2 < len2 && (pointer1 == len1 || nums1[pointer1] > nums2[pointer2])) {
sum_path2 += nums2[pointer2++];
} else {
sum_path1 = sum_path2 = Math.max(sum_path1, sum_path2) + nums1[pointer1];
pointer1++;
pointer2++;
}
}
return (int)(Math.max(sum_path1, sum_path2) % MOD);
}Append Characters to String to Make Subsequence
You’re given two strings, source and target, made up of lowercase English letters. Your task is to determine the minimum number of characters that must be appended to the end of the source so that the target becomes a subsequence of the resulting string.
- Two pointers: sourceIndex, targetIndex
- Scan source once:
- MATCH → advance targetIndex
- NO MATCH → skip source char
- Unmatched target suffix length = answerpublic int appendCharacters(String source, String target) {
int sourceIndex = 0;
int targetIndex = 0;
final int sourceLength = source.length();
final int targetLength = target.length();while (sourceIndex < sourceLength && targetIndex < targetLength) { if (source.charAt(sourceIndex) == target.charAt(targetIndex)) { targetIndex += 1; } sourceIndex += 1; } return targetLength - targetIndex; }
Given sorted array (negatives → positives), return squares in sorted order.
ON/ ON
- Two pointers: left=0, right=n-1
- Fill result BACKWARDS from pos=n-1 into separate result array
- Compare |nums[left]| vs |nums[right]|
- Pick LARGER square → place at pos–
- No merging needed (largest squares first)public static int[] sortedSquares(int[] nums) {
int n = nums.length;int[] res = new int[n]; int left = 0, right = n - 1; int pos = n - 1; while (left <= right) { if (Math.abs(nums[left]) > Math.abs(nums[right])) { res[pos] = nums[left] * nums[left]; left++; } else { res[pos] = nums[right] * nums[right]; right--; } pos--; } return res; }
Intersection of Two Linked Lists
Hint – Same as LCA for Tree Nodes
Try to solve the Intersection of Two Linked Lists problem using the Two Pointers pattern.
Statement
You are given the heads of two singly linked lists, headA and headB, to determine whether the two lists intersect. If they intersect, return the node where the intersection begins. Otherwise, return NULL.
O(N+M) / O1
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// Initialize two pointers, each starting at the head of one list
ListNode ptrA = headA;
ListNode ptrB = headB;
// Traverse both lists until the two pointers meet
// If the lists intersect, they will eventually point to the same node
// If not, both will become null at the same time and the loop will stop
while (ptrA != ptrB) {
// When ptrA reaches the end of its list, move it to the head of list B
// Otherwise, move it to the next node
ptrA = (ptrA == null) ? headB : ptrA.next;
// When ptrB reaches the end of its list, move it to the head of list A
// Otherwise, move it to the next node
ptrB = (ptrB == null) ? headA : ptrB.next;
}
// When the loop ends, ptrA and ptrB are either both null (no intersection)
// or both point to the intersection node
return ptrA;
}Remove Element
You are given an integer array, nums, and an integer, val. Your task is to remove all occurrences of val from nums in place, meaning no additional memory allocation should be used. The relative order of the elements in the array may be changed. After modifying the array, return the number of elements that are not equal to val.
Let kk represent the number of elements in nums that are not equal to val. To successfully solve this problem, you need to ensure the following:
Initialize an iterator, k, with 0 to be at the start of the array.
Initialize another iterator, j, with 0 to iterate over the array. For each integer, nums[j]:
If it’s not equal to val, put the integer nums[j] at nums[k] and increment k.
After the loop, return k representing the count of elements not equal to val.String Compression
Given an array of characters, chars, compress it in place according to the following rules:
Start with an empty string s.
For each group of consecutive repeating characters in chars:
If the group length is 11, append just the character to s.
Otherwise, append the character followed by the group length.public class Solution {
public static int compress(char[] chars) {
int n = chars.length;
int w = 0; // write pointer
int i = 0; // read pointer
while (i < n) {
int j = i;
// advance j to the end of the current run
while (j < n && chars[j] == chars[i]) j++;
int count = j - i;
// write the character
chars[w++] = chars[i];
// write the count digits if > 1
if (count > 1) {
for (char c : String.valueOf(count).toCharArray()) {
chars[w++] = c;
}
}
i = j; // next run
}
return w;
} }Partition Labels
You are given a string s. Your task is to divide the string into as many parts as possible such that each letter appears in at most one part.
In other words, no character should occur in more than one partition. After concatenating all parts in order, the result should be the original string s.
Core idea
Each partition must extend at least to the last index of every character it contains; otherwise that character would appear in multiple partitions.
So while scanning from left to right, you keep track of how far the current partition must extend to include the last occurrence of all characters seen so far.
public List<Integer> partitionLabels(String s)
{
int[] lastOccurrence = new int[26];
for (int i = 0; i < s.length(); i++) {
lastOccurrence[s.charAt(i) - 'a'] = i;
}</Integer>
int partitionEnd = 0;
int partitionStart = 0;
List<Integer> partitionSizes = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
partitionEnd = Math.max(partitionEnd, lastOccurrence[s.charAt(i) - 'a']);
if (i == partitionEnd) {
partitionSizes.add(i - partitionStart + 1);
partitionStart = i + 1;
}
}
return partitionSizes;
}Next Permutation
Your task is to rearrange an array, nums, containing positive integers to form the next lexicographically greater permutation. This means finding the next permutation in the sequence of all possible arrangements sorted in dictionary order. For example, given the array [4,5,6][4,5,6], the next permutation is [4,6,5][4,6,5]. In the same way, [5,6,4][5,6,4] becomes [6,4,5][6,4,5]. If the array is already in its highest possible order (sorted in descending order), such as [6,5,4][6,5,4], it’s not possible to find a lexicographically larger permutation. In this case, you must rearrange the array to its lowest possible order (sorted in ascending order), which would be [4,5,6][4,5,6]. The entire operation must be completed in-place while using only a constant amount of extra memory.
1] Find the pivot: We scan from the right to find the first element (pivot) that is smaller than its right neighbor. This is the element we will increase.
2] Find the successor: We scan from the right again to find the smallest element (successor) that is larger than the pivot.
3] Swap: We swap the pivot and the successor.
Reverse the suffix: We reverse the part of the array to the right of the pivot’s original position. This ensures the new suffix is in its smallest possible order (ascending). This single reverse operation also cleverly handles both possible scenarios:
Case 1 (pivot is found): The suffix (from i+1i+1 onward) was previously in descending order. Reversing it sorts it into ascending order. This makes the new permutation as small as possible, ensuring it’s the immediate next one.
Case 2 (no pivot is found): If the array were already in its largest order (e.g., [3,2,1][3,2,1]), the first loop would finish with i=−1i=−1. This final step will then reverse from i+1i+1 (which is index 00) to the end, correctly transforming the entire array into its smallest possible order (e.g., . [1,2,3][1,2,3]).
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i + 1] <= nums[i]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1, nums.length - 1);
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}Rotate Array
Given an integer array, nums, shift its elements to the right by k positions. In other words, rotate the array to the right by k steps, where k is non-negative.
[https://www.educative.io/courses/grokking-coding-interview/solution-rot
Normalize the rotation steps. Compute the length of the array, n, and set k = k % n to handle cases where k is greater than n. This ensures we only rotate by the effective number of steps.
Reverse the entire array. Set two pointers: left = 0 and right = n - 1. While left < right, swap nums[left] and nums[right], then move the pointers inward (left += 1, right -= 1). Reverse the first k elements. Set left = 0 and right = k - 1. While left < right, swap nums[left] and nums[right], then move both pointers inward. Reverse the remaining n - k elements. Set left = k and right = n - 1. While left < right, swap nums[left] and nums[right], then move both pointers inward. After these three reversals, all elements in nums will have been rotated to the right by k steps in place.
public static void rotate(int[] nums, int k) {
int n = nums.length;
k = k%n;
reverse(nums, 0, n-1); reverse(nums, 0, k-1); reverse(nums, k, n-1);
// Write your solution code here
}
public static void reverse(int[] nums, int start, int end) {
while (start < end){
int t = nums[start]; nums[start++] = nums[end]; nums[end--] = t;
}
// Write your solution code here
}
}
