Placement Practice | Arrays - I

In this series of the blog, we will learn about topics which are very very important in the placement point of view.

Introduction to Arrays

An array is a collection of items of similar data types stored at contiguous memory locations.

Which makes it easier to calculate the position of each element by simply adding an offset to a base value viz, the memory location of the first element of the array.

Note: The location of the next index depends on the data type we use.

Defining an Array:

Array definition constitutes the two things data type of the array elements and the size of the array. The size of the array is fixed and the memory for an array needs to be allocated before use, the size of an array cannot be increased or decreased dynamically.

Generally, they are declared as:

dataType arrayName[arraySize];

Distinguished from a normal variable by brackets [ ].

Accessing array elements:

We can access elements of an array through indexes also, it allows random access.

Suppose an array named arr stores N elements then indexes in the array are in the range of 0 to N-1.

Element present at ith index in the array can be accessed as arr[i],

Advantages of using arrays:

• Allows random access of elements.

• Better cache locality that can make a difference in performance

Examples:

// A character array in C/C++/Java

char arr1[] = {'p', 'r', 'o', 'g', 'r', 'a', 'm', 'm', 'e', 'r', 's'};

// An Integer array in C/C++/Java

int arr2[] = {100, 200, 300, 400, 500};

// Item at i'th index in array is typically accessed

// as "arr[i]".  For example arr1[4] gives us 'r'

// and arr2[3] gives us 400.

Searching in an array:

Searching an element in an array means to check if a given element is present in an array or not. This can be done by accessing elements of the array one by one starting from the first element and checking if any of the element matches with the given element.

We can use loops to perform the above operation of array traversal and access the elements using indexes.

Below is the algorithm to perform to the search operation in the given array.

for(i = 0; i < n; i++)
{
    if(arr[i] == key)
    { 
        print "Element Founded";
    }
    else
    {
        print "Element not Found";
    }
}

Time Complexity of this search operation will be O(N) in the worst case as we are checking every element of the array from 1st to last, so the number of operations is N.

---

Insertion and Deletion in Arrays

Insertion in Arrays:

Given an array of a given size. The task is to insert a new element in this array. There are two possible ways of inserting elements in an array:

1. Insert elements at the end of the array.

2. Insert elements at any given index in the array.

Special Case: A special case is needed to be considered is whether the array is already full or not. If the array is full, then the new element can not be inserted.

Consider the given array is arr[] and the initial size of the array is N, and the length of the array is len. That is, there is len number of elements already present in this array.

1) Insert an element P at the end in arr[]: The first step is to check if there is any space left in the array for the new elements. To do this check,

if(len < N)
     // space left
else
     // array is full

If there is space left for the new element, insert it directly at the end at position len + 1 and index Glen:

arr[len] = P;

Time Complexity of this insert operation is constant, i.e. O(1) as we are directly inserting the element in a single operation.

2) Insert an element P at the position, pos in arr[]: The first step is to check if there is any space left in the array for the new elements. To do this check,

if(len < N)
     // space left
else
     // array is full

Now, if there is space left, the element can be inserted. The index of the new element will be indx = pos - 1. Now, before inserting the element at the index indx, shift all elements from the index indx till the end of the array to the right by 1 place. This can be done as:

for(i = len-1; i >= indx; i--)
{
    arr[i+1] = arr[i];
}

After shifting the elements, place the element P at index indx.

arr[indx] = P;

Time Complexity in the worst case of this insertion operation can be linear i.e. O(N) as we might have to shift all of the elements by one place to the right.

Deletion in Arrays:

To delete a given element from an array, we will have to first search for the element in the array. If the element is present in the array then delete operation is performed for the element otherwise the user is prompted that the array does not contain the given element.

Consider the given array is arr[] and the initial size of the array is N, and the length of the array is len. That is, there is len number of elements already present in this array.

Deleting an element P from the array arr[]: Search the element P in the array arr[] to find the index at which it is present.

for(i = 0; i < N; i++)
{
    if(arr[i] == P)
        indx = i; return;
    else
        Element not Found;
}

Now, to delete the element present at index indx, left shift all of the elements present after indx by one place and finally reduce the length of the array by 1.

for(i = idx+1; i < len; i++)
{
    arr[i-1] = arr[i];
}
len = len-1;

Time Complexity in the worst case of this insertion operation can be linear i.e. O(N) as we might have to shift all of the elements by one place to the left.

---

Array Rotation

As the name suggests, array rotation means to rotate the elements of an array by given positions

Consider the array below :

[1, 2, 3, 4, 5]

The above array is rotated counter-clockwise or towards left by 2 elements, After rotation, the array will be:

