DEPARTMENT OF

COMPUTER SCIENCE & ENGINEERING

Slow Learner Lab Assignment

Student Name: Ansuman Roul UID: 22BCS10231

Section: 606/A Semester: 05
Branch: BE-CSE Date of Submission: 21 Oct
Subject Name: AP Lab-1 Subject Code: 22CSP-314

Problem 1: Trapping Rainwater Problem

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

int trap(vector<int>& height) {

int left = 0, right = height.size() - 1;
int maxLeft = 0, maxRight = 0, water = 0;

while (left <= right) {

if (height[left] <= height[right]) {
if (height[left] >= maxLeft)
maxLeft = height[left];
else
water += maxLeft - height[left];
left++;
} else {
if (height[right] >= maxRight)
maxRight = height[right];
else
water += maxRight - height[right];
right--;
}
}
return water;
}

int main() {
vector<int> height = {7, 0, 4, 2, 5, 0, 6, 4, 0, 5};
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
cout << "Maximum water that can be trapped: " << trap(height) << endl;
return 0;
}

Input:
vector<int> height = {7, 0, 4, 2, 5, 0, 6, 4, 0, 5};
Output:
Maximum water that can be trapped: 25

Time Complexity:
• O(n), where n is the number of bars (heights).
The algorithm makes a single pass from both sides of the array, which
gives linear complexity.
Space Complexity:
• O(1), as we are using only a few variables (left, right, maxLeft,
maxRight, water) apart from the input array.

Problem2: Maximum Possible Minimum Power of a City

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

bool isPossible(vector<int>& stations, int r, int k, int minPower) {

int n = stations.size();
vector<int> power(n, 0);
int usedStations = 0;

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

power[i] = stations[i];
if (i > 0) power[i] += power[i - 1];
if (i >= 2 * r + 1) power[i] -= stations[i - (2 * r + 1)];

if (power[i] < minPower) {

int addStations = minPower - power[i];
if (addStations > k) return false;
k -= addStations;
}
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

return true;
}

int maxPowerCity(vector<int>& stations, int r, int k) {

int low = 0, high = 1e9;
while (low < high) {
int mid = (low + high + 1) / 2;
if (isPossible(stations, r, k, mid)) low = mid;
else high = mid - 1;
}
return low;
}

int main() {
vector<int> stations = {1, 2, 4, 5, 0};
int r = 1, k = 2;
cout << "Maximum possible minimum power: " << maxPowerCity(stations,
r, k) << endl;
return 0;
}

Input:
vector<int> stations = {1, 2, 4, 5, 0};
int r = 1, k = 2;
Output:
Maximum possible minimum power: 5

Time Complexity:
• O(n * log(maxPower)), where n is the number of cities.
For each binary search step (log(maxPower)), we iterate over the n cities
to check if placing power stations is feasible.
Space Complexity:
• O(n), as we store additional arrays for tracking power and any
modifications during the feasibility check.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Problem 3: Minimum Score to Make t a Subsequence of s

Solution:
#include <iostream>
#include <string>
using namespace std;

int minScoreToSubsequence(string s, string t) {

int left = 0, right = t.size() - 1;
while (left <= right && s.find(t.substr(left, right - left + 1)) == string::npos) {
if (s.find(t.substr(left + 1, right - left)) != string::npos)
left++;
else
right--;
}
return right - left + 1;
}

int main() {
string s = "abacaba", t = "bzaa";
cout << "Minimum possible score: " << minScoreToSubsequence(s, t) <<
endl;
return 0;
}

Input:
string s = "abacaba";
string t = "bzaa";
Output:
Minimum possible score: 1

Time Complexity:
• O(n + m), where n is the length of string s and m is the length of string t.
We are scanning through both strings, making it linear with respect to
their combined lengths.
Space Complexity:
• O(1), since only a few variables are used (left, right), and no extra arrays
or data structures are needed.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Problem 4: Flip, Modify and Query Arrays

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

void processQueries(vector<int>& nums1, vector<int>& nums2,

vector<vector<int>>& queries) {
for (auto& query : queries) {
if (query[0] == 1) {
for (int i = query[1]; i <= query[2]; i++) {
nums1[i] = 1 - nums1[i];
}
} else if (query[0] == 2) {
for (int i = 0; i < nums2.size(); i++) {
nums2[i] += nums1[i] * query[1];
}
} else if (query[0] == 3) {
int sum = 0;
for (int num : nums2) sum += num;
cout << sum << endl;
}
}
}

int main() {
vector<int> nums1 = {1, 0, 1};
vector<int> nums2 = {0, 0, 0};
vector<vector<int>> queries = {{1, 1, 1}, {2, 1, 0}, {3, 0, 0}};
processQueries(nums1, nums2, queries);
return 0;
}

