Kumar k sir Notes
Lecture:-0+1
Hash Array :- an array which contains frequency of number of occurrence of any number
in which number is represented by an index.
It works for +ve numbers from 0 to n ...
Not good for large array sizes.
EX:- ARRAY :- 0 1 2 3 4 5 6 ← Index
5 1 5 5 8 1 8
So,Max element of the above array is 8, we will create a hash array of size
equal to max element (i.e 8 here), initially value will be 0 .
We will iterate each and every value of the above array and replace the element 0f
hash array from 0 to required frequency.
EX:- Hash Array:- 0 1 2 3 4 5 6 7 8 ← Index
0 2 0 0 0 3 0 0 2
So, here index 1 is showing how many times 1 comes in the main array.
NOTE:- Hash array is wasting spaces.
Lecture:-2
Hash Map:- It is an Vertical table which contains key and value where key represent
number and value represent frequency of that number(occurrence of any
number).
It works for all integers numbers from -infinite to +infinite ...
It never stores the duplicate key.
All operations take O(1) time like insertion,erasing ,finding etc.
EX:- ARRAY :- 0 1 2 3 4 5 6 ← Index
5 1 5 5 8 1 8
5 3
1 2
8 2
Key value
This above is Hash map(or unordered_map) means values are present in any order.
NOTE:- Hashmap takes O(n) Space in worst case when all
elements are different in array.
Note:- 1) Header file like this :- #include<unordered_map>
2)Declaration :- unordered_map<int,int>m;
Code Ex1:-
#include<iostream>
#include<unordered_map>
using namespace std;
int main(){
unordered_map<string,int>mp;
pair<string , int>p1;
p1.first = "prince kumar";
p1.second = 20;
pair<string ,int>p2;
p2.first = "piyush kumar";
p2.second = 20;
pair<string , int>p3;
p3.first = "aastha kumari";
p3.second = 20;
mp.insert(p1);
mp.insert(p2);
mp.insert(p3);
//for printing the values of mp
// for(pair<string,int>ele : mp){
// cout<<ele.first<<" "<<ele.second<<endl;
// }
//for printing the values of mp
for(auto ele : mp){
cout<<ele.first<<" "<<ele.second<<endl;
}
}
unordered_map<data_type,data_type>mp ← any data types can come
Code EX2:-
#include<iostream>
#include<unordered_map>
using namespace std;
int main(){
unordered_map<string,int>m;
m["prince kumar"]=20;
m["kumar sangakara"]=36;
m["virat kohli"]=18;
//printing the values of the map.
for(auto val : m){
cout<<val.first<<" "<<val.second<<endl;
}
// want to get size of map i.e map.size() name
cout<<m.size()<<endl;
//want to delete any value
m.erase("kumar sangakara");
for(auto val : m){
cout<<val.first<<" "<<val.second<<endl;
}
return 0;
}
LECTURE 4:-
Ques:- Given an array of some elements. Find the element which has
min freq and also an element which has maximum freq(that element also).
HINT:-
a) Use hash_map to store the value with their frequence
b) T.C :- O(n) , S.C:- O(n)
c) Brute force method takes time complexity :- O(n2),S.C:- O(n)
Code:-
#include<iostream>
#include<unordered_map>
#include<vector>
#include<climits>
using namespace std;
int main(){
vector<int>v;
int n ;
cout<<"enter the size of the array:-";
cin>>n;
cout<<"enter the element of the array:-";
for(int i=0;i<n;i++){
int q;
cin>>q;
v.push_back(q);
}
unordered_map<int,int>mp;
int max_freq_ele;
int max_freq_val=0;
int min_freq_ele;
int min_freq_val=INT_MAX;
for(int i=0;i<n;i++){
// if number is not present then insert it.
mp[v[i]]++;
}
for(auto ele : mp){
if(ele.second > max_freq_val){
max_freq_val = ele.second;
max_freq_ele = ele.first;
}
}
for(auto ele : mp){
if(ele.second < min_freq_val && ele.second != max_freq_val){
min_freq_val = ele.second;
min_freq_ele = ele.first;
}
}
cout<<"The max freq ele is :-"<<max_freq_ele<<" With
freq:-"<<max_freq_val<<endl;
cout<<"The min freq ele is :-"<<min_freq_ele<<" With
freq:-"<<min_freq_val<<endl;
}
O/P:- enter the size of the array:-6
enter the element of the array:-3 4 2 3 2 3
The max freq ele is :-3 With freq:-3
The min freq ele is :-4 With freq:-1
LECTURE 5:-
Ques:- Given an array of some elements. Find the element which can
forms a pair with distance less than or equal to k.
Return all the possible pairs.
EXAMPLE:-
0 1 2 3 4 5 ← Index.
3 2 3 2 5 3
Output:- 3,2
HINT:-
a) Use hash_map to store the value with its last occurrence position
b) You will get the same again then check the distance of last occu.. and
current occurrence , if you get less than or equal to k, store it
b) T.C :- O(n) , S.C:- O(n)
c) Brute force method takes time complexity :- O(n2),S.C:- O(n)
Code:-
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
int main(){
vector<int>v;
int n ;
cout<<"enter the size of the array:-";
cin>>n;
cout<<"enter the element of the array:-";
for(int i=0;i<n;i++){
int q;
cin>>q;
v.push_back(q);
}
unordered_map<int,int>mp;//val,index.
int k;
cout<<"enter the value K distance:-";
cin>>k;
vector<int>ans;
for(int i=0;i<n;i++){
if(mp.find(v[i]) != mp.end()){
int idx = mp[v[i]];
if(i-idx <= k){
ans.push_back(v[i]);
}
mp[v[i]] = i;
}
else mp[v[i]]=i;
cout<<"all the pairs happend with the dis less than or equal to K are:-";
if(ans.size()==0) cout<<0;
else{
for(int i=0;i<ans.size();i++){
cout<<ans[i]<<" ";
}
}
}
Output:- enter the size of the array:-6
enter the element of the array:-3 2 3 2 5 3
enter the value K distance:-2
all the pairs happend with the dis less than or equal to K are:-32
Hashing prefix sum lect:-5
Find the pair of elements whose difference is exactly equal to k.(k>=0)
Hint:-
A) arr[i]-arr[j] = k => arr[i] = arr[j]+k & arr[j]-k.
EXAMPLE:-
0 1 2 3 4 ← Index.
1 5 3 4 2
k=2.
B)Create a unordered_map & Iterate on each and every element of array,
While iteration check at each element that what difference you required
to complete the sum or how much value remaining to complete sum
Ex:- at i=0, rem = k-arr[i]=2-1=1 or 1+?=k
Check this rem=1 is present inside the map or not , if not , put this
arr[i] into map with its index
If present simply return that value .
CODE:-
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
int main(){
vector<int>v;
int n ;
cout<<"enter the size of the array:-";
cin>>n;
cout<<"enter the element of the array:-";
for(int i=0;i<n;i++){
int q;
cin>>q;
v.push_back(q);
}//1 5 3 2 4
int k;
cout<<"enter the value of K:-";
cin>>k;
unordered_map<int,int>mp;//value,index.
for(int i=0;i<n;i++){
int dif_rem = k-v[i];
int sum_rem = k+v[i];
if(dif_rem<0) dif_rem*=-1;
if(mp.find(dif_rem) != mp.end()){
cout<<"pair is "<<dif_rem<<","<<v[i]<<" at index
"<<mp[dif_rem]<<" and "<<i<<" respectively"<<endl;
}
else{ // remain value is not present inside the map.
mp[v[i]] = i;
}
if(mp.find(sum_rem) != mp.end()){
cout<<"pair is "<<sum_rem<<","<<v[i]<<" at index
"<<mp[sum_rem]<<" and "<<i<<" respectively"<<endl;
}
else{ // remain value is not present inside the map.
if(mp.find(v[i]) == mp.end()) mp[v[i]] = i;
}
}
O/P:- enter the size of the array:-5
enter the element of the array:-1 5 3 4 2
enter the value of K:-2
pair is 1,3 at index 0 and 2 respectively
pair is 5,3 at index 1 and 2 respectively
pair is 4,2 at index 3 and 4 respectively
Hashing prefix sum lect:-7
Find the number of subarrays whose sum is exactly equal to k.(k>=0)
Hint:-
A) arr[i]+arr[j] = k EXAMPLE:-
0 1 2 3 4 ← Index.
1 0 1 2 5 4
k=3.
Output :- 2 → (1 to 3 index) and (2 to 3 index) so total subarray are 2.
Hint:- a) take prefix sum , check how much value is remaining if that remain
value is present inside the map , count += freq.
In map keep prefix sum and freq(how many times same sum
came)
//count number of subarray with sum == targetSum
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
int main(){
vector<int>v;
int n ;
cout<<"enter the size of the array:-";
cin>>n;
cout<<"enter the element of the array:-";
for(int i=0;i<n;i++){
int q;
cin>>q;
v.push_back(q);
}//1 5 3 2 4
int targetSum;
cout<<"enter the value of K:-";
cin>>targetSum;
unordered_map<int,int>mp;//unordered_map, it will store all the prefix
sum values with freq.
int curr_sum=0;
int count = 0;
for(int i=0;i<n;i++){
curr_sum += v[i];
int remain = curr_sum- targetSum;
if(curr_sum == targetSum) count++;
if(mp.find(remain) != mp.end()){
count += mp[remain];
}
else{ // remain is not present in map,push the current sum & its
frequency.
mp[curr_sum]++;
}
cout<<"total subarray are:-"<<count;
}
Output:-enter the size of the array:-6
enter the element of the array:-1 0 1 2 10 5
enter the value of K:-3
total subarray are:-2
Output:- enter the size of the array:-3
enter the element of the array:-1 1 1
enter the value of K:-2
total subarray are:-2
Zscaler OA Ques
Q.
Code:-
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n;
cout<<"enter the size of the array:-";
cin>>n;
vector<int>arr(n);
cout<<"enter the values of Heights:-";
for(int i=0;i<n;i++){
int q;
cin>>q;
arr[i]=q;
}
sort(arr.begin(),arr.end());
int i =arr.size()-1;
int count=0;
while(i>=1){
i=n-1;
while((i != 0) && (arr[i]==arr[i-1])){
i--;
}
int l = arr[i];
int sl = arr[i-1];
int diff = l-sl;
arr[i]-=diff;
count++;
}
cout<<"the minimum number of steps:-"<<count-1;
return 0;
}
Output1:- enter the size of the array:-5
enter the values of Heights:-4 5 5 4 2
the minimum number of steps:-6
Output2 :- enter the size of the array:-2
enter the values of Heights:-886 777
the minimum number of steps:-1
Output3:- enter the size of the array:-3
enter the values of Heights:-5 2 1
the minimum number of steps:-3
Hashing prefix sum lect:-14
Qus1. GFG PROBLEM
Max distance between same elements
Input: arr[] = [1, 1, 2, 2, 2, 1]
Output: 5
Explanation: distance for 1 is: 5-0 = 5, distance for 2 is : 4-2 = 2, So
max distance is 5.
Method 1:-
//Brute force method TC:- O(N2)
int n = arr.size();
int max_dis = 0;
int curr_dis = 0;
for(int i=0;i<n-1;i++){
for(int j=i; j<n ; j++){
if(arr[i] == arr[j]){
curr_dis = j-i;
max_dis = max(max_dis,curr_dis);
}
}
}
return max_dis;
METHOD2:-
HINT:-
a)Put two pointer at start and at end then check & find dis
then store into variable
//Method 2
int n = arr.size();
int max_dis = 0;
int curr_dis = 0;
int low = 0;
int high = n-1;
while(low<high){
while((arr[low] != arr[high])) high--;
curr_dis = high-low;
max_dis = max(curr_dis,max_dis);
while( low<=high && arr[low]==arr[low+1] ) low++;
low++;
high=n-1;
}
return max_dis;
METHOD3:-
HINT:-
a)Take hashmap and store the first occurrence of element with
its index.
b)If same element comes again then first check it is present in
map or not , if yes then get diff between their index , update the
max dis variable.
Code:-
//method3 T.C:- O(N)
unordered_map<int, int> first_occurrence; // Stores first index of elements
int max_dis = 0;
for (int i = 0; i < arr.size(); i++) {
if (first_occurrence.find(arr[i]) == first_occurrence.end()) {
first_occurrence[arr[i]] = i; // Store first occurrence
} else {
max_dis = max(max_dis, i - first_occurrence[arr[i]]);
}
}
return max_dis;
Qus2. LEETCODE PROBLEM 387
387. First Unique Character in a String
Given a string s, find the first non-repeating character in it and return its index. If
it does not exist, return -1.
Example 1: Input: s = "leetcode"
Output: 0
Explanation: The character 'l' at index 0 is the first character that does not occur
at any other index.
HINT:- a) Iterate each element of given string, You can use map to store the
character and its frequency .
b) Iterate on map, catch the element, check firstly whether the frequency is 1
or not, if 1 then find its index in the original string. Store its index in
min_idx variable if and only if the new index is lower than the previous
stored index.
CODE:-
int firstUniqChar(string s) {
int n = s.size();
unordered_map<char,int>mp;//charcter,freq.
for(int i=0;i<n;i++){
mp[s[i]]++;
int min_idx = INT_MAX;
bool flag = false;
for(auto ele : mp){
char val = ele.first;
if(ele.second == 1){
flag = true;
for(int i=0;i<n;i++){
if(s[i] == val){
min_idx = min(min_idx,i);
break;
if(flag == false) return -1;
return min_idx;
Qus3. LEETCODE PROBLEM 1002 ( VVI )
1002. Find Common Characters
Given a string array words, return an array of all characters that show up in all strings
within the words (including duplicates). You may return the answer in any order.
Example 1: Input: words = ["belle","label","roller"]
Output: ["e","l","l"]
Example 2: Input: words = ["cool","lock","cook"]
Output: ["c","o"]
HINT:-
a) Iterate in on element of words array ,count the frequency of
letters , replace the frequency if you get smaller freq.
CODE:-
vector<string> commonChars(vector<string>& words) {
vector<int>min_freq(26,INT_MAX);
for(int i=0;i<words.size();i++){
vector<int>freq(26,0);
string s = words[i];
for(int j=0;j<s.size();j++){
int idx = int(s[j])-97;
freq[idx]++;
}
for(int k=0;k<26;k++){
min_freq[k]=min(min_freq[k],freq[k]);
}
vector<string>result;
for(int i=0;i<26;i++){
int freq = min_freq[i];
if(freq != 0){
while(freq > 0){
char val = char(i+97);
//convert char into string then push into the array result.
result.push_back(string(1, val));
freq--;
}
}
}
return result;
}
Hashing prefix sum lect:-16
Q1. Longest Consecutive Sequence [LEETCODE:-128]
Given an unsorted array of integers nums, return the length of the
longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Example 1: Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4].
Therefore its length is 4.
Example 2: Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Example 3:Input: nums = [1,0,1,2]
Output: 3
Hint:- a) Take a ordered set to store the unique values , then put all the
values into new array.
b) Iterate on each value & check prev value + 1 == curr value or not
If yes count++.
OUTPUT:-
int longestConsecutive(vector<int>& nums) {
int n = nums.size();
if(n == 0) return 0;
set<int>s;//value single times always
for(int i=0;i<n;i++){
s.insert(nums[i]);
}
vector<int>result;
for(auto e : s){
result.push_back(e);
}
if(s.size() == 1) return 1;
int count = 1;
int longest_count = 1;
for(int i=1;i<result.size();i++){
if(result[i-1]+1 == result[i]){
count++;
longest_count = max(longest_count,count);
}
else count=1;
}
return longest_count;
}
Hashing prefix sum lect:-17
Ques. Count Number of Pairs With Absolute Difference K [leetcode 2006]
Given an integer array nums and an integer k, return the
number of pairs (i, j) where i < j such that |nums[i] - nums[j]| ==
k.
Example 1: Input: nums = [1,2,2,1], k = 1
Output: 4
Method 1: Brute force method T.C:- O(N2)
Code:-
int countKDifference(vector<int>& nums, int k) {
int count = 0;
for(int i=0;i<nums.size()-1;i++){
for(int j=i+1;j<nums.size();j++){
if(abs(nums[i]-nums[j]) == k) count++;
}
}
return count;
}
Method 2:-
Hint :-
|nums[i] - nums[j]| == k. Or nums[i]-nums[j] =|k|
Therefor nums[i]-nums[j] = +-k;
nums[i] = nums[j]+k & nums[j]-k
a)Iterate on each value of array, find above value and search either of
both or individual ,it is present in map or not , if present take their freq
and add in count variable . then put that value of array in map also
Code:-
int countKDifference(vector<int>& nums, int k) {
int count = 0;
unordered_map<int,int>mp;//val,freq
for(int i=0;i<nums.size();i++){
count += mp[nums[i]+k] + mp[nums[i]-k];
mp[nums[i]]++;
}
return count;
}
Hashing prefix sum lect:-18
Ques1. Subarrays with sum K
Given an unsorted array of integers, find the number of subarrays
having sum exactly equal to a given number k.
Input: arr = [10, 2, -2, -20, 10], k = -10
Output: 3
Explaination: Subarrays: arr[0...3], arr[1...4], arr[3...4] have sum exactly
equal to -10.
Code:- Use hash map and prefix sum technique.
int countSubarrays(vector<int> &arr, int k) {
// code here
unordered_map<int,int>mp;
int count=0;
int curr_sum=0;
int n = arr.size();
for(int i=0;i<n;i++){
curr_sum += arr[i];
if(curr_sum == k)count++;
int rem = curr_sum - k;
if(mp.find(rem) != mp.end()){
count += mp[rem];
}
mp[curr_sum]++;
}
return count;
}
Ques2. Count Subarrays with given XOR
Given an array of integers arr[] and a number k, count the number of
subarrays having XOR of their elements as k.
Examples:
Input: arr[] = [4, 2, 2, 6, 4], k = 6
Output: 4
Explanation: The subarrays having XOR of their elements as 6 are [4, 2],
[4, 2, 2, 6, 4], [2, 2, 6], and [6]. Hence, the answer is 4.
Hint:- a) use XOR(^) properties.
i) 0 XOR A = A [A is any value]
ii) A XOR A = 0 , A XOR B = 1
iii) ? XOR A = B then => ? = B XOR A
EX:- ? XOR 1 = 0 => ? = 0 XOR 1 = 0.
Use the same above code and approach to deal with this good Question
CODE:-
Hashing prefix sum lect:-20
Ques. Longest Palindrome by Concatenating Two Letter Words [2131]
HINT:- a) palindrome which is equal from start and end. mirror image from middle.
EX:- ABBA , 121 , 1001 etc
b) palindrome will be formed by concatenation by following 2 rules.
i) let string 1 you have then concatenating string will be reverse of string 1.
EX:- string1:- AC therefore concatenating string will CA.
The Resulting string will be palindrome AC+CA :- ACCA.
ii) If any words is same itself after reverse like ww,xx,aa then in palindrome this
type of words will only exist 1 time. If you will add more times of different above
like words then palindromes will not form.
EX :- ACCA + WW :- ACWWCA ← Palindrome
Let ACWWCA + XX :- ACWWXXCA ← Not a Palindrome
CODE HINT :- a) take a map which will store every string , take a loop on array and find i
Its reverse is existing in map or not , if found then increase length
b) ww,xx,aa this types of words find with different loop , if found add and
increase length and break loop.
CODE:-
Hashing prefix sum lect:-19
Ques2. Find the Prefix Common Array of Two Arrays
Link : - Ques
EX:- A = [1,3,2,4], B = [3,1,2,4]
i i
OUTPUT :- [0,2,3,4]
Initial count = 0; unordered_map<int,int>mp_A & unordered_map<int,int>mp_B
Hint :- a) At same time , take a loop on the both array, traverse each element
,check A[i] is common in B Array before index i or not , If present count++,
same time check B[i] is present in an A array before index i or not ,if present
count++.
But if not present or present at both cases ,put that element in their respective
unordered_map
Then at the end after updating, put the count value in the result array.
then i++ check similar for next element
Code:-
Hashing prefix sum lect:-21
Ques. microsoft:- Link :- Ques
Given an array A consisting of N integers, returns the maximum sum of two numbers
whose digits add up to an equal sum.
if there are not two numbers whose digits have an equal sum, the function should return
-1.
Constraints: N is integer within the range [1, 200000]
each element of array A is an integer within the range [1, 1000000000]
Example1:
Input: A = [51, 71, 17, 42]
Output: 93
Explanation: There are two pairs of numbers whose digits add up to an equal sum: (51,
42) and (17, 71), The first pair sums up to 93
Method1:- //Brute force method. TC:- O(n2)
Method2:- optimised solution T.C:- O(n)
HINT:- a) Use hashmap to store array element’s digits sum , that element also.
b) if digits sum is equal with some other element digits sum of array ,
which is present inside the map , then we will check firstly stored ele
is greater then current element or not if current ele is greater on which
you are currently present . if current ele greater then remove already
present element and put current ele on which your index is present.
Because we need greatest Sum .
CODE:-
Hashing prefix sum lect:-22
Ques. Amazon OA
Ques. link ;- click
Code:-
HINT :- a) take all char of string s into unordered hash_map with its frequency.
b) take another loop and check all character of t is existing in map or not
If not present even a single character of t , then break a loop and return false.
If present all the character, then store the min freq of character among all
character of t in map, lastly return it.
Hashing prefix sum lect:-23
Ques . Amazon asked OA link:- click
Hint :-a) Use hashmap to store every value with their frequency .
b) Traverse on the map for every element, take freq & first divide it by 3 and
check is it possible to deliver the items 3 at a time, if possible then how
many times delivery action this product takes. Then reduce their freq from
map (only if it is possible to deliver).
If not possible to deliver 3 product at a time then check is it possible to
deliver 2 items at a time or not , and how many times it will take to deliver.
Then reduce their freq from map (only if it is possible to deliver).
c) Lastly check which item has remained freq equal to 1(means product not
delivered). Then return -1.
CODE:-
Hashing prefix sum lect:-25
Ques:- Visa intern OA liNK - click [VVVVI]
Ans :-
Hint :- Brute Force method, T.C:- O(n*m) , n = points array size , m = lamp array size
a) Take a loop on points array and check every elements of points array, lie inside
the Lamp array or not simple.
Code:-
