Skip to main content

Arrays

Arrays: Getting hang of it

Ready for another exciting practice session!? Buckle up, gather your tools (pen & paper if required for dry run) and we'll start with the problems ๐Ÿš€

Problem 1: Insert element in array

Write a C++ program to insert an element in an array at the specified position.

Input

Input size of array: 5
Array elements: 10, 20, 30, 40, 50
Element to insert: 25
Position where to insert: 3

Output

Elements of array are: 10, 20, 25, 30, 40, 50

Intuition

Firstly, let's discuss the size of array that we are going to create. Till now, we created an array of the size as specified by the user but now since, we want to insert an element, we'll create an array of size + 1.

Now let's understand what position means in terms of array index. If you observe the sample input, the index for the input position is just position - 1 (this is because the index starts from 0 rather than 1). Example: Element insertion at position 3 means insertion at index 2 and so on.

Once the user has given the position input, first check that it's a valid position as in it's not negative or not greater than the size + 1 of array. If invalid, then simply return invalid position.

Now, if this has to be manually done then all the elements before the position would be the same and all the elements after the position would be moved forward by 1 place to make space at the position.

To achieve this, I'll run a loop on array starting from size and will go till position. Inside the loop we'll keep making arr[i] = arr[i-1]. Finally, after shifting all the required elements, place the input element num at the required position as arr[pos-1] = num.

Logic

  1. Input size and elements in array. Store it in some variable say size and arr.
  2. Input new element and position to insert in array. Store it in some variable say num and pos.
  3. To insert new element in array, shift elements from the given insert position to one position right. Hence, run a loop in descending order from size to pos to insert. The loop structure should look like for(i=size; i>=pos; i--).
    Inside the loop copy previous element to current element by arr[i] = arr[i - 1];.
  4. Finally, after performing shift operation. Copy the new element at its specified position i.e. arr[pos - 1] = num;

Try it yourself

Solution
#include <iostream>
using namespace std;

int main()
{
    int i, size, num, pos;

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

	/* Create array */
	int arr[size + 1];

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

    /* Input new element and position to insert */
    cout << "Enter element to insert: " << endl;
    cin >> num;
    cout << "Enter the element position: " << endl;
    cin >> pos;

    /* If position of element is not valid */
    if (pos > size + 1 || pos <= 0)
    {
        cout << "Invalid position! Please enter position between 1 to " << size;
    }
    else
    {
        /* Make room for new array element by shifting to right */
        for (i = size; i >= pos; i--)
        {
            arr[i] = arr[i - 1];
        }

        /* Insert new element at given position and increment size */
        arr[pos - 1] = num;
        size++;

        /* Print array after insert operation */
        cout << "Array elements after insertion: ";
        for (i = 0; i < size; i++)
        {
            cout << arr[i] << " ";
        }
    }

    return 0;
}

Problem 2: Delete element from array

Write a C++ program to delete an element from array at specified position.

Input

Input array elements: 10 20 30 40 50
Input position to delete: 2

Output

Array elements: 10, 30, 40, 50

Intuition

Similar to the last question, nothing needs to be done till the position pos from where the element needs to be removed. Also the equivalent index for given pos would be pos-1. Starting from this point, we would be iterating till the end of array and shift all elements to their previous positions by arr[i] = arr[i+1]. This would have removed the element and even filled the gap as we shifted all proceeding elements to the previous positions but what to do with the last position, it's not required anymore as we have already shifted to its previous position? I'll simply reduce the array size by 1 and voila! we have the updated array.

PS: Don't forget to check that the position provided by user is a valid position from 1 to size of array.

Logic

  1. Move to the specified location which you want to remove in given array.
  2. Copy the next element to the current element of array. Which is you need to perform array[i] = array[i + 1].
  3. Repeat above steps till last element of array.
  4. Finally decrement the size of array by one.

Try it yourself

Solution
#include <iostream>
using namespace std;

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

    /* Input size and elements in array */
    cout << "Enter size of the array: " << endl;
    cin >> size;

    int arr[size];

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

    /* Input element position to delete */
    cout << "Enter the element position to delete: " << endl;
    cin >> pos;

    /* Invalid delete position */
    if (pos < 0 || pos > size)
    {
        cout << "Invalid position! Please enter position between 1 to " << size;
    }
    else
    {
        /* Copy next element value to current element */
        for (i = pos - 1; i < size - 1; i++)
        {
            arr[i] = arr[i + 1];
        }

        /* Decrement array size by 1 */
        size--;

        /* Print array after deletion */
        cout << "Elements of array after delete are: ";
        for (i = 0; i < size; i++)
        {
            cout << arr[i] << " ";
        }
    }

    return 0;
}

Problem 3: Find frequency of each array element

Write a C++ program to input elements in array and find frequency of each element in array.

Input

array elements: 5, 10, 2, 5, 50, 5, 10, 1, 2, 2

Output