Input:
vector<int> nums1 = {1, 0, 1};
vector<int> nums2 = {0, 0, 0};
vector<vector<int>> queries = {{1, 1, 1}, {2, 1, 0}, {3, 0, 0}};
Output:
3
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Time Complexity:
• For type 1 queries (flip operation): O(r - l), where l and r are indices for
flipping the values.
• For type 2 queries (modify array): O(n), where n is the length of the
arrays nums1 and nums2.
• For type 3 queries (sum query): O(n), since it involves summing up all
elements of nums2.
• Overall complexity depends on the number of queries, worst case would
be O(q * n), where q is the number of queries and n is the length of the
arrays.
Space Complexity:
• O(n), where n is the size of the nums1 and nums2 arrays.

Problem 5: Fixed-Bound Subarrays

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

int countFixedBoundSubarrays(vector<int>& nums, int minK, int maxK) {

int count = 0, start = 0, minPos = -1, maxPos = -1;

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

if (nums[i] < minK || nums[i] > maxK) {
start = i + 1;
minPos = maxPos = -1;
}
if (nums[i] == minK) minPos = i;
if (nums[i] == maxK) maxPos = i;

if (minPos != -1 && maxPos != -1)

count += max(0, min(minPos, maxPos) - start + 1);
}
return count;
}

int main() {
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

vector<int> nums = {1, 3, 5, 2, 7, 5};

int minK = 1, maxK = 5;
cout << "Number of fixed-bound subarrays: " <<
countFixedBoundSubarrays(nums, minK, maxK) << endl;
return 0;
}

Input:
vector<int> nums = {1, 3, 5, 2, 7, 5};
int minK = 1, maxK = 5;
Output:
Number of fixed-bound subarrays: 2

Time Complexity:
• O(n), where n is the number of elements in the nums array.
We scan through the array once, keeping track of the positions of minK
and maxK.
Space Complexity:
• O(1), since we use only a few variables to store positions and counts

Problem 6: Largest Rectangle in Histogram

Solution:
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int largestRectangleArea(vector<int>& heights) {

stack<int> s;
int maxArea = 0, i = 0;

while (i < heights.size()) {

if (s.empty() || heights[i] >= heights[s.top()]) {
s.push(i++);
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

} else {
int h = heights[s.top()];
s.pop();
int width = s.empty() ? i : i - s.top() - 1;
maxArea = max(maxArea, h * width);
}
}
while (!s.empty()) {
int h = heights[s.top()];
s.pop();
int width = s.empty() ? i : i - s.top() - 1;
maxArea = max(maxArea, h * width);
}
return maxArea;
}

int main() {
vector<int> heights = {2, 1, 5, 6, 2, 3};
cout << "Largest rectangle area: " << largestRectangleArea(heights) << endl;
return 0;
}

Input:
vector<int> heights = {2, 1, 5, 6, 2, 3};
Output:
Largest rectangle area: 10

Time Complexity:
• O(n), where n is the number of bars (heights).
Each bar is pushed and popped from the stack at most once, so the overall
complexity is linear.
Space Complexity:
• O(n), where n is the number of bars. The stack can grow up to the size of
the input array.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Problem 7: Maximum Path Sum in a Binary Tree

Solution: #include <iostream>
#include <climits>
using namespace std;

struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int maxPathSum(TreeNode* root, int& maxSum) {

if (!root) return 0;

int left = max(0, maxPathSum(root->left, maxSum));

int right = max(0, maxPathSum(root->right, maxSum));

maxSum = max(maxSum, left + right + root->val);

return root->val + max(left, right);

}

int getMaxPathSum(TreeNode* root) {

int maxSum = INT_MIN;
maxPathSum(root, maxSum);
return maxSum;
}

int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
cout << "Maximum path sum: " << getMaxPathSum(root) << endl;
return 0;
}

Input:
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Output:
Maximum path sum: 6

Time Complexity:
• O(n), where n is the number of nodes in the tree.
Each node is visited once to compute the maximum path sum.
Space Complexity:
• O(h), where h is the height of the tree.
This is due to the recursion stack, and in the worst case (a skewed tree), h
can be equal to n.

Problem 8: Maximum Profit with k Transactions

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

int maxProfit(int k, vector<int>& prices) {

if (prices.empty()) return 0;
vector<int> buy(k + 1, INT_MIN), sell(k + 1, 0);

for (int price : prices) {

for (int i = 1; i <= k; i++) {
buy[i] = max(buy[i], sell[i - 1] - price);
sell[i] = max(sell[i], buy[i] + price);
}
}
return sell[k];
}

int main() {
vector<int> prices = {3, 2, 6, 5, 0, 3};
int k = 2;
cout << "Maximum profit: " << maxProfit(k, prices) << endl;
return 0;
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING

Input:
vector<int> prices = {3, 2, 6, 5, 0, 3};
int k = 2;
Output:
Maximum profit: 7

Time Complexity:
• O(k * n), where k is the number of transactions and n is the number of
days.
We update the buy and sell arrays for each day and each transaction.
Space Complexity:
• O(k), as we are using two arrays of size k (one for buy and one for sell).