Day-2 : Array (Basics)

Welcome back to "DSA with Mee"! After yesterday's introduction, we’re diving right into some key array operations today. Arrays are the backbone of many problems in programming, so it’s important to get comfortable with them. We'll be solving five core problems involving arrays that will help build your understanding

1. Find the Largest and Smallest Elements in an Array

This is one of the most common tasks when working with arrays. The goal is to find the biggest and smallest elements. We do this by iterating through the array and keeping track of the largest and smallest numbers we encounter.

How It’s Done:

• We initialize the largest and smallest variables to extreme values.

• Then, we loop through the array and update largest and smallest whenever we find a larger or smaller value.

#include <iostream>
#include <climits>
using namespace std;

void findLargestAndSmallest(int arr[], int n) {
    int largest = INT_MIN, smallest = INT_MAX;

    for (int i = 0; i < n; i++) {
        if (arr[i] > largest) {
            largest = arr[i];
        }
        if (arr[i] < smallest) {
            smallest = arr[i];
        }
    }

    cout << "Largest: " << largest << ", Smallest: " << smallest << endl;
}

int main() {
    int arr[] = {12, 35, 1, 10, 34, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    findLargestAndSmallest(arr, n);
    return 0;
}

OUTPUT:

2. Find the Second Largest Element in an Array

The second largest element is an interesting challenge because we have to remember the largest element, and then find the next one that is just smaller than it. This can be done in a single pass through the array.

How It’s Done:

• We keep track of the largest and second largest elements while iterating through the array.

• Whenever we find a new largest element, we update both the largest and second largest.

#include <iostream>
#include <climits>
using namespace std;

int findSecondLargest(int arr[], int n) {
    if (n < 2) {
        return -1;  // Not enough elements to find the second largest
    }

    int largest = INT_MIN, secondLargest = INT_MIN;

    for (int i = 0; i < n; i++) {
        if (arr[i] > largest) {
            secondLargest = largest;
            largest = arr[i];
        } else if (arr[i] > secondLargest && arr[i] != largest) {
            secondLargest = arr[i];
        }
    }

    return secondLargest;
}

int main() {
    int arr[] = {12, 35, 1, 10, 34, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    int secondLargest = findSecondLargest(arr, n);
    if (secondLargest == INT_MIN) {
        cout << "Second largest not found." << endl;
    } else {
        cout << "Second Largest: " << secondLargest << endl;
    }
    return 0;
}

OUTPUT:

3. Rotate an Array to the Left by k Positions

Rotating an array means shifting all the elements to the left by k positions. This is a very useful operation when dealing with circular data.

How It’s Done:

• First, we compute k % n to handle cases where k is greater than the array length.

• Then, we copy the elements in the rotated order into a temporary array and put them back.

#include <iostream>
using namespace std;

void rotateArray(int arr[], int n, int k) {
    k = k % n;  // If k is larger than n
    int temp[n];

    // Copy the elements from k to n-1 to the start of the temporary array
    for (int i = 0; i < n; i++) {
        temp[i] = arr[(i + k) % n];
    }

    // Copy the rotated array back to the original
    for (int i = 0; i < n; i++) {
        arr[i] = temp[i];
    }
}

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

    rotateArray(arr, n, k);

    cout << "Array after rotating " << k << " positions: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

OUTPUT:

4. Count the Number of Occurrences of a Specific Element

This is a straightforward problem. We just need to count how many times a given element appears in the array.

How It’s Done:

• We loop through the array, and every time we find the element, we increment a counter.

#include <iostream>
using namespace std;

int countOccurrences(int arr[], int n, int element) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == element) {
            count++;
        }
    }
    return count;
}

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

    int count = countOccurrences(arr, n, element);
    cout << "Element " << element << " appears " << count << " times." << endl;

    return 0;
}

OUTPUT:

5. Find All Elements that Appear More Than Once in the Array

Finding duplicates in an array is a common task. We use a frequency map (hash table) to count how many times each element appears, then return the elements with a frequency greater than 1.

How It’s Done:

• We use an unordered map to store the frequency of each element.

• Then, we check the map to find elements that appear more than once.

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

vector<int> findDuplicates(int arr[], int n) {
    unordered_map<int, int> freqMap;
    vector<int> duplicates;

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

    for (auto& pair : freqMap) {
        if (pair.second > 1) {
            duplicates.push_back(pair.first);
        }
    }

    return duplicates;
}

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

    vector<int> duplicates = findDuplicates(arr, n);
    cout << "Elements that appear more than once: ";
    for (int num : duplicates) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

OUTPUT:

---

Today, we covered essential array operations that are key to understanding and solving many algorithmic problems. Mastering these basic operations will help you efficiently work with arrays and lay a solid foundation for more complex topics. Keep practicing, and stay tuned for our next post.