Data Structure - Arrays
Published: 2021-02-09 14:09:29

Summarizing Data Structure series from [Leetcode](https://leetcode.com/explore/)

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**.  <br/>
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 <br>

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) or right(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.