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
input = {1,2,3,1,2,6,8,3,5,7,2,9,5,3,4}
output=
1: 2
2: 3
3: 3
4: 1
5: 2
6: 1
7: 1
8: 1
9: 1

Brute Force Approach:

boolean visited[] = new boolean[arr.length];
for(int i=0 ; i<n ; i++){
count=0;
if(visited[i]==true)
continue;

for(int j=i ; j<n l j++){

if(arr[i]==arr[j]){
count++;
visited[i]=true;
}
}
print(arr[i]+": "+ count);
}

Optimized with HashMap Java:

HashMap<Integer, Integer> hm = new HashMap<>();
for(int i=0 ; i<n ; i++){
if(hm.containsKey(arr[i]))
hm.put(arr[i], hm.get(arr[i])+1);
else
hm.put(arr[i], 1);

//hm.put(arr[i], getOrDefault(arr[i],0)+1);
}

Optimized with HashMap C++:

unordered_map<int, int> hm;
for(int i=0 ; i<n i ++){
if(hm.find(arr[i]) != hm.end())
hm[arr[i]] = hm[arr[i]]+1;
else
hm[arr[i]]=1;
//hm[arr[i]]++;
}

387. First Unique Character in a String

class Solution {
public int firstUniqChar(String s) {
int freq[] = new int[26];
int n=s.length();

//Count the frequency of each character

for(int i=0 ; i<n ; i++)
freq[s.charAt(i)-'a']++;
 //Find the first character with frequency 1.
for(int i=0 ; i<n ; i++)
if(freq[s.charAt(i)-'a']==1)
return i;
return -1;
}
}

560. Subarray Sum Equals K

Input: nums = [1,1,1], k = 2
Output: 2

SubArrays:
1
1 1
1 1 1
1 1
1

class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer,Integer> prefixCount = new HashMap<>();
prefixCount.put(0,1); //prefix sum 0 seen once

int prefixSum=0, count=0;

for(int num: nums){

prefixSum += num;
if(prefixCount.containsKey(prefixSum-k))
count += prefixCount.get(prefixSum-k);
prefixCount.put(prefixSum, prefixCount.getOrDefault(prefixSum,0)+1);
}
return count;
}
}

Prefix Array
arr[] = {1,2,3,4,5}
res[] = {1,3,6,10,15}

Brute Force:
for(int i=0 ; i<n ; i++)
int sum=0;
for(int j=0 ; j<=i ; j++)
sum+=arr[j];
print(sum);

Optimized:
res[0]=arr[0];
for(int i=1 ; i<n l i++)
res[i]=res[i-1]+arr[i];
Problem Statement:
Sum of array between indices L and R.
arr[] = {1,2,3,4,5,6}
arr[][]= {{1,6}, {2,4}, {4,5}, {1,5}}

Output = 21 9 9 15
arr[] = {1,2,3,4,5,6}
res[] = {0,1,3,6,10,15,21}

class Main{
PSVM(){
int arr[] = {1,2,3,4,5,6};
int arr1[][]= {{1,6}, {2,4}, {4,5}, {1,5}};
int prefix[] = new int[arr.length+1];
prefix[1]=arr[0];
for(int i=2 ; i<=n ; i++)
prefix[i] = prefix[i-1]+arr[i-1];

for(int i=0 ; i<arr1.length ; i++){

int L=arr1[i][0];
int R=arr1[i][1];
print(prefix[R]-prefix[L-1]);
}
}
}

724. Find Pivot Index

Input: nums = [1,7,3,6,5,6]
Output: 3

1,7, 3, 6, 5, 6
1 8 11 17 22, 28

L = 11
R = 11

