🎯 By the end of this lesson you can…
- Explain how arrays sit in memory
- Know the cost of common array operations
- Modify arrays in place with a write pointer
A row of numbered seats
| Operation | Cost | Why |
|---|---|---|
read / write arr[i] | O(1) | the address is computed directly |
| push / pop at the end | O(1)* | no shifting (*amortised) |
| insert / delete at the front | O(n) | every item shifts |
| search for a value | O(n) | may check every item |
| search in a sorted array | O(log n) | binary search |
The write-pointer trick
Problem: remove every 0 from an array in place and return the new length.
remove-zeros.pseudo
1BEGIN2 SET NUMS = [0, 3, 0, 5, 7, 0]3 SET WRITE = 04 FOR READ = 0 TO LENGTH(NUMS) - 15 IF NUMS[READ] <> 0 THEN6 SET NUMS[WRITE] = NUMS[READ]7 SET WRITE = WRITE + 18 END IF9 END FOR10 DISPLAY WRITE11 DISPLAY NUMS12ENDRemove a value in place
1function removeValue(nums, val) {2 let write = 0;3 for (let read = 0; read < nums.length; read++) {4 if (nums[read] !== val) nums[write++] = nums[read];5 }6 return write;7}8const a = [3, 2, 2, 3, 4];9const k = removeValue(a, 3);10console.log(k, a.slice(0, k));1def remove_value(nums, val):2 write = 03 for read in range(len(nums)):4 if nums[read] != val:5 nums[write] = nums[read]6 write += 17 return write8 9a = [3, 2, 2, 3, 4]10k = remove_value(a, 3)11print(k, a[:k])✨ The logic didn’t change. Only the syntax changed.
💡 Concept check
Which operation is O(n) on an array?
🛠️ Move zeros to the end
Write moveZeros(nums) that moves all 0s to the end in place, keeping the order of the other numbers, and returns the array.
📌 Key takeaways
- Access by index is O(1); search is O(n).
- Insert/delete at the end is O(1); at the front or middle is O(n) (everything shifts).
- The "write pointer" trick removes items in place in O(n) time, O(1) space.
Finished reading & practising?
Saved in this browser. Create a free account to keep it forever.
