Array and String

Array

int[] sequence = new int[10];

Wow, it's good to be back. The first time that I wrote this line was about 5 years ago. It's still the same line but my understanding of it has changed dramatically over the past 5 years.

• 2011 - A long rectangular box that holds 10 numbers
• 2012 - This long rectangular box weirdly starts at index 0
• 2013 - 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$
• 2014 - sequence is a pointer stored in the stack memory
  • It points the real object in the array that is stored in the heap space
• 2015 - sequence is in fact a memory address (for index 0)
  • sequence[1] is also an address that is 4 bytes (32 bit depending on the type) away from sequence.
• 2016 - 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}$.

"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.

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
• 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
  • Minimum Window Substring
  • Minimum Size Subarray Sum

References

• Stack Memory vs Heap Space by Pankaj
• Wikipedia Sequence