Leetcode practice notes

Arrays

• Stored contiguously in RAM (eg: ints in 4 byte chunks, chars in 1 byte)
• Reading and writing values (via index) is instant → Constant time operation i.e. O(1)
• Time complexity (O) refers to worst case. e.g.: Inserting an element in the middle of static array may require us to move ALL the elements by one index. So we generalize to O(n), i.e. n operations for n elements.
• Static arrays
  • Static → fixed size, writing limited by size
  • r/w ith element → O(1)
  • Insert/remove end → O(1)
  • Insert middle → O(n)
  • Remove middle → O(n)