Thread by @swapnakpanda

All you would like to know about

✪ Array Data Structure
✪ Array Operations
✪ Array Based Problems

* Time and Space Complexities covered

DSA Series: 🧵 👇

We will cover

1️⃣ Introduction
2️⃣ Array Size
3️⃣ Array Index
4️⃣ Array Dimension
5️⃣ Array Operations
6️⃣ Other Array-based Data Structures
7️⃣ Some Array-based Problems

1️⃣ Introduction

An array is a "collection of items" stored at contiguous memory locations.

Syntax: All items are written comma-separated inside square brackets.

Example: [1, 2, 3, 4, 5]

There are total 5 items in the array. 1 is the first item, 2 is the 2nd and 5 is the last.

2️⃣ Array Size

The total number of items contained in an array defines its size.

There are 2 types of Arrays wrt its size. Static Sized and, Dynamic Sized.

++

✪ Static Sized
These arrays are initialised with a size which can never be changed. If array is full, no new item can be inserted until any existing item is removed.

✪ Dynamic Sized
When a dynamic sized array is full, while inserting a new item, size is increased.

3️⃣ Array Index

An item in the array can be accessed "directly" by using an index (an integer).

Each array has a "base index" which is used to access the first item in the array.

++

Index of an item is calculated by adding an "offset" to the base index.

Offset indicates how far an item is from the very first item in the array. 1 item far means offset is 1, 10 items far means offset is 10.

4️⃣ Array Dimension

If items of an array are non-arrays, its dimension is 1.
If items are arrays, its dimension is (child array dimension + 1).

Example: [[1,2,3],[4,5,6]] is a 2-dimensional array.

Items are accessed using 2 indices.

Example: array[1][2]

5️⃣ Array Operations

5️⃣.1️⃣ Get
5️⃣.2️⃣ Insert/Update
5️⃣.3️⃣ Remove
5️⃣.4️⃣ IsEmpty
5️⃣.5️⃣ Search
5️⃣.6️⃣ Sort

5️⃣.1️⃣ Get

Getting an item in an array is straightforward. Index of the item is used to fetch it directly.

Example: array[1] fetches an item at Index "1"

Time Complexity: O(1)

5️⃣.2️⃣ Insert/Update

If no item is already existing at an index, attempting to store an item at that index is known as "Insert". Or else it's an "Update" operation.

Example: array[2] = 5

Here item "5" is inserted/updated at index "2" of array.

Time Complexity: O(1)

5️⃣.3️⃣ Remove

When an item at an index is removed from array, that place becomes empty.

Example: delete array[1]

Time Complexity: O(1)

5️⃣.4️⃣ IsEmpty

It checks if no items are present in the entire array.

To do this, we traverse through entire array starting from the base index and continue till the last index.

If an item is found at any index, this operation returns "false". Else "true"

Time Complexity: O(n)

5️⃣.5️⃣ Search

To search for an item in an array, array has to be traversed. There are 2 popular search techniques. Both of these will be discussed in separated threads.

5️⃣.5️⃣.1️⃣ Linear Search
Time Complexity: O(n)

5️⃣.5️⃣.2️⃣ Binary Search
Time Complexity: O(log n)

5️⃣.6️⃣ Sorting

Sorting (or ordering) is done to keep items of an array is a specific order (increasing, decreasing or, custom defined)

There are many sorting techniques and each will be discussed in upcoming threads. Here, we will highlight their time and space complexities.

++

5️⃣.6️⃣.1️⃣ Bubble Sort
Time: Best O(n), Worst O(n²), Avg O(n²)
Space: O(1)

5️⃣.6️⃣.2️⃣ Selection Sort
Time: Best O(n²), Worst O(n²), Avg O(n²)
Space: O(1)

5️⃣.6️⃣.3️⃣ Insertion Sort
Time: Best O(n), Worst O(n²), Avg O(n²)
Space: O(1)

++

5️⃣.6️⃣.4️⃣ Merge Sort
Time: Best O(nlogn), Worst O(nlogn), Avg O(nlogn)
Space: O(n)

5️⃣.6️⃣.5️⃣ Quick Sort
Time: Best O(nlogn), Worst O(n²), Avg O(nlogn)
Space: O(logn)

5️⃣.6️⃣.6️⃣ Counting Sort
Time: Best O(n), Worst O(n), Avg O(n)
Space: O(max)

++

5️⃣.6️⃣.7️⃣ Radix Sort
Time: Best O(n), Worst O(n), Avg O(n)
Space: O(max)

5️⃣.6️⃣.8️⃣ Bucket Sort
Time: Best O(n), Worst O(n²), Avg O(n)
Space: O(n)

++

5️⃣.6️⃣.9️⃣ Heap Sort
Time: Best O(nlogn), Worst O(nlogn), Avg O(nlogn)
Space: O(1)

5️⃣.6️⃣.1️⃣0️⃣ Shell Sort
Time: Best O(nlogn), Worst O(n²), Avg O(nlogn)
Space: O(1)

6️⃣ Other Array based Data Structures

✪ Stack
✪ Queue
✪ Dequeue
✪ Priority Queue

7️⃣ Array based Problems

✪ Rotating an Array
✪ Split an array and attach the first part after the second part
✪ Rearrange an array (based on array value, index etc)
✪ Find kth maximum and minimum item
✪ Find mean, median and mode
✪ Find number of occurrences of an item

We have come to the end of the very first thread of DSA series. I hope you enjoyed going through it.

Share your feedbacks. Like and Retweet the very first tweet to support and encourage me.

Follow @swapnakpanda to receive more threads from DSA series.

See you soon 👋