Skip to main content

Arrays

Arrays: Mastering it

Let's master the array concept by solving a few more problems on arrays.

Problem 1: To find second largest element

Write a C++ program to find the second largest element of an array.

Input

Input size of array: 5
Array elements: 10, 30, 50, 20, 45

Output

Second largest element: 45

Intuition

Let's first revise that how we found our max element in warm up article. We took our max value to be INT_MIN, iterated the array and kept updating max value as soon as we found a value larger than that.

In this problem, we'll have 2 variables: max1 and max2. max1 will store the maximum element just like in the above mentioned problem, and max2 will store the second largest element. But now how to update max2??

See as soon as we find an element larger than max1, we update it to that element means that the current value before update was the largest element till now and hence the second largest right? This means before updating we need to make max2 as max1 and then update the max1.

But is the problem solved? What if the first element is the max element implying that max1 never gets updated after that? Hence, we also need to check that if any array element is greater than max2 (second largest element) but less than max1 (largest element). If this case is true then max2 has to be updated to this array value.

Logic

  1. Input size and elements in array, store it in some variable say size and arr.
  2. Declare two variables max1 and max2 to store first and second largest elements. Store minimum integer value in both i.e. max1 = max2 = INT_MIN.
  3. Iterate though all array elements, run a loop from 0 to size - 1. Loop structure should look like for(i=0; i<size; i++).
  4. Inside loop, check if current array element is greater than max1, then make largest element as second largest and current array element as largest. Say, max2 = max1 and max1 = arr[i].
  5. Else if the current array element is greater than max2 but less than max1 then make current array element as second largest i.e. max2 = arr[i].

Try it yourself

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

int main()
{
    int size, i;
    int max1, max2;

    // Input size of the array
    cout << "Enter size of the array: ";
    cin >> size;

	// Create array
	int arr[size];

    // Input array elements
    cout << "Enter elements in the array: ";
    for(i = 0; i < size; i++)
    {
        cin >> arr[i];
    }

    max1 = max2 = INT_MIN;

    // Check for first largest and second
    for(i = 0; i < size; i++)
    {
        if(arr[i] > max1)
        {
            // If current element of the array is first largest
            // then make current max as second max
            // and then max as current array element
            max2 = max1;
            max1 = arr[i];
        }
        else if(arr[i] > max2 && arr[i] < max1)
        {
            // If current array element is less than first largest
            // but is greater than second largest then make it
            // second largest
            max2 = arr[i];
        }
    }

    cout << "First largest = " << max1 << endl;
    cout << "Second largest = " << max2 << endl;

    return 0;
}

Problem 2: Left Rotate an array

Write a C++ program to left rotate an array at a specified position.

Input

Input array size: 5
Input array elements: 10 20 30 40 50
No. of times to left rotate: 2

Output

Array elements: 30, 40, 50, 10, 20

Intuition

What we understand in this problem is to left rotate this array once and repeat that process for the no. of times required. This makes one thing clear that we'll call a left_rotate_once function for the no. of times required. Now what to write in this function?

What I can observe is that except last element, every element takes the value of its next element and last element becomes the first element. Hence, the process is simplified!

  • Let the array size be n
  • Store the first element in a variable: first
  • Make every arr[i] = arr[i+1] except the last element
  • Update the last element: arr[n-1] = first
  • Print the updated array.

Logic

  1. Read elements in an array say arr.
  2. Read number of times to rotate in some variable say N.
  3. Left Rotate the given array by 1 for N times. In real, left rotation is shifting of array elements to one position left and copying first element to last.

Try it yourself

Solution
#include <iostream>
using namespace std;

void printArray(int arr[], int size);
void left_rotate_once(int arr[], int size);

int main()
{
    int i, N, size;

    // Input size of the array
    cout << "Enter size of the array: "<<endl;
    cin >> size;

    // Dynamically allocate array based on the input size
    int* arr = new int[size];

    // Input array elements
    cout << "Enter " << size << " elements: "<<endl;
    for(i = 0; i < size; i++)
    {
        cin >> arr[i];
    }

    // Input number of times to left rotate
    cout << "Enter number of times to left rotate: "<<endl;
    cin >> N;

    // Actual rotation
    N = N % size;

    // Print array before rotation
    cout << "Array before rotation: ";
    printArray(arr, size);

    // Rotate array n times
    for(i = 0; i < N; i++)
    {
        left_rotate_once(arr, size);
    }

    // Print array after rotation
    cout << "Array after rotation: ";
    printArray(arr, size);

    // Free dynamically allocated memory
    delete[] arr;

    return 0;
}

void left_rotate_once(int arr[], int size)
{
    int i, first;

    // Store first element of array
    first = arr[0];

    for(i = 0; i < size - 1; i++)
    {
        // Move each array element to its left
        arr[i] = arr[i + 1];
    }

    // Copy the first element of array to last
    arr[size - 1] = first;
}

