Two Pointer Flashcards
- 3Sum
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> output = new ArrayList<>();
Arrays.sort(nums);
for(int i =0;i<nums.length;i++){
if(i!=0 && nums[i]==nums[i-1]){
continue;
}
int left = i+1;
int right = nums.length - 1;
while(left<right){
if(nums[i]+nums[left]+nums[right]==0){
List<Integer> li = new ArrayList<>();
li.add(nums[i]);
li.add(nums[left]);
li.add(nums[right]);
left++;
right--;
output.add(li);
while(left<right && nums[left]==nums[left-1]){
left++;
}
while(left<right && nums[right]==nums[right+1]){
right--;
}
}
else if(nums[i]+nums[left]+nums[right]>0){
right--;
}
else left++;
}
}
return output;
} }
- Rotate Array
Medium
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
class Solution {
public void rotate(int[] nums, int k) {
if(nums.length==1){
return;
}
rotateBy(nums, 0, nums.length-1);
rotateBy(nums,0,k-1);
rotateBy(nums, k, nums.length-1);
}
public void rotateBy(int[] nums, int start, int end){
while(start<=end){
int temp = nums[start];
nums[start]=nums[end];
nums[end] = temp;
end--;
start++;
}
} }
- Valid Palindrome
Easy
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
Example 1:
Input: s = “A man, a plan, a canal: Panama”
Output: true
Explanation: “amanaplanacanalpanama” is a palindrome.
Example 2:
Input: s = “race a car”
Output: false
Explanation: “raceacar” is not a palindrome.
class Solution {
public boolean isPalindrome(String s) {
String str = s.replaceAll(“[^a-zA-Z0-9]”, “”).toLowerCase();
int left = 0;
int right = str.length()-1;
while(left<right){
if(str.charAt(left)==str.charAt(right)){
left++;
right–;
}
else {
return false;
}
}
return true;
} }
- K-diff Pairs in an Array
Medium
Given an array of integers nums and an integer k, return the number of unique k-diff pairs in the array.
A k-diff pair is an integer pair (nums[i], nums[j]), where the following are true:
0 <= i, j < nums.length
i != j
|nums[i] - nums[j]| == k
Notice that |val| denotes the absolute value of val.
public class Solution {
public int findPairs(int[] nums, int k) {
Arrays.sort(nums);
int left = 0, right = 1;
int result = 0;
while (left < nums.length && right < nums.length) {
if (left == right || nums[right] - nums[left] < k) {
// List item 1 in the text
right++;
} else if (nums[right] - nums[left] > k) {
// List item 2 in the text
left++;
} else {
// List item 3 in the text
left++;
result++;
while (left < nums.length && nums[left] == nums[left - 1])
left++;
}
}
return result;
}
}
- K-diff Pairs in an Array
Solved
Medium
Given an array of integers nums and an integer k, return the number of unique k-diff pairs in the array.
A k-diff pair is an integer pair (nums[i], nums[j]), where the following are true:
0 <= i, j < nums.length
i != j
|nums[i] - nums[j]| == k
Notice that |val| denotes the absolute value of val.
Example 1:
Input: nums = [3,1,4,1,5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.
class Solution {
public int findPairs(int[] nums, int k) {
Arrays.sort(nums);
int left = 0;
int right = left+1;
int count = 0;
Set<List<Integer>> s = new HashSet<>();
while(left<right & left<nums.length && right<nums.length){
if(nums[right]-nums[left]==k){
List<Integer> li = new ArrayList<>();
li.add(nums[right]);
li.add(nums[left]);
right++;
left++;
if(!s.contains(li)){
s.add(li);
count++;
}
}
else if(nums[right]-nums[left]>k){
left++;
}
else{
right++;
}
}
return count;
}
}</Integer></Integer>
- Merge Sorted Array
Easy
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].
Example 3:
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
m =m-1;
n = n-1;
int curr = nums1.length-1;
while(curr>=0){
if(m<0){
nums1[curr]=nums2[n];
n--;
curr--;
}
else if(n<0){
nums1[curr]=nums1[m];
m--;
curr--;
}
else {
if(nums2[n]>nums1[m]){
nums1[curr]=nums2[n];
curr--;
n--;
}
else {
nums1[curr]=nums1[m];
curr--;
m--;
}
}
} } }
