New update is available. Click here to update.
About
A Bachelor of Technology in Electronics and Communication Engineering student at Punjab Engineering College, Chandigarh. Proficient in C++, Python, Data Structures, and Algorithms. I have four years ...
Punjab Engineering College (PEC) 2025
My Stats
EXP gained
8551
Level
6 (Specialist)
Community stats
Discussions
2
Upvotes
1
Know more
171
Total problems solved
101
Easy
66
Moderate
4
Hard
0
Ninja

Current streak:

0 days

Longest streak:

6 days

Less

More

Achievements
8
Ronin
Topics
Arrays
Stacks & Queues
Greedy
+ 5 more
Discussions
BFS Approach
Interview problems

#include<bits/stdc++.h>

int minTimeToRot(vector<vector<int>>& grid, int n, int m)

{

vector<pair<int,int>> help={{0,1},{1,0},{-1,0},{0,-1}};

queue<pair<pair<int,int>,int>> q;

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

for(int j=0;j<m;j++){

if(grid[i][j]==2){

q.push({{i,j},0});

}

}

}

vector<vector<int>> visited(n,vector<int>(m,0));

int ans=0;

while(!q.empty()){

pair<pair<int,int>,int> node=q.front();

q.pop();

int x=node.first.first;

int y=node.first.second;

// cout<<x<<" "<<y<<endl;

int time=node.second;

ans=time;

visited[x][y]=1;

int new_time=time+1;

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

int new_x=help[i].first+x;

int new_y=help[i].second+y;

if(new_x>=0 && new_y>=0 && new_x<n && new_y<m && grid[new_x][new_y]==1 && visited[new_x][new_y]!=1){

grid[new_x][new_y]=2;

pair<pair<int,int>,int> l={{new_x,new_y},new_time};

q.push(l);

}

if(new_x>=0 && new_y>=0 && new_x<n && new_y<m){

visited[new_x][new_y]=1;

}

}

}

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

for(int j=0;j<m;j++){

if(grid[i][j]==1){

return -1;

}

}

}

return ans;

// Write your code here.

}

Naman9102
Published On 26-Jul-2023
159 views
0 replies
0 upvotes
Simple Topological sort and DFS || C++ || Faster than 99%
Interview problems

#include<bits/stdc++.h>

void dfs(int node, vector<vector<int>> &adj, vector<bool> &visited, stack<int>&s){

visited[node]=true;

for(auto i : adj[node]){

if(!visited[i]){

dfs(i,adj,visited,s);

}

}

s.push(node);

}

int dfs3(int node, vector<vector<int>> &adjR, vector<bool> &visited){

visited[node]=true;

int k=1;

int ans=1;

for(auto i:adjR[node]){

if(!visited[i]){

k=k+1;

ans+=dfs3(i,adjR,visited);

}

}

return ans;

}

int countWays(int n, vector<vector<int>> &fruitIds)

{

vector<vector<int>> adj(n);

for(int i=0;i<fruitIds.size();i++){

int u=fruitIds[i][0];

int v=fruitIds[i][1];

adj[u].push_back(v);

adj[v].push_back(u);

}

vector<bool> visited(n);

stack<int> s;

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

if(!visited[i]){

dfs(i,adj,visited,s);

}

}

// REVERSE THE GRAPH TO FIND ALL THE SCC

vector<vector<int>> adjR(n);

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

visited[i]=false;

}

vector<int> arr; int num=0;

while(!s.empty()){

int node=s.top();

s.pop();

if(!visited[node]){

num=dfs3(node,adj,visited);

arr.push_back(num);

}

}

int sum=0;

int product=1;

sort(arr.begin(),arr.end());

for(int i=0;i<arr.size();i++){

for(int j=i+1;j<arr.size();j++){

product=arr[i]*arr[j];

sum+=product;

}

}

return sum;

// Write your code here.

}

Naman9102
Published On 24-Jul-2023
47 views
1 replies
1 upvotes
Optimized approach using two pointers
Interview problems

#include <bits/stdc++.h>

int twoSum(vector<int> arr,int l,int target){

int r=arr.size()-1;

int ans=0;

while(l<=r){

if(arr[l]+arr[r]<target){

ans+=(r-l);

l++;

r=arr.size()-1;

}

else{

r--;

}

}

return ans;

}

int threeSumSmaller(int n, vector<int> arr, int target) {

if(arr.size()<3){

return 0;

}

sort(arr.begin(),arr.end());

int ans=0;

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

// if(i!=0 && arr[i-1]==arr[i]){

//     continue;

// }

int num=target-arr[i];

ans+=twoSum(arr,i+1,num);

}

return ans;

// Write your code here.

}

Naman9102
Published On 11-Apr-2023
87 views
0 replies
0 upvotes
Simple DFS Approach || C++
Interview problems

#include <bits/stdc++.h>

int solve(int i, int j, int n, int m, vector<string> &grid, string &s, int p,vector<vector<int>>&visited) {

if(i<0|| j<0||i>n||j>m){

return 0;

}

// cout<<s[k];

if(p==s.size()-1 && grid[i][j]==s[p]){

visited[i][j]=-1;

return 1;

}

int ans=0;

visited[i][j]=0;

vector<pair<int,int>> help{{1,0},{0,1},{0,-1},{-1,0}};

for(int k=0;k<4;k++){

int new_i=i+help[k].first;

int new_j=j+help[k].second;

if(new_i>=0 && new_j>=0 && new_i<n && new_j<m && grid[new_i][new_j]==s[p+1]&&visited[new_i][new_j]!=0){

// cout<<grid[new_i][new_j]<<endl;

visited[new_i][new_j]=0;

ans+=solve(new_i,new_j,n,m,grid,s,p+1,visited);

}

}

visited[i][j]=-1;

return ans;

}

int countStrings(int n, int m, vector<string> &grid , string &s)

{

vector<vector<int>> visited(n);

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

for(int j=0;j<m;j++){

visited[i].push_back(-1);

}

}

int ans=0;

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

for(int j=0;j<m;j++){

if (grid[i][j] == s[0]) {

ans += solve(i, j, n, m, grid, s, 0,visited);

}

}

}

return ans;

// Write your code here

}

Naman9102
Published On 08-Jul-2023
80 views
1 replies
0 upvotes
NLogN Solution
Interview problems

#include <bits/stdc++.h>

vector<int> mergeKSortedArrays(vector<vector<int>>&kArrays, int k)

{

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

vector<pair<int,vector<int>>> help;

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

help.push_back({0, kArrays[i]});

pq.push({kArrays[i][0], i});

}

vector<int> ans;

while(!pq.empty()){

pair<int,int> temp=pq.top();

pq.pop();

int arrnum=temp.second;

ans.push_back(temp.first);

vector<int> temp1=kArrays[arrnum];

int index=help[arrnum].first+1;

if(index>=temp1.size()){

continue;

}

else{

help[arrnum]={index,temp1};

pq.push({temp1[index],arrnum});

}

}

return ans;

// Write your code here.

}

Naman9102
Published On 07-Jul-2023
253 views
0 replies
0 upvotes