Array and String

Array

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

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 by Pankaj

• Wikipedia Sequence