[3, 4, 5, 1, 2]

So it looks like :

• Shift all elements after the K-th element to the left by K positions.

• Fill the K blank spaces at the end of the array by first K elements from the original array.

Note: A similar approach can be applied for clockwise rotation.

Implementations:

1) Simple Method: The simplest way to rotate an array is to implement the above visually observed approach by using extra space.

1. Store the first K elements in a temporary array say temp[].

2. Shift all elements after the K-th element to the left by K positions in the original array.

3. Fill the K blank spaces at the end of the original array by the K elements from the temp array.

Say, arr[] = [10, 20, 30, 40, 50, 60, 70], K = 3
1) Store first K elements in a temp array
   temp[] = [10, 20, 30]
2) Shift rest of the arr[]
   arr[] = [40, 50, 60, 70, 50, 60, 70]
3) Store back the K elements from temp
   arr[] = [40, 50, 60, 70, 10, 20, 30]

Time Complexity: O(N), where N is the number of elements in the array.

Space Complexity: O(K) where K is the number of places by which elements will be rotated.

2) Another Method (without extra space): We can also rotate an array by avoiding the use of a temporary array. The idea is to rotate the array one by one K times.

leftRotate(arr[], d, n)
start
  For i = 0 to i < d
    Left rotate all elements of arr[] by one
end

To rotate an array by 1 position to the left:

1. Store the first element in a temporary variable say, temp.

2. Left shift all elements after the first element by 1 position. That is, move arr[1] to arr[0], arr[2] to arr[1] and so on.

3. Initialize arr[N-1] with temp.

To rotate an array by K position to the left, repeat the above process K times.

Take the same example,

arr[] = [10, 20, 30, 40, 50, 60, 70], K = 2
Rotate arr[] one by one 2 times.

After 1st rotation: [20, 30, 4, 50, 60, 70, 10]
After 2nd rotation: [ 30, 40, 50, 60, 70, 10, 20]

Time Complexity: O(N*K), where N is the number of elements in the array and K is the number of places by which elements will be rotated.

Auxiliary Space: O(1).

---

Reversing an Array

It simply means reversing the order of elements in the given array.

Given an array of N elements. The task is to reverse the order of elements in the given array.

For Example:

Input  : arr[] = {10, 20, 30}
Output : arr[] = {30, 20, 10}

Input :  arr[] = {40, 50, 10, 20}
Output : arr[] = {20, 10, 50, 40}

There are two solutions to this problem viz Iterative and Recursive.

Iterative Solution:

• Method 1(Using Temporary Array): The idea is to first copy all of the elements of the given array in a temporary array. Then traverse the temporary array from the end and replace elements in the original array by elements of temp array. This method will take extra space in order of O(N).

• Method 2(Efficient): This method is efficient than the above method and avoids using extra spaces. We simply have to traverse array from both ends and keep swapping elements from both ends until the middle of the array is reached.

1) Initliazze start and end as
    start = 0, end = N-1
2) In a loop, swap arr[start] with arr[end] 
   and change start and end as follows:
       start++,
       end-- 

For example:

    [10, 20, 30, 40, 50, 60]
=>  [60, 20, 30, 40, 50, 10]
=>  [60, 50, 30, 40, 20, 10]
=>  [60, 50, 40, 30, 20, 10]

Time Complexity: O(N), where N is the number of elements in the array.

Recursive Solution:

The recursive approach is almost similar to that of the iterative solution

Below is the recursive algorithm to reverse an array:

1) Initialize start and end as 
   start = 0, end = n-1
2) Swap arr[start] with arr[end]
3) Recursively call reverse for rest of the array.

Below is the recursive function to reverse an array:

void reverse_Array(arr[], start, end)
{
    if(start >= end)
        return;
    //swap start and end
    temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;
    
    //Recursive function calling
    reverse_Array(arr, start + 1, end - 1);
}

Time Complexity: O(N), where N is the number of elements in the array.

---

Prefix Sum Array

The prefix sum array of an array, arr[] can be defined as an array of the same size say, prefixSumArray[] such that the value at any index i in prefixSumArray[] is the sum of all elements from indexes 0 to i in arr[].

Can be depicted as:

prefixSumArray[I] = arr[0] + arr[1] + arr[2] + . . . + arr[i]

for all 0 <= i <= N

Examples:

Input: arr[] = {100, 200, 100, 500, 1500}
Output: prefixSumArray[] = {100, 300, 400, 900, 2400}

Expalanation: While traversing the array, update the element by adding it with its previous element. 
prefixSumArray[0] = 100,
prefixSumArray[1] = prefixSumArray[0] + arr[1] = 300,
prefixSumArray[2] = prefixSumArray[1] + arr[2] = 400 and so on.

