Array is a continuos block of memory. We use an ‘index’ to access $i^{th}$ element of the array. In most of the programming languages indexing start from 0.
| Operation | T.C. |
|---|---|
| Access | $O(1)$ |
| Search | $O(n)$ |
| Insertion | $O(n)$ |
| Deletion | $O(n)$ |
Automatically double up in size once the limit is exhausted.
Avereage T.C. for insertion at end is $O(1)$.
Given an array of integers, write a program that efficiently finds the largest element present in the array. Given an array return the index of the largest element.
int index(int arr[]){
int res = 0;
for(int i=1; i<n; i++)
if(arr[i] > arr[res])
res = i;
return res;
}
Given an array of integers, write a program that efficiently finds the second largest element present in the array.
int index(int arr[], int n){
int res = -1, largest = 0;
for(int i=1; i<n; i++)
if(arr[i] > arr[largest])
{
largest = i;
res = largest;
}
else if(arr[i] < arr[largest])
if(res == -1 || arr[i] > arr[res])
res = i;
return res;
}
Implement is_sorted() for array of integers.
bool is_sorted(int a[], int size){
if(size == 0 || size == 1) return true;
for(int i=1; i<size; i++)
if(a[i] < a[i-1])
return false;
return true;
}
Given a sorted array arr[] of size N, delete all the duplicates elements from arr[].
int remove_duplicate(int arr[],int n){
int index = 1;
for(int i=1; i<n; i++)
if(arr[i] != arr[i-1])
arr[index++] = arr[i];
return index;
}
Given an array, rotate the array to the right by k steps, where k is non-negative.
void rotate(vector<int>& nums, int k) {
k %=nums.size();
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin()+k);
reverse(nums.begin()+k, nums.end());
}