Dynamic Arrays - DSA Notes 📝

🎯 Learning Goal

• What are the characteristics of dynamic arrays?
• What are the time complexities of dynamic arrays?

🧠 Key Concepts (aka My Notes)

Dynamic Arrays

• Can grow as elements are added.
• Different languages have different default array size (Java = 10 and C# = 4)

Insertion at end (Pushing)

• End Pointer (or length) is important!
• Insert a value at arr[length] and resize if length >= capacity

# Insert n in the last position of the array
def pushback(self, n):
    if self.length == self.capacity:
        self.resize()

    # insert at next empty position
    self.arr[self.length] = n
    self.length += 1

⌚ Amortized Time Complexity is O(1)

This is amortized, meaning it's the average time taken for a sequence of pushing operations.

The resizing only happen when the array runs out of size, which does not happen on every push.

This is the same for deleting at end (popping)

Resizing

• Copy the values to a new static array which is 2x the size
• Deallocate the old array when everything has been copied over

def resize(self):
    # Create new array of double capacity
    self.capacity = 2 * self.capacity
    newArr = [0] * self.capacity 

    # Copy elements to newArr
    for i in range(self.length):
        newArr[i] = self.arr[i]
    self.arr = newArr

⌚ Time Complexity for resize is O(n)

🤔 Analyzing Time Complexity

• Analyzing means we consider the sum of all operations

For example, to go from array of size 1 to size 8 requires 15 operations. Array operations went from 1 -> 2 -> 4 -> 8 (Don't forget to count the resizing as 1 extra operation.)

The last term is always greater than the sum of all the terms before it. (1+ 2 + 4 < 8).

The formula is that for any array size n, it will take at most 2n operations. (15 > 2 . 8)

Constants are dropped in time complexity analysis.

That's why resizing time complexity is O(n),

⌚ Time Complexity for Dynamic Arrays

Essentially the same as Static Arrays.

💪 LeetCode Problems

• 1929. Concatenation of Array (Link)