DEPARTMENT OF

COMPUTER SCIENCE & ENGINEERING

Complex Problems
Student Name: Akhanda Pal Biswas UID: 21BCS5828
Branch: CSE Section/Group: KRG_CC_2(A)
th
Semester: 06 Date of Performance:02/04/2024
Subject Name: Advance Programming Lab-II Subject Code: 21CSP-351

1. Aim: To solve complex problems of advanced programming.

2. Objective: To solve questions related to advanced programming on

variousprogramming concepts like Array, Graphs, Dynamic Programming
etc.

3. Code and Output:

Question 1

Given two strings S and P where S consists of only lowercase English

alphabets while P consists of lowercase English alphabets as well as special
characters ‘.’ and ‘*’, the task is to implement a function to test regular
expressions such that: '.' Matches any single character. '*' Matches zero or
more of the preceding elements. Note: For each appearance of the character
‘*', there will be a previous valid character to match. Examples: Input: s =
"aaa", p = "a" Output: false Explanation: "a" does not match the entire string
"aaa".

Code:

#include <iostream>
#include <vector>
using namespace std;

bool isMatch(string s, string p) {

int m = s.size(), n = p.size();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[0][0] = true;

for (int j = 1; j <= n; ++j) {

if (p[j - 1] == '*') {
dp[0][j] = dp[0][j - 2];
}
}

for (int i = 1; i <= m; ++i) {

for (int j = 1; j <= n; ++j) {
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
dp[i][j] = dp[i - 1][j - 1];
} else if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 2];
if (p[j - 2] == '.' || p[j - 2] == s[i - 1]) {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
} else {
dp[i][j] = false;}}}
return dp[m][n];}
int main() {
string s, p;
// cout << "Enter string s: ";
cin >> s;
// cout << "Enter pattern p: ";
cin >> p;

cout << boolalpha << isMatch(s, p) << endl;

return 0;
}

Output:

Question 2
Serialization is the process of converting a data structure or object into a
sequence of bits so that it can be stored in a file or memory buffer, or
transmitted across a network connection link to be reconstructed later in the
same or another computer environment. Design an algorithm to serialize and
deserialize a binary tree. There is no restriction on how your
serialization/deserialization algorithm should work. You just need to ensure
that a binary tree can be serialized to a string and this string can be
deserialized to the original tree structure. Clarification: The input/output
format is the same as how LeetCode serializes a binary tree. You do not
necessarily need to follow this format, so please be creative and come up
with different approaches yourself.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Code:
#include <iostream>
#include <sstream>
#include <string>
#include <queue>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (!root)
return "null";
return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
stringstream ss(data);
queue<string> nodes;
string str;
while (getline(ss, str, ','))
nodes.push(str);
return buildTree(nodes);
}
private:
TreeNode* buildTree(queue<string>& nodes) {
string val = nodes.front();
nodes.pop();

if (val == "null")
return nullptr;

TreeNode* root = new TreeNode(stoi(val));

root->left = buildTree(nodes);
root->right = buildTree(nodes);
return root;}};
// Helper function to print the binary tree (for testing purposes)
void printTree(TreeNode* root) {
if (!root)
return;
cout << root->val << " ";
printTree(root->left);
printTree(root->right);
}

int main() {
// Example usage
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
root->right = new TreeNode(3);
root->right->left = new TreeNode(4);
root->right->right = new TreeNode(5);
Codec codec;
string serialized = codec.serialize(root);
cout << "Serialized tree: " << serialized << endl;
TreeNode* deserialized = codec.deserialize(serialized);
cout << "Deserialized tree: ";
printTree(deserialized);
cout << endl;

return 0;
}

Output:

Question 3

Given an MxN matrix where each element can either be 0 or 1. Weneed to

find the shortest path between a given source cell to a destination cell. The
path can only be created out of a cell if its value is 1.

Code:
#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <climits>

using namespace std;

// Define directions: up, down, left, right

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

// Structure to represent a cell in the matrix

struct Cell {
int x, y;
Cell(int _x, int _y) : x(_x), y(_y) {}
};

// Function to check if a cell is valid (inside the matrix)

