Class Assignment
BM2043 - Algorithms and Data Structure Lab
September 13, 2024
Problem Statement 1: Merge Sort
Arin is analyzing a dataset where he needs to sort the data efficiently. To achieve this, he decides to use the
merge sort algorithm, which is known for its efficient sorting capabilities with a time complexity of O(n log n).
Given an integer array nums, help Arin implement the merge sort algorithm to sort the array in ascending
order.
Example 1:
• Input: nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
• Output: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
• Explanation: The array is sorted in ascending order.
Example 2:
• Input: nums = [12, 11, 13, 5, 6, 7]
• Output: [5, 6, 7, 11, 12, 13]
• Explanation: The array is sorted in ascending order.
Constraints:
• 1 ≤ [Link] ≤ 104
• −105 ≤ nums[i] ≤ 105
Your Task: You do not need to read input or print anything. Complete the function mergeSort which takes
an array of integers as input and sorts it in ascending order using the merge sort algorithm.
Class Definition:
class Solution {
public:
void mergeSort(vector<int>& nums) {
// Implement merge sort algorithm
mergeSortHelper(nums, 0, [Link]() - 1);
}
private:
void mergeSortHelper(vector<int>& nums, int left, int right) {
// Implement merge sort helper function
}
void merge(vector<int>& nums, int left, int mid, int right) {
// Implement merge function
}
};
1
Problem Statement 2: Two Sum
Yash is managing a store’s inventory system, where products have unique price tags arranged in ascending
order. A customer approaches him and asks for two products that add up to a specific amount. Yash has a list
of product prices and wants to quickly find the pair of products that exactly sum up to the target price.
Given a 1-indexed array of integers numbers representing the sorted prices of the products, help Yash find
the indices of the two products that add up to the target price. Return these indices in an array [index1, index2]
where 1 ≤ index1 < index2 ≤ [Link].
Example 1:
• Input: numbers = [2, 7, 11, 15], target = 9
• Output: [1, 2]
• Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:
• Input: numbers = [2, 3, 4], target = 6
• Output: [1, 3]
• Explanation: The sum of 2 and 4 is 6. Therefore, index1 = 1, index2 = 3. We return [1, 3].
Example 3:
• Input: numbers = [-1, 0], target = -1
• Output: [1, 2]
• Explanation: The sum of -1 and 0 is -1. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Constraints:
• 2 ≤ [Link] ≤ 3 × 104
• −1000 ≤ numbers[i] ≤ 1000
• numbers is sorted in non-decreasing order.
• −1000 ≤ target ≤ 1000
• The tests are generated such that there is exactly one solution.
Your Task: You do not need to read input or print anything. Complete the function twoSum which takes an
array of integers and a target integer as input parameters and returns the indices of the two numbers.
Class Definition:
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
// Implement logic to find the two numbers whose sum equals the target
}
};
Problem Statement 3
Ishan is working as a financial analyst, and he’s analyzing the stock market to identify the most lucrative series
of transactions. To do this, he needs to find the time period where the stock prices (represented as an array
of integers) multiplied together result in the highest product, which will help him identify the best buying and
selling strategy.
Given an integer array nums where each element represents the stock price change for a given day, help Ishan
find the subarray with the largest product and return the product.
2
Example 1:
• Input: nums = [2, 3, -2, 4]
• Output: 6
• Explanation: The subarray [2, 3] has the largest product of 6.
Example 2:
• Input: nums = [-2, 0, -1]
• Output: 0
• Explanation: The result cannot be 2, because [-2, -1] is not a contiguous subarray.
Constraints:
• 1 ≤ [Link] ≤ 2 × 104
• −10 ≤ nums[i] ≤ 10
• The product of any subarray of nums is guaranteed to fit in a 32-bit integer.
Your Task: You do not need to read input or print anything. Complete the function maxProduct which takes
an array of integers as input and returns the maximum product of any contiguous subarray.
Class Definition:
class Solution {
public:
int maxProduct(vector<int>& nums) {
// Implement logic to find the maximum product subarray
}
};
Problem Statement 4: (Binary Search On Search Space)
Pritesh is working on a signal processing algorithm where he needs to identify significant points of interest in
a dataset. Specifically, he wants to find the ”peak” elements in an array of signal values. A peak element is
defined as an element that is strictly greater than its immediate neighbors.
Given a 0-indexed integer array nums, help Pritesh find a peak element and return its index. If the array
contains multiple peaks, returning the index of any peak is acceptable. To simplify, consider that elements
outside the array are always smaller than the array’s elements.
Constraints: The algorithm should run in O(log n) time.
Example 1:
• Input: nums = [1, 2, 3, 1]
• Output: 2
• Explanation: The element 3 is a peak element, and the function should return the index 2.
Example 2:
• Input: nums = [1, 2, 1, 3, 5, 6, 4]
• Output: 5
• Explanation: The function can return either index 1 where the peak element is 2, or index 5 where the
peak element is 6.
3
Constraints:
• 1 ≤ [Link] ≤ 1000
• −231 ≤ nums[i] ≤ 231 − 1
• nums[i] != nums[i + 1 for all valid i.
Your Task: You do not need to read input or print anything. Complete the function findPeakElement which
takes an array of integers as input and returns the index of a peak element.
Class Definition:
class Solution {
public:
int findPeakElement(vector<int>& nums) {
// Implement the logic to find a peak element in O(log n) time
}
};