Day 3 of the 100 Days DSA Challenge: Arrays Advanced

Welcome to Day 3 of the 100 Days DSA (Data Structures and Algorithms) Challenge! Today, we’ll explore some advanced operations with arrays. These tasks will help you deepen your understanding of array manipulation and prepare you for tackling more complex problems.

1. Implement a Function to Merge Two Sorted Arrays

Merging two sorted arrays involves combining them into one sorted array. This is a fundamental operation used in many sorting algorithms and data processing tasks.

Placeholder for Code Example:

#include <stdio.h>

void mergeSortedArrays(int arr1[], int n1, int arr2[], int n2, int result[]){
    int i = 0, j = 0, k = 0;
    while (i < n1 && j < n2) {
        if (arr1[i] < arr2[j]) {
            result[k++] = arr1[i++];
        } else {
            result[k++] = arr2[j++];
        }
    }
    while (i < n1) {
        result[k++] = arr1[i++];
    }
    while (j < n2) {
        result[k++] = arr2[j++];
    }
}
int main() {
    int arr1[] = {1, 3, 5, 7};
    int arr2[] = {2, 4, 6, 8};
    int n1 = sizeof(arr1)/sizeof(arr1[0]);
    int n2 = sizeof(arr2)/sizeof(arr2[0]);
    int result[n1 + n2];
    mergeSortedArrays(arr1, n1, arr2, n2, result);
    printf("Merged array: ");
    for (int i = 0; i < n1 + n2; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
    return 0;
}

2. Write a Program to Find the Union and Intersection of Two Arrays

Finding the union and intersection of two arrays involves identifying elements that appear in either or both arrays. This task will help you practice set operations and array manipulation.

Placeholder for Code Example:

#include <stdio.h>

void printUnion(int arr1[], int n1, int arr2[], int n2) {
    int i = 0, j = 0;
    printf("Union: ");
    while (i < n1 && j < n2) {
        if (arr1[i] < arr2[j]) {
            printf("%d ", arr1[i++]);
        } else if (arr2[j] < arr1[i]) {
            printf("%d ", arr2[j++]);
        } else {
            printf("%d ", arr1[i]);
            i++;
            j++;
        }
    }
    while (i < n1) printf("%d ", arr1[i++]);
    while (j < n2) printf("%d ", arr2[j++]);
    printf("\n");
}
void printIntersection(int arr1[], int n1, int arr2[], int n2) {
    int i = 0, j = 0;
    printf("Intersection: ");
    while (i < n1 && j < n2) {
        if (arr1[i] < arr2[j]) {
            i++;
        } else if (arr2[j] < arr1[i]) {
            j++;
        } else {
            printf("%d ", arr1[i]);
            i++;
            j++;
        }
    }
    printf("\n");
}
int main() {
    int arr1[] = {1, 3, 4, 5, 7};
    int arr2[] = {2, 3, 5, 6};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    printUnion(arr1, n1, arr2, n2);
    printIntersection(arr1, n1, arr2, n2);
    return 0;
}

3. Solve the Problem of Finding a Subarray with a Given Sum (for Positive Numbers)

Finding a subarray with a given sum is a common problem that can be solved efficiently for positive numbers using a sliding window or two-pointer approach.

Placeholder for Code Example:

#include <stdio.h>

void findSubarrayWithGivenSum(int arr[], int n, int sum) {
    int currentSum = 0, start = 0;
    for (int i = 0; i < n; i++) {
        currentSum += arr[i];
        while (currentSum > sum && start <= i) {
            currentSum -= arr[start];
            start++;
        }
        if (currentSum == sum) {
            printf("Subarray with given sum found between indexes %d and %d\n", start, i);
            return;
        }
    }
    printf("No subarray with given sum found.\n");
}
int main() {
    int arr[] = {1, 2, 3, 7, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 12;
    findSubarrayWithGivenSum(arr, n, sum);
    return 0;
}

4. Implement Kadane's Algorithm to Find the Maximum Sum Subarray

Kadane's algorithm is a powerful technique to find the maximum sum subarray in linear time. This problem is crucial for understanding dynamic programming and optimization.

Placeholder for Code Example:

#include <stdio.h>
#include <limits.h>

void kadaneAlgorithm(int arr[], int n) {
    int maxSoFar = INT_MIN, maxEndingHere = 0;
    for (int i = 0; i < n; i++) {
        maxEndingHere = maxEndingHere + arr[i];
        if (maxSoFar < maxEndingHere) {
            maxSoFar = maxEndingHere;
        }
        if (maxEndingHere < 0) {
            maxEndingHere = 0;
        }
    }
    printf("Maximum sum subarray: %d\n", maxSoFar);
}
int main() {
    int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = sizeof(arr) / sizeof(arr[0]);
    kadaneAlgorithm(arr, n);
    return 0;
}

5. Solve the Problem of Rearranging an Array with Alternate Positive and Negative Numbers

Rearranging an array to alternate positive and negative numbers is a common interview question that tests your ability to manipulate array indices and maintain order.

Placeholder for Code Example:

#include <stdio.h>

void rearrangeArray(int arr[], int n) {
    int temp[n], i, j = 0;
    for (i = 0; i < n; i++) {
        if (arr[i] >= 0) {
            temp[j++] = arr[i];
        }
    }
    for (i = 0; i < n; i++) {
        if (arr[i] < 0) {
            temp[j++] = arr[i];
        }
    }
    for (i = 0; i < n; i++) {
        arr[i] = temp[i];
    }
}

int main() {
    int arr[] = {1, 2, -3, -4, -1, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    rearrangeArray(arr, n);
    printf("Array after rearrangement: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

Conclusion

Today's challenges are designed to strengthen your understanding of arrays and their advanced operations. By working through these exercises, you'll develop valuable problem-solving skills and gain confidence in handling complex array manipulations. Keep up the great work, and see you tomorrow for Day 4 of the 100 Days DSA Challenge!