Function for prefix sum array for a given array arr[] of size N:

void p_Sum(int arr[], int N, int prefixSumArray[])
{ 
    prefixSum[0] = arr[0]; 
  
    // Adding present element with previous element 
    for (int i = 1; i < N; i++) 
        prefixSum[i] = prefixSum[i-1] + arr[i]; 
} 

Finding sum in Range:

Since the array prefixSumArray[i] stores the sum of all elements up to i.

Therefore, prefixSumArray[j] - prefixSumArray[i] will give :

//sum of elements up to j-th index - sum of elements up to i-th element
//this total sum will exclude the i-th element

//Therefor, for sum of elements in range [i, j]  by:
prefixSumArray[j] - prefixSumArray[i - 1]

The above formula will not work in the case when i = 0.

Therefore,

sumRange = prefixSumArray[j]  , if i = 0
otherwise,
sumRange=prefixSumArray[j] - prefixSumArray[i-1], if (i != 0)

Sample Problem: Consider an array of size N with all initial values as 0. Perform given 'm' add operations from index 'a' to 'b' and evaluate the highest element in the array. An add operation adds 10 to all elements from index a to b (both inclusive).

Example:

Input : n = 5 // We consider array {0, 0, 0, 0, 0}
        m = 3.
        a = 2, b = 4.
        a = 1, b = 3.
        a = 1, b = 2.
Output : 30

Explanation : 
After I operation -
A : 0 10 10 10 0

After II operation -
A : 10 20 20 10 0

After III operation -
A : 20 30 20 10 0

Highest element : 30

Solution using Prefix Sum:

1) Run a loop for 'm' times, inputting 'a' and 'b'.
2) Add 10 at index 'a' and subtract 10 from index 'b+1'.
3) After completion of 'm' operations, compute the prefix sum array.
4) Scan the largest element and we're done.

What we did was adding 10 at ‘a’ because this will add 10 to all elements while taking prefix sum array. Subtracting 10 from ‘b+1’ will reverse the changes made by adding 10 to elements from ‘b’ onward.

For better understanding :

After I operation -
A : 0 10 0 0 -10 
Prefix Sum Array : 0 10 10 10 0

After II operation -
A : 10 10 0 -10 -10
Prefix Sum Array : 10 20 20 10 0

After III operation -
A : 20 10 -10 -10 -10
Prefix Sum Array : 20 30 20 10 0

Final Prefix Sum Array : 20 30 20 10 0 

The highest element : 30

---

Implementing Arrays in C++ using STL

Arrays can also be implemented using some built-in classes available in the C++ Standard Template Library.

And we are discussing the most commonly used classes for implementing sequential lists or arrays:

• Vector

• List

Vector:

A vector in C++ STL is a class that represents a dynamic array. the benefits of vector over normal arrays are,

• We don't need to pass size as an additional parameter once we pass the vector.

• Vectors have many in-built functions for erasing an element, inserting an element, etc.

• Vectors support dynamic sizes, we don't need to initially specify the size of a vector. we will also resize a vector.

• There are many other functionalities vector provide.

Vectors are the same as dynamic arrays with the power to resize itself automatically when an element is inserted or deleted, with their storage being handled automatically by the container.

Vector elements are placed in contiguous storage in order that they will be accessed and traversed using iterators. In vectors, data is inserted at the end. Inserting at the end takes differential time, as sometimes there could also be a requirement of extending the array.

Removing the last element takes only constant time because no resizing happens. Inserting and erasing at the start or within the middle is linear in time.

To use vector include the below header file:

#include <vector>

Declaration:

vector <type_of_element> vector_name;

Here, type_of_element can be any valid C++ data type,
or containers like Pair, List, etc.

Some important and commonly used functions of Vector class are:

• begin() – Returns an iterator pointing to the first element within the vector.

• end() – Returns an iterator pointing to the theoretical element that follows the last element within the vector.

• size() – Returns the number of elements within the vector.

• capacity() – Returns the size of the storage space currently allocated to the vector expressed as a number of elements.

• empty() – Returns whether the container is empty.

• push_back() – It pushes the elements into a vector from the back.

• pop_back() – it is used to pop or remove elements from a vector from the back.

• insert() – It inserts new elements before the element at the required position.

• erase() – it is used to remove elements from a container from the required position or range.

• swap() – it is used to swap the contents of one vector with another vector of the same type and size.

• clear() – it is used to remove all the elements of the vector container.

• emplace() – It extends the container by inserting a new element at the position.

• emplace_back() – it is used to insert a new element into the vector container, the new element is added to the end of the vector.

