Day 3 : 100 Days Of DSA

Hey there, welcome to the day 3 of 100 days of DSA challenge. Today, I’ll be solving some advanced array problems. Here's a quick look at the questions I tackled and how I approached them 🤖✨ Check out my GitHub repository for all my solutions and progress. Let’s keep learning!

---

1. To find the union and intersection of two arrays

This problem can be solved by first iterating through both arrays and adding elements to the result array. For the union, elements from the second array are added only if they are not already present in the result array. For the intersection, the code checks if each element of the second array exists in the first array and adds common elements to the result. The isPresent function is used to check for duplicates in the result array, and both operations have a time complexity of O(n).

Code:

// To find the union and intersection of two arrays
#include<iostream>
using namespace std;

//Array1 - 1,2,3,4,1,3,2,7
//Array2- 2,3,6,9,0,1,3
//Union- 1,2,3,4,1,3,2,7,2,3,6,9,0,1,3

bool isPresent(int arr[],int element,int size){
    for(int i=0;i<size;i++){
        if(arr[i]==element){
            return true;
        }
    }
    return false;
}
// Time Complexity -> O(n), Space Complexity-> O(n)
void unionArray(int arr1[],int arr2[],int n1,int n2){
    int j=0;
    int res[n1+n2];
    for(int i=0;i<n1;i++){
        res[j++]=arr1[i];
    }
    for(int i=0;i<n2;i++){
        if(!isPresent(res,arr2[i],j)){
            res[j++]=arr2[i];
        }

    }

    cout<<"The union of the two arrays is:"<<endl;
    for(int i=0;i<j;i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
}


// Time Complexity -> O(n), Space Compexity -> O(n)
void intersectionArray(int arr1[],int arr2[],int n1,int n2){
    int res[n1+n2];
    int j=0;
    for(int i=0;i<n1;i++){
        if(isPresent(arr1,arr2[i],n1)){
            res[j++]=arr2[i];
        }
    }

    cout<<"Intersection of the two arrays is:"<<endl;
    for(int i=0;i<j;i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
}

int main(){
    int arr1[6]={3,4,5,2,1,1};
    int arr2[6]={1,2,7,8,9,0};
    unionArray(arr1,arr2,6,6);
    intersectionArray(arr1,arr2,6,6);
}

Output:

---

2. To merge two sorted arrays

The solution merges two sorted arrays by iterating through both arrays using two pointers and comparing their elements. It selects the smaller element between the two arrays at each step and adds it to the result array. The process continues until all elements from both arrays are merged. The time complexity is O(n) because each element is processed once, and the space complexity is O(n) due to the extra result array used to store the merged elements.

Code:

//To merge two sorted arrays

#include<iostream>
using namespace std;

// Time Complexity -> O(n), Space Complexity -> O(n)
void merge(int arr1[],int arr2[],int n1,int n2){
    int res[n1+n2];
    int i=0,j=0,k=0;
    while(i<n1 || j<n2){
        if(arr1[i]<=arr2[j]){
            res[k++]=arr1[i];
            i++;
        }
        else{
            res[k++]=arr2[j];
            j++;
        }
    }
    cout<<"Merging two arrays in sorted manner:"<<endl;
    for(int i=0;i<k;i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
}

int main(){
    int arr1[8]={0,1,1,6,7,45,67,99};
    int arr2[9]={3,4,5,8,9,33,78,90,100};
    merge(arr1,arr2,8,9);
}

Output:

---

3. Rearranging an array with alternate positive and negative numbers.

The solution separates the positive and negative numbers from the array into two separate vectors. It then places them alternately back into the original array, starting with the array that has more elements. If there are leftover elements in the larger array, they are placed at the end. The time complexity is O(n) because we process each element once, and the space complexity is O(n) due to the extra space used to store positive and negative numbers separately.

Code:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

void rearrangeArray(vector<int>& arr, int n) {
    vector<int> pos;
    vector<int> neg;

    for(int i = 0; i < n; i++) {
        if(arr[i] > 0) {
            pos.push_back(arr[i]);
        } else {
            neg.push_back(arr[i]);
        }
    }

    int pos_size = pos.size();
    int neg_size = neg.size();

    int i = 0;
    if(pos_size > neg_size) {
        for(i = 0; i < neg_size; i++) {
            arr[2*i] = pos[i];
            arr[2*i+1] = neg[i];
        }
        int idx = neg_size * 2;
        for(i = neg_size; i < pos_size; i++) {
            arr[idx++] = pos[i];
        }
    } else {
        for(i = 0; i < pos_size; i++) {
            arr[2*i] = pos[i];
            arr[2*i+1] = neg[i];
        }
        int idx = pos_size * 2;
        for(i = pos_size; i < neg_size; i++) {
            arr[idx++] = neg[i];
        }
    }

    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {1, 2, -3, -4, 5, -6, -7, 8};
    int n = arr.size();
    rearrangeArray(arr, n);
    return 0;
}

Output:

---

4. To find a subarray with a given sum (for positive numbers).

This solution finds a subarray with a given sum using a sliding window approach. It maintains a running sum (curr_sum) and a start pointer to adjust the window size when the sum exceeds the target. If the sum equals the target, the subarray is printed, and the function returns true. The time complexity of this solution is O(n) because each element is processed once as the start and end pointers move through the array, making it linear in time.

Code:

// To find a subarray with a given sum
#include<iostream>
using namespace std;

bool subarraySum(int arr[], int n, int target) {
    int start = 0, curr_sum = 0;

    for(int end = 0; end < n; end++) {
        curr_sum += arr[end];

        while(curr_sum > target && start < end) {
            curr_sum -= arr[start];
            start++;
        }

        if(curr_sum == target) {
            cout << "Subarray found from index " << start << " to " << end << "with target "<<target<<endl;
            return true;
        }
    }
    return false;
}

int main() {
    int arr[] = {1, 2, 3, 7, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    int target = 12;

    if(!subarraySum(arr, n, target)) {
        cout << "No subarray found" << endl;
    }

    return 0;
}

Output:

---

5. To implement Kadane's Algorithm to find the maximum sum subarray.

Kadane's Algorithm keeps track of the current subarray sum (curr_sum) and updates it by either adding the current element or starting a new subarray from the current element. The max_sum is updated with the maximum of the current subarray sum. The solution iterates through the array once, updating the maximum sum as needed.

Code:

// To implement kadane's algorithm to find maximum subarray sum
#include<iostream>
using namespace std;

int maxSubArraySum(int arr[], int n) {
    int max_sum = arr[0], curr_sum = arr[0];

    for(int i = 1; i < n; i++) {
        curr_sum = max(arr[i], curr_sum + arr[i]);
        max_sum = max(max_sum, curr_sum);
    }

    return max_sum;
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Maximum subarray sum is " << maxSubArraySum(arr, n) << endl;
    return 0;
}

Output:

---

And that wraps up the five problems I completed today! It’s been a great learning experience working through them. Happy coding, and here's to many more coding challenges ahead! ✨