> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/array_and_string.md).

# Array and String

## Array

```java
int[] arr = new int[10];
```

Wow, it's good to be back. It's still the same line as I wrote it years ago, but my understanding has shifted as I progress in the math journey.

* A long rectangular box that holds 10 numbers
* This long rectangular box weirdly starts at index 0  
* This long rectangular box can only be so long
  * later discovered the max range is $$0$$ \~ $$2^{31} - 1$$ 
  * because 32-bit signed integer in 2's complement representation has range from $${-2}^{31}$$ to $$2^{31}-1$$ 
* `arr`  is a pointer stored in the stack memory 
  * It points the real object in the array that is stored in the heap space
* `arr` is in fact a memory address (for index 0)
  * `arr[1]` is also an address that is 4 bytes (32 bit depending on the type) away from `arr`.
* Array is just a CS way to express the more general mathematical idea - finite sequence - a real-valued function whose domain is finite subset of $$\mathbb{N}$$.
* Arrays are a convenient way to represent vectors and matrices from linear algebra.

"In computer science, finite sequences are sometimes called strings, words or lists, the different names commonly corresponding to different ways to represent them in computer memory."

Picture for memory address

Picture for heap/stack memory

## Runtime

O(1) look up\
O(n) insert, delete

## ArrayList

But we can use arraylist, double its size when it's full.

Amortized Analysis TBD

O(1) insert

## Types of Array Questions

* Math (w/ for loop)
  * move zeroes (1D)
  * rotate image (2D)
* Hashing
  * 2 Sum
* Sorted Array
  * Merge Sorted Array
  * Median of Two Sorted Arrays
* Rotated Array
  * Rotate array
  * Reverse array
  * Search in rotated array
* Subarray
  * Maximum Subarray

## String

```java
String str = "foo";
char[] str = {'f', 'o', 'o'};
```

String is just an array of characters.

## Types of String Questions

* StringBuffer ex. reverse words
* Substring ex. strStr
* Two Pointers ex. palindrome

## String Buffer

String is immutable in java. So str.append() will actually cost O(n) because you have create a new String object to hold all the new content. We can use a mutable option StringBuffer if we need to make frequent changes (for example append()).

## Two Pointers

* Left/Right pointers
  * 3 Sum
  * Valid Palindrome
* Fast/slow pointers
  * Linked List Cycle
  * Find the Middle of Linked List
* Window
  * Window Sum
* * Minimum Window Substring
  * Minimum Size Subarray Sum

## References

* [Stack Memory vs Heap Space](http://www.journaldev.com/4098/java-heap-space-vs-stack-memory) by Pankaj  
* Wikipedia [Sequence](https://en.wikipedia.org/wiki/Sequence)