Home DSA Part 6: Arrays
Post
Cancel

DSA Part 6: Arrays

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.

Time complexity

OperationT.C.
Access$O(1)$
Search$O(n)$
Insertion$O(n)$
Deletion$O(n)$

Dynamic Arrays

Automatically double up in size once the limit is exhausted.

  • Vector - C++
  • ArrayList - Java
  • List - Python

Avereage T.C. for insertion at end is $O(1)$.

Problems

Largest element in array

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.

1
2
3
4
5
6
7
8
9
int index(int arr[]){
  
  int res = 0;
  for(int i=1; i<n; i++)
    if(arr[i] > arr[res])
      res = i;
    
  return res;
}

Second Largest element

Given an array of integers, write a program that efficiently finds the second largest element present in the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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()

Implement is_sorted() for array of integers.

1
2
3
4
5
6
7
8
9
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;
}

Remove duplicate elements from sorted array

Given a sorted array arr[] of size N, delete all the duplicates elements from arr[].

1
2
3
4
5
6
7
8
9
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;
}

Rotate array

Given an array, rotate the array to the right by k steps, where k is non-negative.

1
2
3
4
5
6
  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());
  }
This post is licensed under CC BY 4.0 by the author.

Intro to ML Part 8: Preprocessing

Interview Prep: DBMS