Day 2 : 100 Days Of DSA

Welcome to Day 2 of my 100 Days of DSA challenge! Today, I solved five problems focused on arrays. 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 . Find the largest and smallest element in an array

To find the largest and smallest elements in an array, we can start by assuming initial values for both: INT_MIN for the largest element and INT_MAX for the smallest element. Then, we iterate through the array, comparing each element to the current largest and smallest values. If we find an element that is larger than the current largest or smaller than the current smallest, we update accordingly. This approach ensures that we efficiently determine both values in a single pass through the array.

The time complexity of this approach will be O(n).

Code:

//To find the largest and smallest element in an array
#include<iostream>
#include<climits>
using namespace std;

// Time complexity -> O(n)
void max_min(int arr[],int n){
    int min=INT_MAX;
    int max=INT_MIN;
    for(int i=0;i<n;i++){
        if(arr[i]<min){
            min=arr[i];
        }
        if(arr[i]>max){
            max=arr[i];
        }
    }
    cout<<"Smallest Element is:"<<min<<endl;
    cout<<"Largest Element is:"<<max<<endl;
}

int main(){
    int arr[]={10,3,24,33,0,12,56,78,32,-1,78};
    int n=sizeof(arr) / sizeof(arr[0]);
    max_min(arr,n);
}

Output:

2. Find the second largest element in an array

To find the second largest element in an array, we initialize two variables: largest and second_largest, both set to INT_MIN. As we iterate through the array, we update largest if a larger element is found and adjust second_largest accordingly. If no second largest element exists (like in cases of identical or single-element arrays), we return -1.

This solution has a time complexity of O(n), as it requires a single pass through the array.

Code:

//To find the second largest element in an array
#include<iostream>
#include<climits>
using namespace std;

// Time Complexity -> O(n)
int secondLargest(int arr[],int n){
    int largest=INT_MIN;
    int second_largest=INT_MIN;
    for(int i=0;i<n;i++){
        if (arr[i]>largest){
            second_largest=largest;
            largest=arr[i];
        }
    }
    if(second_largest==INT_MIN){
        return -1;
    }
    return second_largest;
}

int main(){
    int arr1[]={1,2,45,9,78,23,67};
    int arr2[]={1,1,1,1,1,1,1,1,1};
    int n1=sizeof(arr1)/sizeof(arr1[0]);
    int n2=sizeof(arr2)/sizeof(arr2[0]);
    int res1=secondLargest(arr1,n1);
    int res2=secondLargest(arr2,n2);
    cout<<"Second largest in arr1:"<<res1<<endl;
    cout<<"Second largest in arr2:"<<res2<<endl; //-1 if there is no second largest element

}

Output:

3 . Count the occurrences of a given element in array

To count the occurrences of a given element in an array, we iterate through the array and compare each element with the target value. If a match is found, we increment a counter. The process is repeated for all elements in the array. The time complexity of this approach is O(n), where n is the number of elements in the array, as we only make a single pass through the array.

Code:

//To count the occurrences of a given element in an array
#include<iostream>
using namespace std;

//Time complexity -> O(n)
int countOfElement(int arr[],int num,int n){
    int count=0;
    for(int i=0;i<n;i++){
        if(arr[i]==num){
            count++;
        }
    }
    return count;
}

int main(){
    int arr[]={1,0,2,3,1,5,6,7,1,0,6,7,2,3,5,1,0};
    int n=sizeof(arr)/sizeof(arr[0]);
    int countOfOne=countOfElement(arr,1,n);
    int countOfZero=countOfElement(arr,0,n);
    cout<<"One occurrs "<<countOfOne<<" times"<<endl;
    cout<<"Zero occurrs "<<countOfZero<<" times"<<endl;

}

Output:

4. Left rotate an array by k positions

To rotate an array to the left by k positions, we can use two methods:

1. Using a Temporary Array (O(n) space, O(n) time complexity):
   We create a temporary array to store the rotated values. First, we copy the elements from index k to n-1 into the temporary array, then copy the first k elements to the end. Finally, we print the rotated array.

2. Using Reversal Technique (O(1) space, O(n) time complexity):
   This method involves three reversal operations:

   • Reverse the first k elements.

   • Reverse the remaining n-k elements.

   • Reverse the entire array to get the rotated result.

The second method is more efficient in terms of space, as it doesn't require additional memory for a temporary array.

Code:

//To rotate an array to the left by k postions
#include<iostream>
using namespace std;

void reverse(int arr[], int start, int end) {
    while (start < end) {
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

//using temperorary array , takes O(n) space, time complexity is O(n);
void rotate1(int arr[],int n,int k){
    int j=0;
    int temp[100];
    for(int i=k;i<n;i++){
        temp[j++]=arr[i];
    }
    for(int i=0;i<k;i++){
        temp[j++]=arr[i];
    }
    for(int i=0;i<n;i++){
        cout<<temp[i]<<" ";
    }
    cout<<endl;
}


// using the reversal technique take O(1) space, and time complexity is O(n)
void rotate2(int arr[],int n,int k){
       k=k%n;
       reverse(arr,0,k-1);
       reverse(arr,k,n-1);
       reverse(arr,0,n-1);
       for(int i=0;i<n;i++){
        cout<<arr[i]<<" ";
       }
       cout<<endl;
}

int main(){
    int arr[]={1,2,3,4,5,6};
    cout<<"The Rotated Array by the two methods is:"<<endl;
    rotate1(arr,6,2);
    rotate2(arr,6,2);
}

Output:

5. Find the element in array that appears more than once

To find elements that appear more than once, we use nested loops to count occurrences of each element while skipping already-checked elements using a countedAlready array. Any element appearing more than once is added to a temporary array for output. This method has a time complexity of O(n²) and uses additional space for tracking duplicates. This time complexity can be reduced to O(n) if we use a hashmap to store with its frequency.

Code:

// To find all elements in the array that appear more than once
// Time Complexity -> O(n^2)
#include<iostream>
using namespace std;

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

void moreThanOnce(int arr[],int n){
    int temp[100]; // a an array to store the no of times an element appears
    int idx=0;
    int temp_size=0;
    bool countedAlready[100]={false};
    for(int i=0;i<n;i++){
        int count=0;
        if(countedAlready[i]){
            continue;
        }
        for(int j=i+1;j<n;j++){
            if(arr[i]==arr[j]){
                count++;
            }
        }
        if(count>0){
            temp[idx++]=arr[i];
        }
    }

    printArray(temp,idx);
}

int main(){
    int arr[10]={1,2,3,4,5,1,4,2,7,9};
    cout<<"Elements that appear more than once are:"<<endl;
    moreThanOnce(arr,10);
}

Output:

This was all for today. Happy Coding! ✨🍀