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, 45Output
Second largest element: 45Intuition
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
- Input size and elements in array, store it in some variable say
sizeandarr. - Declare two variables
max1andmax2to store first and second largest elements. Store minimum integer value in both i.e.max1 = max2 = INT_MIN. - Iterate though all array elements, run a loop from 0 to
size - 1. Loop structure should look likefor(i=0; i<size; i++). - 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 = max1andmax1 = arr[i]. - Else if the current array element is greater than
max2but less thanmax1then make current array element as second largest i.e.max2 = arr[i].
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: 2Output
Array elements: 30, 40, 50, 10, 20Intuition
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
- Read elements in an array say arr.
- Read number of times to rotate in some variable say N.
- 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.
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;
}
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: 2Output
Array elements: 40, 50, 10, 20, 30Intuition
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
- Read elements in an array say arr.
- Read number of times to rotate in some variable say N.
- 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.
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 4Output
Unique elements: 5 2 4Intuition
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
- Input size and elements in array. Store it in some variable say
sizeandarr. - Find frequency of each element and store it in an array say
freq. - Print array elements with frequency 1 which is our required unique elements.
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 5Output
Duplicate elements: 3 5Intuition
Again a related question to the previous problem!
Only one change this time: Print all elements that has frequency > 1.
Logic
- Input size and elements in array. Store it in some variable say
sizeandarr. - Find frequency of each element and store it in an array say
freq. - Print array elements with frequency > 1 which are our required elements.
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 : )