C++ program to illustrate the above functions:

#include <iostream> 
#include <vector> 

using namespace std; 

int main() 
{ 
    vector<int> vcr; 
    
    // Push elements 
    for (int i = 1; i <= 5; i++) 
        vcr.push_back(i); 

    cout << "Size : " << vcr.size(); 
    
    // checks if the vector is empty or not 
    if (vcr.empty() == false) 
        cout << "\nVector is not empty"; 
    else
        cout << "\nVector is empty"; 

    cout << "\nOutput of begin and end: "; 
    for (auto i = vcr.begin(); i != vcr.end(); ++i) 
        cout << *i << " "; 
        
    // inserts at the beginning 
   vcr.emplace(vcr.begin(), 5); 
    cout << "\nThe first element is: " << vcr[0]; 
  
    // Inserts 20 at the end 
    vcr.emplace_back(20); 
    int n = vcr.size(); 
    cout << "\nThe last element is: " << vcr[n - 1]; 
  
    // erases the vector 
    vcr.clear(); 
    cout << "\nVector size after erase(): " << vcr.size();     

    return 0; 
}

Output:

Size : 5
Vector is not empty
Output of begin and end: 1 2 3 4 5 
The first element is: 5
The last element is: 20
Vector size after erase(): 0

List:

Lists are sequence containers that allow non-contiguous memory allocation. List in C++ STL implements a doubly linked list and not arrays. As compared to vector, the list has slow traversal, but once a position has been found, insertion and deletion are quick.

Normally, when we say a list, we mention doubly-linked lists. For implementing a singly linked list, we will use the forward_list class in C++ STL.

To use list include the below header file:

#include< list >

Declaration:

list< type_of_element > list_name;

Here, type_of_element can be any valid C++ data type, or containers like Pair, List, etc.

Some important and commonly used functions of List are:

• front() – Returns the value of the first element in the list.

• back() – Returns the value of the last element in the list.

• push_front(g) – Adds a new element ‘g’ at the beginning of the list.

• push_back(g) – Adds a new element ‘g’ at the end of the list.

• pop_front() – Removes the first element of the list, and reduces the size of the list by 1.

• pop_back() – Removes the last element of the list, and reduces the size of the list by 1.

• begin() and end() – begin() function returns an iterator pointing to the first element of the list.

• empty() – Returns whether the list is empty(1) or not(0).

• insert() – Inserts new elements in the list before the element at a specified position.

• reverse() – Reverses the list.

• size() – Returns the number of elements in the list.

• sort() – Sorts the list in increasing order.

C++ program to illustrate the above functions:

#include <iostream> 
#include <list> 
#include <iterator> 
using namespace std; 

//function for printing the elements in a list 
void showlist(list <int> g) 
{ 
    list <int> :: iterator itr; 
    for(itr = g.begin(); itr != g.end(); ++itr) 
        cout << '\t' << *itr; 
    cout << '\n'; 
} 

int main() 
{ 
    list <int> glist1, glist2; 

    for (int i = 0; i < 10; ++i) 
    { 
        glist1.push_back(i * 2); 
        glist2.push_front(i * 3); 
    } 
    cout << "\nList 1 (glist1) is : "; 
    showlist(gqlist1); 

    cout << "\nList 2 (glist2) is : "; 
    showlist(glist2); 

    cout << "\nglist1.front() : " << glist1.front(); 
    cout << "\nglist1.back() : " << glist1.back(); 

    cout << "\nglist1.pop_front() : "; 
    glist1.pop_front(); 
    showlist(glist1); 

    cout << "\nglist2.pop_back() : "; 
    glist2.pop_back(); 
    showlist(glist2); 

    cout << "\nglist1.reverse() : "; 
    glist1.reverse(); 
    showlist(glist1); 

    cout << "\nglist2.sort(): "; 
    glist2.sort(); 
    showlist(glist2); 

    return 0; 
} 

Output:

List 1 (glist1) is :     0    2    4    6    
8    10    12    14    16    18

List 2 (glist2) is :     27    24    21    18    
15    12    9    6    3    0

glist1.front() : 0
glist1.back() : 18
glist1.pop_front() :     2    4    6    8    
10    12    14    16    18

glist2.pop_back() :     27    24    21    18    
15    12    9    6    3

glist1.reverse() :     18    16    14    12    
10    8    6    4    2

glist2.sort():     3    6    9    12    
15    18    21    24    27

---

I hope you got to learn something. I will be covering more topics from Arrays. Till then try to implement the above learning.

Happy Coding!

Follow us on Instagram @programmersdoor

Join us on Telegram @programmersdoor

Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.

#blog #interview #placement #learn #computer #science