1.
Two Pointer
1. Check Palindrome or Not:
i
arr[] = 2 3 4 1 1 4 3 2
j
Output: True
for(int i=0, j=n-1 ; i<j ; i++, j--){
if(arr[i]!=arr[j])
return false;
}
return true;
125. Valid Palindrome
class Solution {
public boolean isPalindrome(String s) {
int left=0, rights.length()-1;
while(left<right){
while(left<right && !isalnum(s[left]))
left++;
while(left<right && !isalnum(s[right]))
right--;
if(tolower(s[left]) != tolower(s[right]))
return false;
left++;
right--;
}
return true;
}
}
283. Move Zeroes
class Solution { 1,3,12,0,0
public:
void moveZeroes(vector<int>& nums) {
int n=nums.size();
int j=0;
for(int i=0 ; i<n ; i++){
if(nums[i] != 0 && nums[j]==0){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
if(nums[j]!=0){
j++;
}
}
}
};
149. Rearrange Array Elements by Sign
class Solution {
public int[] rearrangeArray(int[] nums) {
int n=nums.length;
int ans[] = new int[n];
int pos=0, neg=1;
for(int x: nums){
if(x>0){
ans[pos]=x;
pos+=2;
}
else{
ans[neg]=x;
neg+=2;
}
}
return ans;
}
}
26. Remove Duplicates from Sorted Array
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n=nums.size();
int j=0;
for(int i=1 ; i<n ; i++){
if(nums[i] != nums[j]){
j++;
nums[j]=nums[i];
}
}
return j+1;
}
};
189. Rotate Array
nums = [1,2,3,4,5], k=5
nums = [1,2,3,4,5,6,7], k = 3
reverse entire array: 7 6 5 4 3 2 1
reverse 0 to k: 5 6 7 4 3 2 1
reverse k to n-1: 5 6 7 1 2 3 4
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n=nums.size();
k=k%n;
reverse(nums, 0, n); //Reverse entire vector
reverse(nums, 0, k-1); //Reverse the first k elements
reverse(nums, k, n); //Reverse the rest vector
}
private:
void reverse(vector<int>& nums, int left, int right){
while(left<right){
int temp=nums[left];
nums[left]=nums[right];
nums[right]=temp;
left++;
right--;
}
}
};
27. Remove Element
Solve it by Yourself, Solution is same as question 26
42. Trapping Rain Water
class Solution {
public:
int trap(vector<int>& height) {
}
};
2. Sliding Window
Types of Sliding Window
a. Fixed size
b. Variable size
a. Fixed size
1. Sum of min and max element of all subarrays of size w;
int arr[] = {1,2,3,4,5,6,7,8};
int w=3;
1 2 3 4
2 3 4 6+4=10
3 4 5 8+10=18
4 5 6 10+18=28
5 6 7 12+28=40
6 7 8 14+40=54
main{
int arr[] = {1,2,3,4,5,6,7,8};
int w=3;
cout << subArraySum(arr,w);
}
subArraySum(int arr, int w){
int total=0;
int n=arr.length;
for(int i=0 ; i<n ; i++){
int len=0;
for(int j=i ; j<n ; j++){
len++;
if(len==2){
int min=Integer.MAX_VALUE;
int max=Integer.MIN_VALUE;
for(int k=i ; k<=j ; k++){
if(min>arr[k])
min=arr[k];
if(max<arr[k])
max=arr[k];
}
total +=min+max;
}
}
}
return total;
}
2. Count distinct elements in every window of size w.
arr[] = {1,2,1,3,4,2,3}
int w=4
Output - 3 4 4 3
1 2 1 3 3
2 1 3 4 4
1 3 4 2 4
3 4 2 3 3
Solution:
vector<int> countDistinct(int arr[], int n, int w){
unordered_map<int, int> freq;
vector<int> res;
//insert first window in map arr = 1,2,1,3,4,2,3 w=4
for(int i=0 ; i<w ; i++)
freq[arr[i]]++; Map
Key Value
res.push_back(freq.size());
2 1
//Process the remaining window 3 2
for(int i=w ; i<n ; i++){ 4 1
if(freq[arr[i-w]]==1) res = 3 4 4 3
freq.erase(arr[i-w]);
else
freq[arr[i-w]]--;
freq[arr[i]]++;
res.pus_back(freq.size());
}
return res;
}
int main(){
int arr[] = {1,2,1,3,4,2,3};
int w=4;
int n=arr.length;
vector<int> res= countDistinct(arr, n, w);
239. Sliding Window Maximum
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
class Solution {
public: nums = [1,3,-1,-3,5,3,6,7], k = 3
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq; i = 0 1 2 3 4 5 6
vector<int> res; dq = 7
res = 3 3 5 5 6 7
for(int i=0 ; i<nums.size() ; i++){
if(!dq.empty() && dq.front()==i-k)
dq.pop_front();
while(!dq.empty() && nums[dq.back()] < nums[i])
dq.pop_back();
dq.push_back(i);
if(i>=k-1)
res.push_back(nums[dq.front()]);
}
return res;
}
};
b. Variable size
3. Longest Substring Without Repeating Characters
Input: s = "abcabcbb"
Output: 3
class Solution {
public int lengthOfLongestSubstring(String s) { //abcabcbb
HashMap<Character, Integer> hm = new HashMap<>();
int maxLen=0, start=0; MAP
a 3
for(int end=0 ; end<s.length() ; end++){ 7 b 7
char ch=s.charAt(end); b c 5
if(hm.containsKey(ch) && hm.get(ch)>=start)
start = hm.get(ch)+1; 7
hm.put(ch, end);
maxLen = Math.max(maxLen,end-start+1); 3
}
return maxLen;
}
}
438. Find All Anagrams in a String
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> res;
if(p.length() > s.length())
return res;
vector<int> freq(26, 0);
//Fill the frequency of pattern
for(char c: p)
freq[c-'a']++;
cbaebabacd
int left=0, right=0; freq 0123456789
int charsToMatch=p.size(); 110-1
while(right<s.size()){
if(freq[s[right]-'a']-- >0) L=8 R=10
charsToMatch--; CTM=2
if(right-left+1 == p.size()){ res = 0 6
if(charsToMatch==0)
res.push_back(left);
if(freq[s[left]-'a']++ >=0)
charsToMatch++;
left++;
}
right++;
}
return res;
}
};
76. Minimum Window Substring
class Solution {
public:
string minWindow(string s, string t) {
vector<int> need(128,0);
int required=t.size(), bestLeft=-1, minLen=INT_MAX;
for(char c: t)
need[c]++;
for(int left=0, right=0; right<s.size() ; right++){
if(--need[s[right]]>=0)
required--;
while(required==0){
if(right-left+1 < minLen){
bestLeft=left;
minLen = right-left+1;
}
if(++need[s[left]]>0)
required++;
left++;
}
}
return (bestLeft==-1 ? "" : s.substr(bestLeft, minLen));
}
};
Frequency Array
Prefix Array
KDanes Algorithm
Prime Sieve
Pigeon Hole Algorithm
String ALgorithm
1. KMP Algorith,
2. Z-Value Algorithm
3. Rabin Karp Algorithm
4. Manacher's Algorithm