bool isValid(int x, int y, int rows, int cols) {
return (x >= 0 && x < rows && y >= 0 && y < cols);}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
// Function to find the shortest path using BFS
int shortestPath(vector<vector<int>>& grid, Cell src, Cell dest) {
int rows = grid.size();
int cols = grid[0].size();

// Initialize a queue for BFS

queue<Cell> q;

// Mark the source cell as visited and enqueue it

vector<vector<bool>> visited(rows, vector<bool>(cols, false));
visited[src.x][src.y] = true;
q.push(src);

// Initialize distance of source cell to 0

vector<vector<int>> distance(rows, vector<int>(cols, 0));

// BFS
while (!q.empty()) {
Cell current = q.front();
q.pop();

// If the current cell is the destination, return its distance

if (current.x == dest.x && current.y == dest.y)
return distance[current.x][current.y];

// Explore all 4 adjacent cells

for (int i = 0; i < 4; ++i) {
int newX = current.x + dx[i];
int newY = current.y + dy[i];

// If the new cell is valid and can be visited

if (isValid(newX, newY, rows, cols) && grid[newX][newY] == 1 &&
!visited[newX][newY]) {
// Mark the new cell as visited
visited[newX][newY] = true;
// Update the distance of the new cell
distance[newX][newY] = distance[current.x][current.y] + 1;
// Enqueue the new cell
q.push(Cell(newX, newY));}}}
// If destination cannot be reached
return INT_MAX;
}
int main() {
// Example usage
vector<vector<int>> grid = {
{1, 0, 1, 1, 1},
{1, 0, 1, 0, 1},
{1, 1, 1, 0, 1}
};
Cell src(0, 0);
Cell dest(2, 4);
int shortest = shortestPath(grid, src, dest);
if (shortest != INT_MAX)
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
cout << "Shortest path length: " << shortest << endl;
else
cout << "Destination is not reachable from source." << endl;

return 0;
}
Output:

Question 4

Given an array arr[] of size N, the task is to find the length of the Longest
Increasing Subsequence (LIS) i.e., the longest possible subsequence in
which the elements of the subsequence are sorted in increasing order.
Examples: Input: arr[] = {3, 10, 2, 1, 20} Output: 3 Explanation: The longest
increasing subsequence is 3, 10, 20Given an arrayarr[] of size N, the task is
to find the length of the Longest Increasing Subsequence (LIS) i.e., the
longest possible subsequence in which the elements of the subsequence are
sorted in increasing order. Examples: Input: arr[] = {3, 10, 2, 1, 20} Output:
3 Explanation: The longest increasing
subsequence is 3, 10, 20.

Code:
#include <iostream>
#include <vector>

using namespace std;

int longestIncreasingSubsequence(vector<int>& arr) {

int n = arr.size();
if (n == 0)
return 0;

// Initialize an array to store the length of LIS ending at each index

vector<int> lis(n, 1);
// Iterate over the array to find the length of LIS ending at each index
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
lis[i] = lis[j] + 1;
}
}
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
// Find the maximum length of LIS
int maxLength = 1;
for (int i = 0; i < n; ++i) {
maxLength = max(maxLength, lis[i]);
}

return maxLength;
}

int main() {
vector<int> arr = {3, 10, 2, 1, 20};
cout << "Length of Longest Increasing Subsequence: " <<
longestIncreasingSubsequence(arr) << endl;
return 0;
}
Output:

Question 5

Given two strings, string, and pattern, the task is to find the smallest substring
in string containing all characters of pattern. Examples:Input: string = “this
is a test string”, pattern = “tist” Output: “t stri” Explanation: “t stri” contains
all the characters of pattern.
Input: string = “geeksforgeeks”, pattern = “ork”
Output: “ksfor”Given two strings, string, and pattern, the task is to findthe
smallest substring in string containing all characters of pattern.

Code:
#include <iostream>
#include <string>
#include <unordered_map>
#include <climits>

using namespace std;