class Solution {
public int pivotIndex(int[] nums) {
int n=nums.length;
int prefix[] = new int[n];
prefix[0]=nums[0];
for(int i=1 ; i<n ; i++)
prefix[i]=prefix[i-1]+nums[i];

for(int i=0 ; i<n ; i++){

int LeftSum = prefix[i]-nums[i];
int RightSum = prefix[n-1]-prefix[i];
if(LeftSum==RightSum){
return i;
}
}
return -1;
}
}
Kadane's Algorithm: is a dynamic programming technique used to find the maximum
subarray sum in an array of numbers on O(n).

arr[] = -2, 1 -3, 4, -1, 2, 1, -5, 4

Ourput- 6

Algorithm:
1. Initalize maxSum=arr[0],the largest sum found so far,
currentSum = 0; the sum of current subarray.
2. Iterate through the array,
Add the current element to currentSum,
If currentSum > maxSum, update maxSum
If currentSum < 0, reset currentSum=0(start new subArray)
3. Return maxSum.

-2, 1 -3, 4, -1, 2, 1, -5, 4

Index element CurrentSum MaxSum

0 -2 -2, reset to 0 -2
1 1 1 1
2 -3 -2, reset to 0 1
3 4 4 4
4 -1 3 4
5 2 5 5
6 1 6 6
7 -5 1 6
8 4 5 6

int kadanesMaxSum(int []arr){

int maxSum=Integer.MIN_VALUE;
int currSum=0;

for(int n: nums){
currSum += n;
if(currSum > maxSum)
maxSum = currSum;
if(currSum < 0)
currSum = 0;
}
return maxSum;
}

363. Max Sum of Rectangle No Larger

class Solution {
public:
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int rows=matrix.size();
int cols=matrix[0].size();
int res=INT_MIN;

for(int left=0 ; left<cols ; left++){

vector<int> rowSum(rows,0);
for(int right = left ; right < cols ; right++){
for(int r=0 ; r<rows ; r++)
rowSum[r]+=matrix[r][right];
 set<int> prefixSet;
prefixSet.insert(0);
int currSum=0;
for(int sum: rowSum){
currSum+=sum;
auto it = prefixSet.lower_bound(currSum-k);
if(it != prefixSet.end())
res = max(res, currSum -* it);
prefixSet.insert(currSum);
}
}
}
return res;
}
};