Frequency of 5 = 3
Frequency of 10 = 2
Frequency of 2 = 3
Frequency of 50 = 1
Frequency of 1 = 1

Intuition

I need to calculate frequencies of all elements of array. Now since there are so many elements and I need to calculate frequencies for each of them, I'll create another array freq that will store these frequencies for element at each index.

I'll run a loop as usual for (i = 0 to size) to iterate over array elements but how to keep track fo their frequencies? The frequency count of current element arr[i] is 1 i.e. that element itself. I now need to go to every other element of array and check if it's equal to the current element. If yes, then I'll increment this count. To achieve this I'll run another loop on j from i+1 to size and keep comparing it to arr[i].

After the inner loop finishes counting all the duplicates, you store the total count in the freq array for the current element. freq[i] = count. The outer loop continues to the next element, and the process repeats until all elements have been selected and their frequencies counted.

Now, I might have 3 1s in my array so do I need to calculate frequency 3 times? Needless right? So I'll calculate the frequency of 1 whenever I encounter it first and while comparing it with arr[j], I'll make the frequencies of all proceeding 1s as 0 in the freq array to mark it as already evaluated.

What will our freq array elements be initialized with? It can't be 0 as that's for different purposes, and values > 0 can be actual frequencies. So let's initialize it with -1 as anyway we'll update it eventually.

Logic

  1. Input size and elements in array from user. Store it in some variable say size and arr.
  2. Declare another array with same size as of input array size to store frequency of each array elements. Say freq will store frequencies of all array elements.
  3. To count frequency of each element we require two loops. One outer loop to select an array element. Second inner loop to find first duplicate element of the currently selected array element by outer loop. Run an outer loop from 0 to size. The loop structure must look like for(i=0; i<size; i++).
  4. Inside outer loop, initialize count variable with 1 to count total frequency of the currently selected array element.
  5. Run an inner loop to count total duplicates of currently selected array element. Run an inner loop from i + 1 to size. The loop structure should look like for(j = i + 1; j < N; j++).
  6. Inside inner loop, if duplicate element is found increment the frequency count of current array element. Which is if(arr[i] == arr[j]) then count++.
  7. After all duplicates has been counted. Store total duplicate count of current element in frequency array. Which is say freq[i] = count.
  8. Finally print freq array to get frequencies of each array element.

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 frequency of each element
     */
    cout << "Frequency of all elements of array: \n";
    for (i = 0; i < size; i++)
    {
        if (freq[i] != 0)
        {
            cout << arr[i] << " occurs " << freq[i] << " times\n";
        }
    }

    return 0;
}

Problem 4: Merge two arrays into one

Write a C++ program to input elements in two arrays and merge two arrays into a third array.

Input

first array elements: 1, 4, 6, 9, 15
second array elements: 2, 5, 8, 10

Output

Merged array in ascending order = 1, 2, 4, 5, 6, 8, 9, 10, 15

Intuition

Let my lazy mind get to work again xD Since the arrays are sorted, I'll iterate over both the arrays and simply keep adding the smaller element among the 2 arrays. So let's create 2 variables: index1 and index2, both set to 0. These variables keep track of the merged elements from the given two arrays individually.

Also, we need to create a merge_array that would store the merged elements from both the arrays and we would be returning in the output. Can you guess its size? Since it would contain all elements of both array1 and array2, it's size merge_size would be the summ of size of both the input arrays: size1 + size2.

Now run a loop for merge_array starting from 0 to merge_size something like for(merge_index=0; merge_index<merge_size; merge_index++). Inside the loop, we would perform our major task as said in the first para: compare the elements of both the arrays and add the smaller one.

If the element from the first array is smaller, you assign it to the current position in the merge_array and increment index1. Otherwise, you assign the element from the second array and increment index2.

After the loop, you've merged elements from both arrays up to the point where the smaller elements are exhausted in one of the arrays.

If there are remaining elements in either of the input arrays, you merge them into the merge_array after the loop. You might need two separate loops for this, checking if index1 or index2 is less than their respective sizes. If yes, then add the remaining elements in merge_array.

Understand with an example:

Array 1: 1, 2, 4
Array 2: 3, 5, 6, 14

Now index1 is at 0th index of array1 and index2 is at 0th index of array2.

  • Compare both elements on these indices: 1 < 3 so add 1 to merge_arrary and move index1 to 1st index.
  • Compare again: 2 < 5 so again add 2 to merge_array and move index1 to 2nd index. merge_index is also constantly moving as we are doing this inside the loop over merge_array. merge_index would be currently at 1st index.
  • merge_index would now be at 2nd index. Now compare 4 > 3 . So add 3 to merge_array and move index2 to 1st index.
  • 4 < 5 : add 4 to merge_array and index1 reaches the size1 of array1. But have we added all elements of both arrays to merge_array? No right. Elements of array2 are still left, so let's add them too.
  • Run a loop as while (index2 < size2). Keep adding array2 elements to merge_array and keep incrementing index2 & merge_index.