string smallestSubstring(const string& str, const string& pattern) {

unordered_map<char, int> patternMap, windowMap;
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
for (char c : pattern) {
patternMap[c]++;
}
int left = 0, right = 0;
int minLength = INT_MAX;
int startIdx = -1;
int count = 0;

while (right < str.length()) {

char currentChar = str[right];
windowMap[currentChar]++;

if (patternMap.find(currentChar) != patternMap.end() &&

windowMap[currentChar] <= patternMap[currentChar]) {
count++;
}

while (count == pattern.length()) {

if (windowMap[str[left]] > patternMap[str[left]] || patternMap.find(str[left])
== patternMap.end()) {
windowMap[str[left]]--;
left++;
} else {
int currentLength = right - left + 1;
if (currentLength < minLength) {
minLength = currentLength;
startIdx = left;
}
windowMap[str[left]]--;
left++;
count--;}}
right++;
}

if (startIdx == -1) {
return ""; // No substring containing all characters of the pattern found
} else {
return str.substr(startIdx, minLength);}}
int main() {
string str1 = "this is a test string";
string pattern1 = "tist";
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
cout << "Smallest substring containing all characters of pattern: "
<< smallestSubstring(str1, pattern1) << endl;
string str2 = "geeksforgeeks";
string pattern2 = "ork";
cout << "Smallest substring containing all characters of pattern: "
<< smallestSubstring(str2, pattern2) << endl;

return 0;
}

Output:

Question 6

Given an array arr[] of size N and an integer K. Find themaximum for

every contiguous subarray of size K.

Code:
#include <iostream>

#include <vector>

#include <deque>

using namespace std;

