What are arrays, strings?
EasyContiguous memory, 0-based indexing
Problem
An array stores a fixed-size sequence of same-type values in contiguous memory, accessed by a 0-based index. A string is essentially an array of characters. Both let you loop over elements with an index.
An array is a row of numbered boxes; a string is a row of letters.
The idea
An array is a block of same-type values laid out back to back in memory, so element i sits at a fixed offset from the start — that is why indexing is O(1) and why the size is fixed. A string is the same idea specialised to characters, which is why almost every array technique transfers straight to strings.
The trick
- Indices run 0 to n-1; the single most common bug in this whole subject is touching a[n].
- Reading or writing any element is O(1); inserting or deleting in the middle is O(n) because everything after must shift.
- Because a string is just an array of characters, two pointers, sliding windows and frequency counts all apply unchanged.
Step 1 of 7. Five values in one block of memory. The first one lives at index 0, not 1. Values: 3, 1, 4, 1, 5. length 5.
1int a[5] = {3, 1, 4, 1, 5}; // a[0]..a[4]2string s = "code"; // s[0]='c', s.size()=43for (int i = 0; i < 5; i++) print(a[i]);Input
- array
- [3, 1, 4, 1, 5]
Memory
- i
- —
- length
- 5
- i
- —
- a[i]
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- a = [7, 2, 9]; a[1]
- Output:
- 2
- Explanation:
- Indexing starts at 0, so a[1] is the second box. The lookup is one jump, not a walk, because the boxes sit side by side in memory.
Example 2
- Input:
- s = "cat"; s[0], s.length
- Output:
- 'c', 3
- Explanation:
- A string is an array of characters, so everything you know about arrays applies to it.
Finished the walkthrough? Add it to your streak.