Data Structure - Arrays

Summarizing Data Structure series from Leetcode

Information specific to Java

1. Arrays

1.1 1D Arrays

Stores a collection of elements sequentially. Elements can be accessed randomly since each element in the array can be identified by an array index.

Analogy: like a DVD box

• fixed size
• items stored contiguous (neighbouring) locations
• items of same type

Array size declared when you instantiate it. Computer will reserve memory for the entire array, memory cant be used in the meantime. e.g. So you shouldn't create an array of 100000 spaces if you are only expecting ~30 items.

• Fixed capacity
  • must specify size of array when you instantiate it
• can be one-dimensional or multi-dimensional

Default values

• Java instantiates array slots as null.
• Java fills unused int Array slots with 0.

Operations

1. Writing elements
   array[i]="value"
   If array has item at index 3, and another item inserted at same index. item will be overwritten.

2. Reading elements
   System.out.println(array[i])

3. Loop through array
   for (int i = 0; i < array.length; i++) { }
for (int value: array) {}

Capacity VS Length

• Capacity: how many items can the array hold? int capacity = array.length
• Length: how many items are in the array?

int length = 0;
for (int i = 0; i < 3; i++) {
    array[i] = i;
    length++;
}

In Java, array.length gives array's capacity.

To get length, user must keep track of it themselves (eg. in for loop, increment variable).

Basic array operations

1. Insert - new value at specific location
2. Delete - remove value
3. Search

Insertion

1. Insert at end

1. always know index of last element (always keep track of length)
2. insert value one index down from length

int intArray = new int[6];
int length = 0;

for (int i = 0; i < 3; i++) {
    intArray[length] = i;
    length++;
}

// insert at end
intArray[length] = 10;
// update length
length++;

2. Insert at start

Complexity: O(N)

1. shift all elements to the right by 1 index
2. insert value in index 0

for (int i = 3; i >= 0; i--) {
   intArray[i + 1] = intArray[i];
}
intArray[0] = value

3. Insert anywhere

1. Shift all elements from that index onwards one position to the right.
2. insert value at desired index

// insert value at index 2
for (int i = 4; i >= 2; i--)
{
    // shift elements to the right 
   intArray[i + 1] = intArray[i];
}
// insert value
intArray[2] = 30;

Deletion

1. Delete first element

Complexity: O(N)

1. delete element at index 0
2. shift all elements to the left

special case of deleting element at any index

// Shift each element one position to the left
for (int i = 1; i < length; i++) {
    int_array[i - 1] = int_array[i];
}

// reduce length tracking variable by 1
length--;

2. Delete last element

1. keep track of array length
2. delete element at index (length-1)

int length = 0;

for(int i = 0; i < 6; i++) {
    intArray[length] = i;
    length++; // keep track of length
}

// delete last element
length--;

last element is "deleted" by allowing it to be overwritten

3. Delete anywhere

Complexity: O(N)

1. delete element at index
2. shift all elements to right of index one position to the left (to fill up vacancy)

// delete the element at index 1, shift each element 1 position to left
for (int i = 2; i < length; i++) {
    int_array[i - 1] = int_array[i];
}

// update array length
length--;

Search

1. Linear Search

Complexity: O(N)

• index not known
• search every array entry

for (int i = 0; i < length; i++) {
        if (array[i] == element) {
            return true;
        }
    }

2. Binary Search

Complexity: O(log n)

• array elements are in sorted order
• look in middle array, then decide to look left(array[i]element)

In Place Array Operations

modifies the input array. NO new array is created.

In place array operations minimize space complexity , however the input data is overwritten / modified therefore other functions can no longer access original data

1. Two-Pointer technique

Involves 2 pointers in an array. often used for
searching for pairs in a sorted array

two decide which sub-strategy of two pointer to use

Determine the movement strategy of both pointers

1. Slow & fast runner / Read & write pointer (same direction)

one slow runner & the other fast runner

Eg. remove duplicates from sorted array

• slow runner (write pointer - tells array where to override next) NEVER gets ahead of fast runner (read pointer - reading values in array). So user can never overwrite element that has not been read.

2. beginning & end pointer (different direction)

One pointer start from beginning of list the other starts from the end of the list.

Eg. reverse characters in string

Other Techniques

• Two pointer technique
  • same direction
  • other direction
  • fixed width
• Circular Array

1.2 Dynamic Arrays

random access list data with variable size

• random access
• variable size

Java implementation: ArrayList

1.3 2-Dimensional array

sequence of elements. The elements can be laid out in a rectangular grid rather than a line.

Java Implementation:
one-dimensional array which containing M elements, each of which is an array of N integers.
int[M][N]
int[row][column]

Related stuff

a. Simliar data structures but different properties

1. string
2. Hash Table
3. Linked List
4. Queue
5. Stack

b. Searching algorithms & complexity

1. Binary Search

c. Two-pointer technique - can be used to solve

1. fast & slow pointer in linked lsit
2. slide window
3. will sometimes relate to greedy algorithm -> helps design pointer's movement strategy.