1. Arrays and Strings
Arrays
•
meaning of ‘Array’ differs between languages
◦
Python → lists, C++ → std::vector
•
size of an array can’t be modified(resized) but in the context of algorithm problems, arrays refer to dynamic arrays.
String
•
string are implemented differently between languages
◦
Python, Java → strings are immutable
◦
C++ → strings are mutable
immutable vs mutable
•
immutable : a type of data that cannot be changed
•
mutable : a type of data that can be changed
if you want to change immutable string s = ‘abc’ to ‘abd’, you have to create it entirely from scratch!
→ you cannot dos[2] = ‘d’to change it to ‘abd’
Time complexity of array and string operations
Operation | Array/List | String(Immutable) |
Append to end | O(1) | O(n) |
Pop from end | O(1) | O(n) |
Inserting (not from end) | O(n) | O(n) |
Deleting (not from end) | O(n) | O(n) |
Modify an element | O(1) | O(n) |
Random access | O(1) | O(1) |
Checking if element exists | O(n) | O(n) |
