Day 2 (Array Basics)

Welcome to Day 2 of my 100 Days of DSA journey! Today, I delved into arrays, one of the fundamental data structures in programming. Arrays offer a convenient way to store and manipulate collections of data. Here are five problems I tackled, along with solutions, to understand their capabilities better. Let’s dive in!

I have also maintained a GitHub repository for the same so please free to check it out as well: github.com/AayJayTee/100-Days-DSA

Q1. Write a program to find the largest and smallest elements in an array.

#include <iostream>
using namespace std;

void largest_smallest_in_array(int arr[],int n){
    int max=arr[0],min=arr[0];  // Initialize max and min with the first element

    for(int i=0;i<n;i++){
        if(max<arr[i]){  // If current element is greater than max, update max
            max=arr[i];
        if(min>arr[i]){  // If current element is smaller than min, update min
            min=arr[i];
        }
        }
    }

    // Output the largest and smallest elements
    cout<<"The largest element is: "<<max<<endl;
    cout<<"The smallest element is: "<<min;
}

int main()
{
    int n;
    cout<<"Enter length of array: ";
    cin>>n;
    int arr[n];  // Declare an array of size n
    cout<<"Enter elements of the array: ";
    for(int i=0;i<n;i++){
        cin>>arr[i];  // Input elements for the array
    }
    largest_smallest_in_array(arr,n);  // Call function to find largest and smallest
    return 0;
}

This program identifies the second largest element by maintaining two variables: max and secmax. As the array is traversed, max is updated to the highest value, and secmax is updated to the second highest. An additional condition ensures secmax is distinct from max, making the approach robust. This solution also runs in O(n) time.

Q2. Implement a program to find the second largest element in an array.

#include <iostream>
using namespace std;

void secondlargest(int arr[],int n){
    int secmax=arr[0];  // Initialize secmax with the first element
    int max=arr[0];  // Initialize max with the first element
    for(int i=0;i<n;i++){
        if(max<arr[i]){  // If current element is greater than max, update secmax and max
            secmax=max;
            max=arr[i];
        }
        else if(secmax<arr[i] && arr[i]!=max){  // If current element is greater than secmax but not equal to max
            secmax=arr[i];
        }
    }
    cout<<"The second largest element is: "<<secmax;  // Output the second largest element
}

int main()
{
    int n;
    cout<<"Enter length of array: ";
    cin>>n;
    int arr[n];  // Declare an array of size n
    cout<<"Enter elements of the array: ";
    for(int i=0;i<n;i++){
        cin>>arr[i];  // Input elements for the array
    }
    secondlargest(arr,n);  // Call function to find second largest
    return 0;
}

Q3. Write a function to rotate an array to the left by k positions.

#include <iostream>
using namespace std;

void rotate_array(int arr[],int n,int k){
    int temp=0;  // Temporary variable to store the first element
    for(int i=0;i<k;i++){  // Rotate the array k times
        temp=arr[0];  // Store the first element in temp
        for(int j=0;j<n-1;j++){  // Shift elements to the left by 1
            arr[j]=arr[j+1];
        }
        arr[n-1]=temp;  // Place the first element at the end of the array
    }
    cout<<"The shifted array is: ";  // Output the rotated array
    for(int i=0;i<n;i++){
        cout<<arr[i];  // Print the elements of the rotated array
    }
}

int main()
{
    int n,k;
    cout<<"Enter length of array: ";
    cin>>n;
    int arr[n];  // Declare an array of size n
    cout<<"Enter elements of the array: ";
    for(int i=0;i<n;i++){
        cin>>arr[i];  // Input elements for the array
    }  
    cout<<"Enter how many positions you want to shift it by?: ";
    cin>>k;  // Input the number of positions to shift
    rotate_array(arr,n,k);  // Call function to rotate the array
    return 0;
}

To rotate an array, this program repeatedly shifts elements one position to the left k times. A temporary variable stores the first element, and a nested loop performs the shifting. The solution, while simple, has a time complexity of O(k * n).

Q4. Create a program to count the number of occurrences of a given element in an array

#include <iostream>
using namespace std;

void no_of_occurance(int arr[],int n, int a){
    int count = 0;  // Initialize count to 0
    for(int i=0;i<n;i++){  // Loop through the array
        if(arr[i]==a){  // If the current element is equal to a, increment count
            count+=1;
        }
    }
    cout<<a<<" occurs "<<count<<" times in the array";  // Output the count of the element
}

int main()
{
    int n,a;
    cout<<"Enter length of array: ";
    cin>>n;
    int arr[n];  // Declare an array of size n
    cout<<"Enter elements of the array: ";
    for(int i=0;i<n;i++){
        cin>>arr[i];  // Input elements for the array
    }  
    cout<<"Enter the element: ";
    cin>>a;  // Input the element whose occurrences need to be counted
    no_of_occurance(arr,n,a);  // Call function to count occurrences
    return 0;
}

This program counts the occurrences of a specific element in the array by traversing it and incrementing a counter each time the element matches the target. This straightforward solution efficiently solves the problem in O(n) time. It is flexible enough to work for arrays of any size.

Q5. Solve the "find all elements that appear more than once in an array" problem.

#include <iostream>
using namespace std;

void appear_more_than_once(int arr[], int n) {
    cout << "The elements that appear more than once are: ";
    for (int i = 0; i < n; i++) {
        bool isDuplicate = false;  // Flag to check if the element is a duplicate

        // Check if the element has already been printed
        for (int k = 0; k < i; k++) {
            if (arr[i] == arr[k]) {
                isDuplicate = true;  // Mark as duplicate
                break;
            }
        }
        if (isDuplicate) continue;  // Skip already printed elements

        // Count occurrences of the current element
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (arr[i] == arr[j]) {
                count++;  // Increment the count for this element
            }
        }

        // Print the element if it appears more than once
        if (count > 1) {
            cout << arr[i] << " ";
        }
    }
    cout << endl;  // Output the end of the list of duplicates
}

int main() {
    int n;
    cout << "Enter length of array: ";
    cin >> n;
    int arr[n];  // Declare an array of size n
    cout << "Enter elements of the array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];  // Input elements for the array
    }
    appear_more_than_once(arr, n);  // Call function to find duplicates
    return 0;
}

This program identifies duplicate elements by checking if they have already been processed and then counting their occurrences. The nested loop ensures that each element is checked against the rest of the array. Although functional, this approach runs in O(n²) time, which could be improved using hash maps or frequency arrays for larger datasets.

Today’s practice helped me deepen my understanding of array manipulation and problem-solving techniques. From identifying key elements to performing rotations and counting frequencies, arrays offer a wealth of operations. While some solutions are optimized, others present opportunities to explore more efficient approaches in the future. Onward to Day 3 !