Prime Sieve
Finding prime number till N.
class PrimeNum{
boolean isPrime(int n){
if(n==1 || n==0) return false;

for(int i=2 ; i<n ; i++)

if(n%i==0)
return false
return true;
}

PSVM(){
int n=50;
for(int i=1 ; i<=N ; i++)
if(isPrime(i))
SOP(i+" ");
}

Sieve of Eratosthenes: O(log log(N))

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
boolean arr[] = f f f f t f t f t t t f t f t t

boolean arr[] = new boolean[n+1];

for(int i=2 ; i*i<=n ; i++)
if(!arr[i])
for(int j=i*i ; j<=n ; j+=i)
arr[j]=ture;

for(int i=2 ; i<=n ; i++)

if(!arr[i])
print(i);

204. Count Primes

class Solution {
public int countPrimes(int n) {
if(n<2)
 return 0;

boolean isPrime[]= new boolean[n];

Arrays.fill(isPrime, true);
isPrime[0]=isPrime[1]=false;

for(int i=2 ; i*i<n ; i++)

if(isPrime[i])
for(int j=i*i ; j<n ; j+=i)
isPrime[j]=false;

int count=0;
for(boolean prime: isPrime)
if(prime)
count++;

return count;
}
}

Pigeon Hole Principle:

if you put more than n objects into n containers, then at least one container must
hold more than one object.

if k>n objects are placed into n boxes, then at least one box contains at least
[k/n] objects.

Example:
if you have 13 socks and 12 drawers, at least one frawer must have 2 or more socks.

Example:
if k objects are placed into n containers, then at lest one container has at least
[k/n] objects.

K=100, n=9;

Pigeonhole Sort:
Example1:
arr = {3,2,1,4,1,2,3,6,3,4,5};

min = 1
max = 6

int newArray[] = new int[max-min+1];

0 1 2 3 4 5 index
2 2 3 2 1 1 elements

Sorted Data: 1 1 2 2 3 3 3 4 4 5 6

Example2:
arr = {13,12,11,14,11,12,13,16,13,14,15};
int newArray[] = new int [max-min+1];
0 1 2 3 4 5
2 2 3 2 1 1

11 11 12 12 13 13 13 14 14 15 16

Example3:
arr = {2, 9999};
min=2
max=9999

int newArray[] = new int[max-min+1];

Questions:
1. You have k objects and n containers. Using Pigeonhole Principle, determine the
minimum number of objects that at least on container must contain.

input1: input2:
K = 13 K=100
N = 12 N=9
Output1 = 2 Ourput2: 12

Algorithm:
1. Read integers k and n.
2. if n==0, output is 0.
3. Apply formula: minObjects: [k/n]
4. Print minObjects.

static int minObj(int n, int k){

if(n==0);
return 0;

int minObjects = (k/n)+1;

//int minObjects = (k+n-1)/n;

return minObjects;
}

2. Find the first missing number.

arr = {2, 7, 9, 3, 4, 8}
min - 2
max = 9
arr[] = new array[8]
0 1 2 3 4 5 6 7
1 1 1 0 0 1 1 1

static int missingNumber(int arr[]){

int n=arr.length;
int min=Integer.MAX_VALUE;
int max=Integer.MIN_VALUE;

//calculate min and max value

for(int i ; i<n ; i++){
if(arr[i]>max)
max=arr[i];
if(arr[i]<min)
 min=arr[i];
}

// create a new array of range

int range = max-min+1;
int phole[] = new int[range];

//fill the new array with frequency

for(int i=0 ; i<n ; i++)
phole[arr[i]-min]++;

//find the index with 0 frequency

for(int i=0 ; i<range ; i++)
if(phole[i]==0)
return i+min;
}

3. Maximum adjacent difference in array in its sorted form:

input1: arr = 1 10 5
output1 = 5

input2: arr = 2 1 11 4 8 20
output = 9

static int calculateDifference(int arr[]){

int n=arr.length;
int min=Integer.MAX_VALUE;
int max=Integer.MIN_VALUE;

//calculate min and max value

for(int i ; i<n ; i++){
if(arr[i]>max)
max=arr[i];
if(arr[i]<min)
min=arr[i];
}

// create a new array of range

int range = max-min+1;
int phole[] = new int[range];

//fill the new array with frequency

for(int i=0 ; i<n ; i++)
phole[arr[i]-min]++;
1 10 5
0 1 2 3 4 5 6 7 8 9
1 0 0 0 1 0 0 0 0 1
int diff=0;
int left=-1;
for(int i=0 ; i<range ; i++){
if(left ==-1 && phole[i]!=0)
left=i;
else if(phole[i]!=0){
int tempDiff = i-left;
if(tempDiff > diff)
diff = tempDiff;
left = i;
}
 }
return diff;

/*for(int i=0 ; i<range ; i++){

if(phole[i]==0)
index++;
else{
diff=Math.max(index,diff);
index=1;
}
}
return diff;*/
}

268. Missing Number

class Solution {
public int missingNumber(int[] nums) {
int n=nums.length;
int sumOfN = n*(n+1)/2;
int sumOfArray=0;
for(int x: nums)
sumOfArray +=x;
return sumOfN-sumOfArray;
}
}

287. Find the Duplicate Number

nums = [1,3,4,2,2]
slow = 2, fast=2
class Solution {
public int findDuplicate(int[] nums) {
int slow=nums[0], fast=nums[0];
do{
slow=nums[slow];
fast=nums[nums[fast]];
}while(slow!=fast);

fast=nums[0];
while(slow!=fast){
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
String ALgorithm
1. KMP Algorith,
2. Z-Value Algorithm
3. Rabin Karp Algorithm
4. Manacher's Algorithm