Introduction to Two Pointers

Question 1

Given an array of integers, move all zeros to the end of the array.

Answer 1

Solution: Two Pointers

Explanation: Start two pointers, left and right, at the start of the array. If the right pointer encounters a nonzero element, swap elements at left and right positions and increment both pointers. If the right pointer encounters zero, increment the right pointer. Repeat until the right pointer reaches the end of the array.

Question 2

Generate a string of 𝑛 n balanced parentheses.

Answer 2

Solution: Some other pattern

Explanation: Generating a string of balanced parentheses requires a different approach, such as backtracking, because it involves forming a specific pattern with nested parentheses. This kind of pattern generation is not supported by the two pointers pattern.

Question 3

Find any three values in a sorted array that sum up to 825.

Answer 3

Solution: Two Pointers

Explanation: By iterating through the array and considering each value, we calculate the sum of the current value and the other two values. To find the other two values, we can utilize two pointers in each iteration: one starting from the leftmost element and the other from the rightmost element. Comparing this sum with 825, we increment or decrement the pointers accordingly.

Question 4

Find all permutations of the following set of elements: {1, 2, 3}.

Answer 4

Solution: Some other pattern

Explanation: Finding permutations requires generating all possible combinations, which involves exploring various branches of a decision tree. This process does not align with the linear traversal approach of the two pointers pattern, making it unsuitable for solving permutation problems.

Question 5

Valid Palindrome

Answer 5

import java.util.*;
public class Main{
public static boolean isPalindrome(String s) {
if(s == null || s.length() == 0) return true;
int l = 0, r = s.length() -1;
while(l <= r) {
if(s.charAt(l) == s.charAt(r)) {
l++;
r–;
} else {
return false;
}
}
return true;
}
}

Question 6

Sum of Three Values

Answer 6

import java.util.*;

public class SumOfThree{
public static boolean findSumOfThree(int[] nums, int target) {
int r = nums.length - 1;
Arrays.sort(nums);
for(int i = 0; i < nums.length - 2; i++) {
int l = i+1;
while(l < r) {
int sum = nums[i]+nums[l]+ nums[r];
if(sum == target)
return true;
else if(sum < target) {
l++;
} else {
r–;
}
}
}
return false;
}
}

Question 7

Remove nth Node from End of List

Answer 7

import java.util.*;
class ReverseLinkedList {
public static LinkedListNode removeNthLastNode(LinkedListNode head, int n) {
LinkedListNode r = head;
LinkedListNode l = head;
for(int i = 0; i < n; i++) {
r = r.next;
}
if(r == null) {
return head.next;
}
while(r.next != null) {
r = r.next;
l = l.next;
}
l.next = l.next.next;

    return head;
} }

Question 8

Sort Colors

Answer 8

import java.util.*;

public class Solution {
public static int[] sortColors (int[] colors) {
int current = 0, start = 0, end = colors.length - 1;
while(current <= end) {
if(colors[current] == 0) {
if(colors[start] != 0) {
int t = colors[start];
colors[start] = colors[current];
colors[current] = t;
}
current++;
start++;
} else if(colors[current] == 1) {
current++;
} else {
if(colors[end] != 2) {
int t = colors[end];
colors[end] = colors[current];
colors[current] = t;
}
end–;
}
}
return colors;
}
}

Question 9

Reverse Words in a String

Answer 9

import java.util.*;

public class Solution {
private static void strRev(char[] seq, int start, int end) {
while(start < end) {
char t = seq[start];
seq[start] = seq[end];
seq[end] = t;
start++;
end–;
}
}
public static String reverseWords(String sentence) {
sentence = sentence.replaceAll(“\s+”,” “).trim();
char[] ch = sentence.toCharArray();
int endLen = ch.length - 1;
strRev(ch, 0, endLen);

    for(int start = 0, end = 0; end <= endLen;end++) {
        if(ch[end] == ' ' || end == endLen) {
            int endIdx = (end == endLen) ? end : end - 1;
            strRev(ch, start, endIdx);
            start = end+1;
        }
        
    }
    return new String(ch);
} }

Question 10

Valid Palindrome II

Answer 10

import java.util.*;

public class Main{
public static boolean isPalindrome(String s) {

    int start = 0, end = s.length() - 1;
    int charToRemoveCount = 0;
    while(start <= end) {
        if(s.charAt(start) == s.charAt(end)) {
            start++;
            end--;
           
        } else {
            return isPalindrome(s, start+1, end) 
                || isPalindrome(s, start, end-1);
            
        }
    }
    
    return true;
}

private static boolean isPalindrome(String s, int i, int j) {
    while(i <= j) {
        if(s.charAt(i) == s.charAt(j)) {
            i++;
            j--;
        }
        else return false;
    }
    return true;
} }