Welcome to Day 3! Today, I’ll be tackling advanced array problems that require a deeper dive into problem-solving. These challenges focused on algorithmic thinking and efficient data handling techniques. Below, you’ll find the problems I solved and the strategies I used to approach them.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let’s keep this journey going! 🚀✨
1. Merge Two Sorted Arrays
This program merges two sorted arrays into a single sorted array. The merge_sorted function takes two sorted arrays and their sizes as input, combines them into a single sorted array, and displays the result. The merging is performed efficiently by comparing elements from both arrays sequentially. This approach ensures the resulting array is sorted without requiring additional sorting steps.
Code:
#include <iostream>
using namespace std;
// Function to merge two sorted arrays
void merge_sorted(int arr1[], int arr2[], int n1, int n2) {
int resn = n1 + n2; // Total size of the resulting merged array
int *res_arr = new int[resn];
int i = 0, j = 0, k = 0;
// Traverse both arrays and merge them
while (i < n1 || j < n2) {
// All elements from arr1 are processed
// Add remaining elements of arr2
if (i == n1) {
res_arr[k++] = arr2[j++];
}
// All elements from arr2 are processed
// Add remaining elements of arr1
else if (j == n2) {
res_arr[k++] = arr1[i++];
}
// Element in arr1 is smaller
else if (arr1[i] < arr2[j]) {
res_arr[k++] = arr1[i++];
}
// Element in arr2 is smaller or equal
else {
res_arr[k++] = arr2[j++];
}
}
cout << "The merged sorted array is: ";
for (int i = 0; i < resn; i++) {
cout << res_arr[i] << " ";
}
delete[] res_arr;
}
int main() {
int n1, n2;
cout << "Enter number of elements in array 1: ";
cin >> n1;
int *arr1 = new int[n1];
cout << "Enter elements of arr1: ";
for (int i = 0; i < n1; i++) {
cin >> arr1[i];
}
cout << "Enter number of elements in array 2: ";
cin >> n2;
int *arr2 = new int[n2];
cout << "Enter elements of arr2: ";
for (int i = 0; i < n2; i++) {
cin >> arr2[i];
}
merge_sorted(arr1, arr2, n1, n2);
delete[] arr1;
delete[] arr2;
return 0;
}
Output:
2. Union and Intersection of Two Arrays
This program calculates the union and intersection of two arrays. The union contains all unique elements from both arrays, while the intersection includes only the common elements present in both arrays. The code uses sorting to facilitate efficient comparison and ensures duplicates are removed in the output.
Union Calculation:
Combines both arrays into a temporary array.
Sorts the temporary array to group duplicates together.
Removes duplicates by checking if the current element is the same as the previous one.
Intersection Calculation:
Sorts both input arrays for easier comparison.
Uses a two-pointer technique to iterate through both arrays simultaneously.
Identifies common elements and ensures duplicates are avoided in the result.
Code:
#include <iostream>
#include <algorithm>
using namespace std;
// Function to calculate the union of two arrays
void arr_union(int arr1[], int arr2[], int n1, int n2) {
// Combine both arrays into a temporary array
int *temp_arr = new int[n1 + n2];
int k = 0;
// Copy elements of the first array into temp_arr
for (int i = 0; i < n1; i++) {
temp_arr[k++] = arr1[i];
}
// Copy elements of the second array into temp_arr
for (int i = 0; i < n2; i++) {
temp_arr[k++] = arr2[i];
}
// Sort the combined array to make duplicate removal easier
sort(temp_arr, temp_arr + k);
// Remove duplicates and store unique elements in res_arr
int *res_arr = new int[k];
int res_n = 0;
for (int i = 0; i < k; i++) {
if (i == 0 || temp_arr[i] != temp_arr[i - 1]) {
res_arr[res_n++] = temp_arr[i];
}
}
cout << "The union of arrays is: [ ";
for (int i = 0; i < res_n; i++) {
cout << res_arr[i] << " ";
}
cout << "]" << endl;
delete[] temp_arr;
delete[] res_arr;
}
// Function to calculate the intersection of two arrays
void arr_intersection(int arr1[], int arr2[], int n1, int n2) {
// Sort both arrays to facilitate efficient comparison
sort(arr1, arr1 + n1);
sort(arr2, arr2 + n2);
int i = 0, j = 0;
int *res_arr = new int[min(n1, n2)];
int k = 0;
// Use two-pointer technique to find common elements
while (i < n1 && j < n2) {
if (arr1[i] < arr2[j]) {
i++; // Move pointer in arr1 forward if its element is smaller
}
else if (arr1[i] > arr2[j]) {
j++; // Move pointer in arr2 forward if its element is smaller
}
else {
// Avoid adding duplicates to the result
if (k == 0 || res_arr[k - 1] != arr1[i]) {
res_arr[k++] = arr1[i];
}
i++;
j++;
}
}
cout << "The intersection of arrays is: [ ";
for (int i = 0; i < k; i++) {
cout << res_arr[i] << " ";
}
cout << "]" << endl;
delete[] res_arr;
}
int main() {
int n1, n2;
cout << "Enter number of elements in array 1: ";
cin >> n1;
int *arr1 = new int[n1];
cout << "Enter elements of arr1: ";
for (int i = 0; i < n1; i++) {
cin >> arr1[i];
}
cout << "Enter number of elements in array 2: ";
cin >> n2;
int *arr2 = new int[n2];
cout << "Enter elements of arr2: ";
for (int i = 0; i < n2; i++) {
cin >> arr2[i];
}
arr_union(arr1, arr2, n1, n2);
arr_intersection(arr1, arr2, n1, n2);
delete[] arr1;
delete[] arr2;
return 0;
}
Output:
3. Find Subarray with a Given Sum (Positive Numbers)
This program finds all subarrays within a given array that sum up to a specified target value. It uses a sliding window approach, where two pointers (i and j) track the current subarray. As the window expands by moving j, if the sum exceeds the target, it shrinks by moving i. If the sum equals the target, the program prints the indices of the subarray. This approach efficiently identifies all valid subarrays with a time complexity of O(n).
Code:
#include <iostream>
using namespace std;
// Function to locate all subarrays with the given sum
void find_subarrays(int arr[], int n, int target_sum) {
int i = 0, current_sum = 0;
// Iterate through the array
for (int j = 0; j < n; j++) {
// Add the current element to the running sum
current_sum += arr[j];
// Shrink the window if the sum exceeds the target
while (current_sum > target_sum && i < j) {
current_sum -= arr[i];
i++;
}
// If the current sum matches the target sum, print the subarray
if (current_sum == target_sum) {
cout << "Subarray with the target sum " << target_sum
<< " is found from index " << i << " to " << j << "." << endl;
}
}
// If no subarray with the given sum is found
if (current_sum != target_sum) {
cout << "No subarray with the target sum found." << endl;
}
}
int main() {
int n, target_sum;
cout << "Enter the number of elements in the array: ";
cin >> n;
int *arr = new int[n];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "Enter the target sum: ";
cin >> target_sum;
// Find all subarrays with the target sum
find_subarrays(arr, n, target_sum);
delete[] arr;
return 0;
}
Output:
4. Kadane's Algorithm for Maximum Sum Subarray
The code implements Kadane’s Algorithm to find the subarray with the maximum sum in a given array of integers. It efficiently computes the sum of contiguous subarrays, keeps track of the current sum, and updates the maximum sum found so far. Additionally, it outputs both the maximum sum and the corresponding subarray.
Code:
#include <iostream>
using namespace std;
// Function to implement Kadane's Algorithm to find the maximum sum subarray
void max_subarr(int arr[], int n) {
int max_sum = arr[0], curr_sum = arr[0];
int start = 0, end = 0, temp_start = 0;
// Iterate through the array starting from the second element
for (int i = 1; i < n; i++) {
// Update current sum by choosing the maximum between the current element or adding it to the current sum
if (arr[i] > curr_sum + arr[i]) {
curr_sum = arr[i];
temp_start = i;
}
else {
curr_sum += arr[i];
}
// Update the maximum sum found so far
if (curr_sum > max_sum) {
max_sum = curr_sum;
start = temp_start;
end = i;
}
}
cout << "Maximum subarray sum is: " << max_sum << endl;
cout << "Subarray with maximum sum is: ";
for (int i = start; i <= end; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int n;
cout << "Enter the number of elements in the array: ";
cin >> n;
int *arr = new int[n];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
max_subarr(arr, n);
delete[] arr;
return 0;
}
Output:
5. Rearrange Array with Alternate Positive and Negative Numbers
Code:
#include <iostream>
using namespace std;
// Function to rearrange array with alternate positive and negative numbers
void rearrange_arr(int arr[], int n) {
int pos[n], neg[n];
int posIndex = 0, negIndex = 0;
// Separate positives and negatives into two different arrays
for (int i = 0; i < n; i++) {
if (arr[i] >= 0) {
pos[posIndex++] = arr[i];
}
else {
neg[negIndex++] = arr[i];
}
}
int i = 0, p = 0, q = 0;
// Place elements from positives and negatives alternately
while (p < posIndex && q < negIndex) {
arr[i++] = pos[p++];
arr[i++] = neg[q++];
}
// If there are remaining positives, add them
while (p < posIndex) {
arr[i++] = pos[p++];
}
// If there are remaining negatives, add them
while (q < negIndex) {
arr[i++] = neg[q++];
}
cout << "Rearranged Array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int n;
cout << "Enter the number of elements in the array: ";
cin >> n;
int *arr = new int[n];
cout << "Enter elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
rearrange_arr(arr, n);
delete[] arr;
return 0;
}
Output:
And that’s Day 3 done! Today’s problems were a great mix of challenges, from array manipulations to implementing Kadane's Algorithm. I’ve gained a deeper understanding of key concepts like subarrays and array rearrangement, which are vital for coding interviews.
Solving these problems has been both fun and insightful, and I’m excited to tackle more on Day 4. Let’s keep the momentum going! 🚀