// Print the given array
void printArray(int arr[], int size)
{
    for(int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}
💡
You must be wondering that why have we written the left_rotate_once and printArray functions after the main() function. Shouldn't it be written before main() ?? Yes you're absolutely correct but you should also know that this is another way to declare and define functions.
In such cases, where you are defining the function after main(), you need to declare them first (before main() function).
Reminder: A separate declaration is not required if you are defining the function before the main() function.

Problem 3: Right rotate an array

Write a C++ program to right rotate an array at a specified position.

Input

Input array size: 5
Input array elements: 10 20 30 40 50
No. of times to right rotate: 2

Output

Array elements: 40, 50, 10, 20, 30

Intuition

This problem is very similar to the previous one. We just need to change the function left_rotate_once to right_rotate_once. Can you guess what all changes will be required?

What I can observe is that except first element, every element takes the value of its previous element and first element becomes the last element. Hence, the process is simplified!

  • Let the array size be n
  • Store the last element in a variable: last
  • Make every arr[i] = arr[i-1] except the first element
  • Update the first element: arr[0] = last
  • Print the updated array.

Logic

  1. Read elements in an array say arr.
  2. Read number of times to rotate in some variable say N.
  3. Right rotate the given array by 1 for N times. In real right rotation is shifting of array elements to one position right and copying last element to first.

Try it yourself

Solution
#include <iostream>
using namespace std;

void printArray(int arr[], int size);
void right_rotate_once(int arr[], int size);

int main()
{
    int i, N, size;

    // Input size of the array
    cout << "Enter size of the array: " << endl;
    cin >> size;

    // Dynamically allocate array based on the input size
    int* arr = new int[size];

    // Input array elements
    cout << "Enter " << size << " elements: " << endl;
    for(i = 0; i < size; i++)
    {
        cin >> arr[i];
    }

    // Input number of times to right rotate
    cout << "Enter number of times to right rotate: " << endl;
    cin >> N;

    // Actual rotation
    N = N % size;

    // Print array before rotation
    cout << "Array before rotation: ";
    printArray(arr, size);

    // Rotate array n times
    for(i = 0; i < N; i++)
    {
        right_rotate_once(arr, size);
    }

    // Print array after rotation
    cout << "Array after rotation: ";
    printArray(arr, size);

    // Free dynamically allocated memory
    delete[] arr;

    return 0;
}

void right_rotate_once(int arr[], int size)
{
    int i, last;

    // Store last element of array
    last = arr[size - 1];

    for(i = size - 1; i > 0; i--)
    {
        // Move each array element to its right
        arr[i] = arr[i - 1];
    }

    // Copy last element of array to first
    arr[0] = last;
}

// Print the given array
void printArray(int arr[], int size)
{
    for(int i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

Problem 4: Print unique elements

Write a C++ program to print all the unique elements of an array.

Input

Input size: 5
Array elements: 5 2 3 3 4

Output

Unique elements: 5 2 4

Intuition

Very simple problem if you solved the last article! Why?
Because we already did a problem to find the frequency of all the array elements. Here also, we'll do the same thing and simply print those elements whose frequency is 1.
Refer the last article for a better understanding : )

Logic

  1. Input size and elements in array. Store it in some variable say size and arr.
  2. Find frequency of each element and store it in an array say freq.
  3. Print array elements with frequency 1 which is our required unique elements.

Try it yourself

Solution
#include <iostream>
using namespace std;

int main()
{
    int arr[100], freq[100];
    int size, i, j, count;

    /* Input size of array */
    cout << "Enter size of array: " << endl;
    cin >> size;

    /* Input elements in array */
    cout << "Enter elements in array: " << endl;
    for (i = 0; i < size; i++)
    {
        cin >> arr[i];

        /* Initially initialize frequencies to -1 */
        freq[i] = -1;
    }

    for (i = 0; i < size; i++)
    {
        count = 1;
        for (j = i + 1; j < size; j++)
        {
            /* If duplicate element is found */
            if (arr[i] == arr[j])
            {
                count++;

                /* Make sure not to count frequency of the same element again */
                freq[j] = 0;
            }
        }

        /* If frequency of the current element is not counted */
        if (freq[i] != 0)
        {
            freq[i] = count;
        }
    }

    /*
     * Print elements with frequency 1
     */
    cout << "Unique elements: ";
    for (i = 0; i < size; i++)
    {
        if (freq[i] == 1)
        {
            cout << arr[i] << " ";
        }
    }

    return 0;
}

Problem 5: Print duplicate elements

Write a C++ program to count and print the no. of duplicate elements in an array.

Input

Input size: 5
Array elements: 5 2 3 3 4 5

Output

Duplicate elements: 3 5

Intuition

Again a related question to the previous problem!

Only one change this time: Print all elements that has frequency > 1.

Logic

  1. Input size and elements in array. Store it in some variable say size and arr.
  2. Find frequency of each element and store it in an array say freq.
  3. Print array elements with frequency > 1 which are our required elements.

Try it yourself

Solution
#include <iostream>
using namespace std;

int main()
{
    int arr[100], freq[100];
    int size, i, j, count;

    /* Input size of array */
    cout << "Enter size of array: " << endl;
    cin >> size;

    /* Input elements in array */
    cout << "Enter elements in array: " << endl;
    for (i = 0; i < size; i++)
    {
        cin >> arr[i];

        /* Initially initialize frequencies to -1 */
        freq[i] = -1;
    }

    for (i = 0; i < size; i++)
    {
        count = 1;
        for (j = i + 1; j < size; j++)
        {
            /* If duplicate element is found */
            if (arr[i] == arr[j])
            {
                count++;

                /* Make sure not to count frequency of the same element again */
                freq[j] = 0;
            }
        }

        /* If frequency of the current element is not counted */
        if (freq[i] != 0)
        {
            freq[i] = count;
        }
    }

    /*
     * Print elements with frequency > 1
     */
    cout << "Duplicate elements: ";
    for (i = 0; i < size; i++){
        if (freq[i] > 1){
            cout << arr[i] << " ";
        }
    }

    return 0;
}

Arrays might seem simple and easy but there are a vast number of problems that could be created & solved. It has a variety of problems and that is why it is considered an essential topic of data structures & algorithms. We would be practicing way more complex and variety of problems in our DSA module. See you there again for a more brutal practice upon arrays🥊Till then keep learning : )