Array Traversal Problems

The problems every array round starts with

Part 4 is about arrays. An array is a list of values stored one after another, and each value has a position number called an index. Most interview questions use arrays. This first lesson collects the classic “warm-up” problems. Each one needs only one or two passes (a pass is one trip through the array from start to end). Each one also teaches a small technique you will use again: a write pointer, a reversal, XOR, or a merge-style walk.

A pointer here is just a variable that holds an index. It “points” at one place in the array, like a finger on a line of text.

Interviewers often add one rule: in place. In place means you change the array you were given, and you do not make a second big array. You may use only O(1) extra memory. O(1) means a small, fixed amount of memory (a few variables), however long the array is. This rule makes the problems interesting.

Largest, second largest, and is it sorted?

You have met the first two already: the “best so far” loop (Lesson 8) and the two-variable second largest (Lesson 11). Checking whether an array is sorted is the same kind of single pass. Compare each item with the one before it. One step down is enough to say “not sorted”:

function isSorted(nums) {  for (let i = 1; i < nums.length; i++) {    if (nums[i] < nums[i - 1]) return false;   // one step down is enough to fail  }  return true;}console.log(isSorted([1, 2, 2, 7])); // trueconsole.log(isSorted([1, 3, 2]));    // false

The read/write pointer pattern

Many in-place problems ask you to keep some items and drop the others. For these, use two pointers that move in the same direction:

• read looks at every item, one by one.
• write marks the place where the next kept item should go. It never gets ahead of read.

When read finds an item to keep, copy it to write, then move write forward by one. At the end, the first write positions hold the answer. This is the “same-direction” form of the two-pointer technique (Lesson 21).

Traced: removing duplicates in place

▶const nums = [1, 1, 2, 3, 3];2let write = 1;3for (let read = 1; read < nums.length; read++) {4  if (nums[read] !== nums[write - 1]) {5    nums[write] = nums[read];6    write++;7  }8}9console.log(write, nums.slice(0, write));

This takes one pass: O(n) time (the steps grow in line with the array length n) and O(1) space. If the array were not sorted, you would need a Set to know which values you have already seen. A Set is a collection that keeps each value only once and can tell you quickly whether it holds a value.

Moving zeros to the end

This uses the same pattern. Keep the non-zero values, in order, at the front. A swap exchanges two values. If you swap instead of copy, the zeros move to the back by themselves.

function moveZeroes(nums) {  let write = 0;  for (let read = 0; read < nums.length; read++) {    if (nums[read] !== 0) {      [nums[write], nums[read]] = [nums[read], nums[write]];      write++;    }  }  return nums;}console.log(moveZeroes([0, 1, 0, 3, 12])); // [ 1, 3, 12, 0, 0 ]

Rotating by k: the reversal method

Rotating right by k moves the last k items to the front. For example, [1, 2, 3, 4, 5, 6, 7] rotated by 3 is [5, 6, 7, 1, 2, 3, 4]. There are three ways to do it. Moving every item one step, k times, costs O(n × k). Copying into a new array costs O(n) time but also O(n) extra space. The reversal method needs only O(n) time and O(1) space. It uses three reversals:

function reverse(nums, i, j) {  while (i < j) {    [nums[i], nums[j]] = [nums[j], nums[i]];    i++;    j--;  }}function rotate(nums, k) {  const n = nums.length;  k %= n;                       // rotating by n changes nothing  reverse(nums, 0, n - 1);      // 1. reverse everything  reverse(nums, 0, k - 1);      // 2. reverse the first k  reverse(nums, k, n - 1);      // 3. reverse the rest  return nums;}console.log(rotate([1, 2, 3, 4, 5, 6, 7], 3)); // [ 5, 6, 7, 1, 2, 3, 4 ]

Missing number and single number (XOR)

Lesson 11 found the missing number with “expected sum minus actual sum”. Here is a related classic. Every value appears twice, except one value. Find that one. A frequency map (a Map that counts each value) works, but it needs O(n) space. For O(1) space, use XOR.

XOR (written ^ in JavaScript) is an operator that compares two numbers bit by bit. A bit is one binary digit, 0 or 1. For each bit, XOR gives 1 if the two bits are different and 0 if they are the same. You only need three facts about it:

console.log(5 ^ 5);          // 0   a value XOR itself is 0console.log(5 ^ 0);          // 5   XOR with 0 changes nothingconsole.log(4 ^ 1 ^ 4);      // 1   order does not matter; the pair of 4s cancelsfunction singleNumber(nums) {  let x = 0;  for (const v of nums) x ^= v;  return x;}console.log(singleNumber([4, 1, 2, 1, 2])); // 4

Now XOR all the values together. Every pair cancels to 0, and only the single value is left. Lesson 58 explains XOR on the individual bits in more detail.

Union of two sorted arrays

The union of two arrays holds every value that is in either array, each value once. If both arrays are sorted, walk through them together, like the merge step of merge sort (Lesson 17). Skip a value if it equals the last value you added:

function unionSorted(a, b) {  const out = [];  let i = 0, j = 0;  const add = (v) => { if (out[out.length - 1] !== v) out.push(v); };   // skip repeats  while (i < a.length && j < b.length) {    if (a[i] < b[j]) add(a[i++]);    else if (a[i] > b[j]) add(b[j++]);    else { add(a[i]); i++; j++; }  }  while (i < a.length) add(a[i++]);  while (j < b.length) add(b[j++]);  return out;}console.log(unionSorted([1, 2, 2, 4], [2, 3, 5])); // [ 1, 2, 3, 4, 5 ]

This takes O(n + m) time, where n and m are the two array lengths. The intersection (the values found in both arrays) works the same way. Add a value only when both front values are equal (Lesson 17, Question 4).

Practice questions

You can solve every question here in one or two passes. Aim for O(1) extra space when the question asks for it.

function removeDuplicates(nums) {  const unique = [...new Set(nums)];  for (let i = 0; i < unique.length; i++) nums[i] = unique[i];  return unique.length;}const a = [1, 1, 2];console.log(removeDuplicates(a), a.slice(0, 2)); // 2 [ 1, 2 ]

function removeDuplicates(nums) {  if (nums.length === 0) return 0;  let write = 1;  for (let read = 1; read < nums.length; read++) {    if (nums[read] !== nums[write - 1]) nums[write++] = nums[read];  }  return write;}const b = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4];const k = removeDuplicates(b);console.log(k, b.slice(0, k)); // 5 [ 0, 1, 2, 3, 4 ]

function removeElement(nums, val) {  let write = 0;  for (const x of nums) {    if (x !== val) nums[write++] = x;  }  return write;}const a = [0, 1, 2, 2, 3, 0, 4, 2];const k = removeElement(a, 2);console.log(k, a.slice(0, k)); // 5 [ 0, 1, 3, 0, 4 ]

function moveZeroes(nums) {  let write = 0;  for (const x of nums) if (x !== 0) nums[write++] = x;  while (write < nums.length) nums[write++] = 0;  return nums;}console.log(moveZeroes([0, 1, 0, 3, 12])); // [ 1, 3, 12, 0, 0 ]

function moveZeroes(nums) {  let write = 0;  for (let read = 0; read < nums.length; read++) {    if (nums[read] !== 0) {      [nums[write], nums[read]] = [nums[read], nums[write]];      write++;    }  }  return nums;}console.log(moveZeroes([0, 1, 0, 3, 12])); // [ 1, 3, 12, 0, 0 ]console.log(moveZeroes([0]));              // [ 0 ]

function rotate(nums, k) {  const n = nums.length;  const out = new Array(n);  for (let i = 0; i < n; i++) out[(i + k) % n] = nums[i];  for (let i = 0; i < n; i++) nums[i] = out[i];  return nums;}console.log(rotate([1, 2, 3, 4, 5, 6, 7], 3)); // [ 5, 6, 7, 1, 2, 3, 4 ]console.log(rotate([1, 2], 5));                // [ 2, 1 ]

function rotate(nums, k) {  const n = nums.length;  k %= n;  const rev = (i, j) => {    while (i < j) { [nums[i], nums[j]] = [nums[j], nums[i]]; i++; j--; }  };  rev(0, n - 1);  rev(0, k - 1);  rev(k, n - 1);  return nums;}console.log(rotate([1, 2, 3, 4, 5, 6, 7], 3)); // [ 5, 6, 7, 1, 2, 3, 4 ]console.log(rotate([-1, -100, 3, 99], 2));     // [ 3, 99, -1, -100 ]console.log(rotate([1, 2], 5));                // [ 2, 1 ]

function singleNumber(nums) {  const freq = new Map();  for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);  for (const [x, c] of freq) if (c === 1) return x;}console.log(singleNumber([4, 1, 2, 1, 2])); // 4

function singleNumber(nums) {  let x = 0;  for (const v of nums) x ^= v;  return x;}console.log(singleNumber([2, 2, 1]));       // 1console.log(singleNumber([4, 1, 2, 1, 2])); // 4

function check(nums) {  const n = nums.length;  let drops = 0;  for (let i = 0; i < n; i++) {    if (nums[i] > nums[(i + 1) % n]) drops++;  }  return drops <= 1;}console.log(check([3, 4, 5, 1, 2])); // trueconsole.log(check([2, 1, 3, 4]));    // falseconsole.log(check([1, 2, 3]));       // true

function unionSorted(a, b) {  return [...new Set([...a, ...b])].sort((x, y) => x - y);}console.log(unionSorted([1, 2, 2, 4], [2, 3, 5])); // [ 1, 2, 3, 4, 5 ]

function unionSorted(a, b) {  const out = [];  const add = (v) => { if (out[out.length - 1] !== v) out.push(v); };  let i = 0, j = 0;  while (i < a.length || j < b.length) {    if (j === b.length || (i < a.length && a[i] <= b[j])) add(a[i++]);    else add(b[j++]);  }  return out;}console.log(unionSorted([1, 2, 2, 4], [2, 3, 5])); // [ 1, 2, 3, 4, 5 ]console.log(unionSorted([], [1, 1]));              // [ 1 ]

Make it stick

What's next

Lesson 20 introduces the prefix sum. It is one extra array of running totals. With it, you can get the sum of any range of items almost instantly. It is the first pattern in this series that turns a whole group of O(n²) problems into O(n).