DEPARTMENT OF

COMPUTER SCIENCE & ENGINEERING

Experiment - 1.1

Name : Saransh Jain

UID : 20BCS8284
Section : 713-A
Subject : Competitive Coding
Subject Code : 20CSP-351

Aim:
Understand the problem and find out better approach to solve
particular problem based on stack queue and arrays.

Question no.1: Implement Queue using

StackDescription:
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k,
and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Solution:
Algorithm:
1- Initialize the two stacks
2- On every put request put the new element in stack one
3- On every pop and peek request transfer all the element of stack1 to
stack2 except one element in case of peek return it
4- Then again transfer all the element back into the stack1 in case of
peek and in case of pop no include last element
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Code:
class MyQueue {
public:
stack<int> stk1,stk2;
MyQueue() {

void push(int x) {
stk1.push(x);
}

int pop() {
while(stk1.size()>1) stk2.push(stk1.top()),stk1.pop();
int ans=stk1.top();
stk1.pop();
while(!stk2.empty()) stk1.push(stk2.top()),stk2.pop();
return ans;
}

int peek() {
while(stk1.size()>1) stk2.push(stk1.top()),stk1.pop();
int ans=stk1.top();
while(!stk2.empty()) stk1.push(stk2.top()),stk2.pop();
return ans;
}

bool empty() {
return stk1.empty();
}
};

Question no.2- 3 Sum

Description:

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words,
if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and

• i+j<n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that
you can reach nums[n - 1].
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Solution:
Algorithm:
1- Sort the array.
2- Make a loop for fixing an element out of three.
3- Now for finding rest two element apply two pointers approach.
4- If some of all the elements are equal to 0 then add it to the answer.
Code:
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& number) {
sort(number.begin(),number.end());
set<vector<int>> ans;
for(int x=0;x<number.size()-1;x++){
if(x>0 && number[x]==number[x-1]) continue;
int i=x+1,j=number.size()-1;
int tar=-number[x];
while(i<j){
if(number[i]+number[j]<tar) i++;
else if(number[i]+number[j]>tar) j--;
else if(number[i]+number[j]==tar){
ans.insert({number[x],number[i],number[j]});
i++;
j--;
}
}
}
vector<vector<int>> result(ans.begin(),ans.end());
return result;
}
};

Question 3: Jump Game II

Description:
Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-
style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the
directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For
this problem, any other format of periods such as '...' are treated as file/directory names.

The canonical path should have the following format:

DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Solution:
Algorithm:
1-Make a dp array.
2 –Start from last index how much is it cost to jump
.3-Store minimum jump on each point.
4-Use stored value to find minimum at each point
.5- Return dp[0].
Code:
class Solution {
public:
int jump(vector<int>& game) {
int m=game.size();
vector<int> dp(m,INT_MAX);
dp[game.size()-1]=0;
for(int i=m-2;i>=0;i--){
int n=min(i+game[i],m-1);
for(int j=i;j<=n;j++) if(dp[j]!=INT_MAX) dp[i]=min(dp[i],dp[j]+1);
}
return dp[0];
}
};

Question 4- Simplify Path

Description:
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should
support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

Notes:
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

• The path starts with a single slash '/'.

• Any two directories are separated by a single slash '/'.
• The path does not end with a trailing '/'.
• The path only contains the directories on the path from the root directory to the target file or
directory (i.e., no period '.' or double period '..')

Return the simplified canonical path.

Solution:
Algorithm:
1- Start with an empty String
2- loop over the input string and add characters of it into the string
3- If you encounter any / then push string into the stack if it is not . or ..
4 - If string is equal to the .. then pop up stack one time in this case
6. add all the element of stack in a new string with an forword slash
that’s the answer
Code:
class Solution {
public:
string simplifyPath(string A) {
stack<string> stk;
string str;
for(int i=0;i<A.size();i++){
if(A[i]=='/'){
if(str.empty()) continue;
if(str==".."){
if(!stk.empty()) stk.pop();
}
if(str!="." && str!="..") stk.push(str);
str="";
}else str+=A[i];
}
if(!stk.empty() && str=="..") stk.pop();
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

else if(!str.empty() && str!=".." && str!=".") stk.push(str);

string ans;
vector<string> vec(stk.size());
int i=stk.size()-1;
while(!stk.empty()){
vec[i--]=stk.top();
stk.pop();
}
for(int i=0;i<vec.size();i++) ans+='/', ans+=vec[i];
return ans.empty()?"/":ans;
}
};

Question 5-Merge two sorted list

Description:
You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of
lists

Return the head of the merged linked list .

Solution:
Algorithm:
1- Start from head of both the list and make a new head of an list
2- Compare both of them list element adds smaller value list to the
newlist
3- And forward the pointer of small element
list

4- Repeat the process.

5 - If element of any list left add them to and return the answer.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Code:
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2){
if(!list1 && !list2) return list1;
if(!list1) return list2;
if(!list2) return list1;
vector<int> vec;
for(ListNode* it=list1;it;it=it->next){
vec.push_back(it->val);
}for(ListNode* it=list2;it;it=it->next){
vec.push_back(it->val);
}
sort(vec.begin(),vec.end());
ListNode* head=new ListNode(vec[0]);
ListNode* it=head;
for(int i=1;i<vec.size();i++){
it->next=new ListNode(vec[i]);
it=it->next;
}
return head;
}
};
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Question 6: Remove Duplicate from the list

Description:
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only
distinct numbers from the original list. Return the linked list sorted as well .

Solution:
Algorithm:
1- Iterate over the list.
2- If any element in the list is same as its next element than increment
the pointer until it reaches the value where it’s not equal to its previous.
3- join the pointer with the previous pointer where we started.
Code:
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* node=new ListNode(-101);
node->next=head;
ListNode* it=node;
while(it->next){
int val=it->next->val;
if(it->next->next && it->next->next->val==val){
while(it->next && it->next->val==val) it->next=it->next->next;
}else it=it->next;
}
return node->next;
}
};