Foundations: measuring code · Lesson 3 of 23
Arrays and strings under the hood
What's fast and slow on arrays, and why building a string in a loop can be costly.
An array keeps its elements next to each other in memory. Knowing the index, the machine computes the address directly: O(1). Inserting at the front or in the middle means shifting everything after it one place: O(n).
nums =
nums[2] jumps straight to 9, but nums.unshift(0) must shift all five.
| Operation | Complexity |
|---|---|
arr[i], arr[i] = x | O(1) |
push, pop | O(1) amortized |
unshift, shift, splice(i, …) | O(n) |
includes, indexOf, find | O(n) |
slice, concat, [...arr] | O(n) (a new copy) |
sort | O(n log n) |
Strings are immutable
JavaScript strings are immutable: s[0] = "x" does nothing, and every + makes a new string. When building a large result piece by piece, collect the parts in an array and join once at the end.
To modify characters (say, reverse), turn the string into an array with [...s] and work on that.
// Reverse an array in place: two pointers swapping from both ends
function reverseInPlace(arr) {
let left = 0, right = arr.length - 1
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]]
left++
right--
}
return arr
}
console.log(reverseInPlace([1, 2, 3, 4, 5]))
console.log(reverseInPlace([..."stressed"]).join(""))- ▶const a = [1, 2, 3, 4]
- 2let l = 0, r = 3
- 3;[a[l], a[r]] = [a[r], a[l]]
- 4l++; r--
- 5;[a[l], a[r]] = [a[r], a[l]]
- 6console.log(a)
Variables
| a | [1, 2, 3, 4] |
Output
What's the output?
const nums = [3, 1, 2] const sorted = nums.sort() sorted.push(9) console.log(nums.length)
What will this code print?
Complete the code
Complete the function that moves every zero to the end in place, keeping the others in order.
function moveZeros(nums) { let write = 0 for (let read = 0; read < nums.length; read++) { if (nums[read] !== 0) { [nums[write], nums[read]] = [nums[read], nums[]] ++ } } return nums }
Exercise
Write isPalindrome(s) with two pointers from both ends (without reversing the string). It must print true false.
Expected output: true false
function isPalindrome(s) {
}
console.log(isPalindrome("racecar"), isPalindrome("seacode"))Practise on real problems
Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.
Learn more from
Played 0 of 3 games
Sign in to save your progress and earn XP.