vector<int> maxOfSubarrays(const vector<int>& arr, int k) {

vector<int> result;

deque<int> dq;

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

while (!dq.empty() && arr[i] >= arr[dq.back()]) {

dq.pop_back();

dq.push_back(i);

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

DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

result.push_back(arr[dq.front()]);

while (!dq.empty() && dq.front() <= i - k) {

dq.pop_front();

while (!dq.empty() && arr[i] >= arr[dq.back()]) {

dq.pop_back();

dq.push_back(i);

result.push_back(arr[dq.front()]);

return result;

int main() {

vector<int> arr = {1, 2, 3, 1, 4, 5, 2, 3, 6};

int k = 3;

vector<int> result = maxOfSubarrays(arr, k);

cout << "Maximum of each subarray of size " << k << ":\n";

for (int num : result) {

cout << num << " ";

cout << endl;

return 0;

Output:
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Question 7:
Given a Binary Tree with all unique values and two node values, n1 and
n2. The task is to find the lowest common ancestor of the given two
nodes. We may assume that either both n1 and n2 are present in the tree
or none of them are present. LCA: It is the first common ancestor of both
the nodes n1 and n2 from the bottom of the tree.

Code:
#include <iostream>

using namespace std;

// Definition for a binary tree node.

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

};

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

if (root == nullptr || root == p || root == q) {

return root;

TreeNode* leftLCA = lowestCommonAncestor(root->left, p, q);

TreeNode* rightLCA = lowestCommonAncestor(root->right, p, q);

if (leftLCA && rightLCA) {

return root;}

return (leftLCA != nullptr) ? leftLCA : rightLCA;

int main() { TreeNode* root = new TreeNode(3);

root->left = new TreeNode(6);

root->right = new TreeNode(8);

DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

root->left->left = new TreeNode(2);

root->left->right = new TreeNode(11);

root->left->right->left = new TreeNode(9);

root->left->right->right = new TreeNode(5);

root->right->right = new TreeNode(13);

root->right->right->left = new TreeNode(7);

TreeNode* n1 = root->left->left; // Node with value 2

TreeNode* n2 = root->left->right->right; // Node with value 5

TreeNode* lca = lowestCommonAncestor(root, n1, n2);

if (lca != nullptr) {

cout << "Lowest Common Ancestor of " << n1->val << " and " << n2->val <<
" is: " << lca->val << endl;

} else {

cout << "One or both of the nodes are not present in the tree." << endl;}}

Output:

Question 8:
Given an array of points [i][j] of size N, where points[i] represents a
balloon over the area of X-coordinates from points[i][0] to points[i][1].
The Y-coordinates don’t matter. All the balloons are required to be burst.
To burst a balloon, an arrow can be launched at point (x, 0) and it travels
vertically upwards and bursts all the balloons which satisfy the condition
points[i][0] <= x <= points[i][1]. The task is to find the minimum number
of arrows required to burst all the balloons.

Code:
#include <iostream>

#include <vector>

#include <algorithm>
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

using namespace std;

int findMinArrowShots(vector<vector<int>>& points) {

if (points.empty()) {

return 0;

sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {

return a[1] < b[1];

});

int arrows = 1;

int end = points[0][1];

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

if (points[i][0] > end) {

arrows++;

end = points[i][1];}}

return arrows;

int main() {

vector<vector<int>> balloons = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};

int minArrows = findMinArrowShots(balloons);

cout << minArrows << endl;

return 0;

Output:
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Question 9:
Given a sorted dictionary (array of words) of an alien language, find the
order of characters in the language. Examples: Input: words[] = {“baa”,
“abcd”, “abca”, “cab”, “cad”} Output: Order of characters is ‘b’, ‘d’, ‘a’,
‘c’.

Code:
#include <iostream>

#include <vector>

#include <unordered_map>

#include <unordered_set>

#include <queue>

using namespace std;

void buildGraph(const vector<string>& words, unordered_map<char,

unordered_set<char>>& graph) {

for (const auto& word : words) {

for (char c : word) {

graph[c]; // Ensure the character exists in the graph

for (int i = 0; i < words.size() - 1; ++i) {

const string& word1 = words[i];

const string& word2 = words[i + 1];

int minLength = min(word1.size(), word2.size());

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

if (word1[j] != word2[j]) {

graph[word1[j]].insert(word2[j]);

break;}}}}

string alienOrder(const vector<string>& words) {

unordered_map<char, unordered_set<char>> graph;

buildGraph(words, graph);

unordered_map<char, int> inDegree;

DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

for (const auto& entry : graph) {

for (char neighbor : entry.second) {

inDegree[neighbor]++;}}

string result = "";

queue<char> q;

for (const auto& entry : graph) {

if (inDegree[entry.first] == 0) {

q.push(entry.first);}}

while (!q.empty()) {

char curr = q.front();

q.pop();

result += curr;

for (char neighbor : graph[curr]) {

inDegree[neighbor]--;

if (inDegree[neighbor] == 0) {

q.push(neighbor);}}} if (result.size() != graph.size()) {

return ""; // There is a cycle in the graph}

return result;

int main() {

vector<string> words = {"baa", "abcd", "abca", "cab", "cad"};

string order = alienOrder(words);

cout << "Order of characters is: " << order << endl;

return 0;}

Output:
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Question 10:
Given two strings str1 and str2 of length M and N respectively and below
operations that can be performed on str1. Find the minimum number of
edits (operations) to convert ‘str1‘into ‘str2‘. Operation 1 (INSERT):
Insert any character before or after any index of str1 Operation 2
(REMOVE): Remove a character of str1 Operation 3 (Replace): Replace
a character at any index of str1 with some other character. Note: All of
the above operations are of equal cost. Examples: Input: str1 = “geek”,
str2 = “geek” Output: 1 Explanation: We can convert str1 into str2 by
inserting a ‘s’ between two consecutive ‘e’ in str2. Input: str1 = “cat”,
str2 = “cut” Output: 1.

Code:
#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int minDistance(string str1, string str2) {

int m = str1.length();

int n = str2.length();

vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

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

dp[i][0] = i;

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

dp[0][j] = j;

// Fill DP table

for (int i = 1; i <= m; ++i) {

for (int j = 1; j <= n; ++j) {

if (str1[i - 1] == str2[j - 1]) {

dp[i][j] = dp[i - 1][j - 1];

} else {
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});}}}

return dp[m][n];

int main() {

string str1 = "geek";

string str2 = "geek";

cout << minDistance(str1, str2) << endl;

str1 = "cat";

str2 = "cut";

cout << minDistance(str1, str2) << endl;

return 0;

Output:

Learning Outcomes:
1. Learnt about complex problems.
2. Learnt about important concepts like Dynamic Programming,
Recursion etc.
3. Learnt about different Programming concepts.