Logic

  1. Input size and elements in two arrays and store them separately in two array variables: say size1, arr1, size2, and arr2 store the size and elements of the first and second arrays, respectively.
  2. Create another array that will store the merged array with size merge_size = size1 + size2, say merge_array[merge_size].
  3. Initialize two variables index1 = 0 and index2 = 0. Both these variables will keep track of the total merged elements from the given two arrays individually.
  4. Run a loop from 0 to merge_size. The loop structure must look like for(merge_index = 0; merge_index < merge_size; merge_index++).
  5. Inside the loop, check for the smallest element in the two input arrays, which is if(arr1[index1] < arr2[index2]), then assign the element of the first array to the merge array, i.e., merge_array[merge_index] = arr1[index1] and increment index1. Otherwise, store merge_array[merge_index] = arr2[index2] and increment index2.
  6. After loop merge the remaining array elements if any.

Try it yourself

Solution
#include <iostream>
using namespace std;

int main()
{
    int size1, size2, merge_size;
    int index1, index2, merge_index;
    int i;

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

    int arr1[size1];

    /* Input elements in the first array */
    cout << "Enter elements in the first array: " << endl;
    for (i = 0; i < size1; i++)
    {
        cin >> arr1[i];
    }

    /* Input size of the second array */
    cout << "\nEnter the size of the second array: " << endl;
    cin >> size2;

    int arr2[size2], merge_array[size1 + size2];

    /* Input elements in the second array */
    cout << "Enter elements in the second array: " << endl;
    for (i = 0; i < size2; i++)
    {
        cin >> arr2[i];
    }

    merge_size = size1 + size2;

    /*
     * Merge two arrays in ascending order
     */
    index1 = 0;
    index2 = 0;
    for (merge_index = 0; merge_index < merge_size; merge_index++)
    {
        /*
         * If all elements of one array
         * are merged to the final array
         */
        if (index1 >= size1 || index2 >= size2)
        {
            break;
        }

        if (arr1[index1] < arr2[index2])
        {
            merge_array[merge_index] = arr1[index1];
            index1++;
        }
        else
        {
            merge_array[merge_index] = arr2[index2];
            index2++;
        }
    }

    /*
     * Merge remaining array elements
     */
    while (index1 < size1)
    {
        merge_array[merge_index] = arr1[index1];
        merge_index++;
        index1++;
    }
    while (index2 < size2)
    {
        merge_array[merge_index] = arr2[index2];
        merge_index++;
        index2++;
    }

    /*
     * Print merged array
     */
    cout << "\nArray merged in ascending order: ";
    for (i = 0; i < merge_size; i++)
    {
        cout << merge_array[i] << " ";
    }

    return 0;
}

Problem 5: Search in an array

Write a C++ program to input elements in array and search whether an element exists in array or not.

Input

size of array: 10
elements in array: 10, 12, 20, 25, 13, 10, 9, 40, 60, 5

Output

Element to search is: 25
Element found at index 3

Intuition

Suppose you are standing in front of a students queue and you have to search for Ritu in that entire queue. What I'll do is I'll start looking every student one by one and check if he/ she's Ritu or not. Once I see Ritu, I'll say that I found her! Similarly, we are going to search for the element here as well.

Let the element to search be num. I'll also create a variable found that can have two values 0 & 1 where value 0 indicates Not found and 1 indicates Found. Now obviously, the initial value of found would be 0.

I'll iterate over the array from 0 to size and keep checking if arr[i] = num. If yes, then make found as 1 and break from the loop.

Now after the loop simply check the value of found. If it's 1 then print Found at position i + 1. If the value is 0 then print Not found.

Note that we printed i+1 as we want the position of element and not the index.

Logic

  1. Input size and elements in array from user. Store it in some variable say size and arr.
  2. Input number to search from user in some variable say num.
  3. Define a flag variable as found = 0. I have initialized found with 0, which means initially I assumed that searched element does not exists in array.
  4. Run loop from 0 to size. Loop structure should look like for(i=0; i<size; i++).
  5. Inside loop check if current array element is equal to searched number or not. Which is if(arr[i] == num) then set found = 1 flag and terminate from loop. Since element is found no need to continue further.
  6. Outside loop if(found == 1) then element is found otherwise not.

Try it yourself

Solution
#include <iostream>
using namespace std;

int main()
{
    int size, i, num, found;

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

    int arr[size];

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

    cout << "Enter element to search: " << endl;
    cin >> num;

    /* Assume that the element does not exist in the array */
    found = 0;

    for (i = 0; i < size; i++)
    {
        /*
         * If the element is found in the array then raise the found flag
         * and terminate from the loop.
         */
        if (arr[i] == num)
        {
            found = 1;
            break;
        }
    }

    /*
     * If the element is found in the array
     */
    if (found == 1)
    {
        cout << "\n" << num << " is found at position " << i + 1;
    }
    else
    {
        cout << "\n" << num << " is not found in the array";
    }

    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 : )