Two Pointers

Question 1

Pair with Target Sum

Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.
Write a function to return the indices of the two numbers (i.e. the pair) such that they add up to the given target.

Example 1:
Input: [1, 2, 3, 4, 6], target=6
Output: [1, 3]
Explanation: The numbers at index 1 and 3 add up to 6: 2+4=6

TC - O(n)
SC - O(1)

Answer 1

Pseudo Code:
1. Initialize startIndex with zeor, endIndex array length minus one, sum with zero.
2. Iterate array until startIndex is less than endIndex.
3. Sum of startIndex and endIndex element
4. If sum is less than given value then increase startIndex
Else if sum is greater than given value then decrease endIndex.
Else If sum is equal to given value return startIndex and endIndex as an array.

Question 2

125. Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Note: For the purpose of this problem, we define empty string as valid palindrome.
Example 1:
Input: "A man, a plan, a canal: Panama"
Output: true
Example 2:
Input: "race a car"
Output: false
TC – O(n)
SC – O(1)

Answer 2

Pseudo code:
1. Convert string to char array.
2. Initialize two int variable, assign 0 to i and string len -1 to j.
3. Iterate while loop until i is less than string len OR j greater than or equal to 0.
a. If char at ith index is not character continue loop by increasing i value to 1
b. If char at jth index is not character continue loop by decreasing j value to 1.
c. If char at ith & jth index is not similar, return false.
d. Increase ith and decrease jth by 1.
4. Return true;
Takeaway: We can improve the same program by two pointer and ascii value of char.

Code
class Solution {
public boolean isPalindrome(String s) {
int start=0;
int end=s.length()-1;
while(start<=end){
int cs=s.charAt(start);
int ce=s.charAt(end);
if(!((cs>=48 && cs<=57) ||(cs>=65 && cs<=90)||(cs>=97 && cs<=122))){
start++;
continue;
}
if(!((ce>=48 && ce<=57) ||(ce>=65 && ce<=90)||(ce>=97 && ce<=122))){
end–;
continue;
}
//ignore case
if((cs>=65 && cs<=90)) {
cs-=65;
}else if((cs>=97 && cs<=122)) {
cs-=97;
}
if((ce>=65 && ce<=90)) {
ce-=65;
}else if((ce>=97 && ce<=122)) {
ce-=97;
}

	            if(cs==ce){
	                start++;
	                end--;
	            }else{
	                return false;
	            }
	        }
	        return true;
	    }
}