Lesson 3: Programs 11-15: Arrays

How to use this lesson. Read the question and try it yourself for ten minutes before you read the approach. In a real interview, say your idea out loud, mention the edge cases (empty input, one item, duplicates, negative numbers), then code, then test with an example.

Problem 11: Two Sum

Question. Given an array of numbers and a target, return the positions of two numbers that add up to the target (or null).

Examples.

• [2, 7, 11, 15], target 9 → [0, 1]

Approach. Checking every pair is O(n squared). Instead, as you walk through the array, ask: have I already seen the number that completes this one (target - x)? A Map from value to position answers that in O(1).

function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return null;
}

console.log(twoSum([2, 7, 11, 15], 9));
console.log(twoSum([3, 2, 4], 6));
console.log(twoSum([3, 3], 6));
console.log(twoSum([1, 2], 10));
console.log(twoSum([], 0));

Output:

[ 0, 1 ]
[ 1, 2 ]
[ 0, 1 ]
null
null

Complexity. O(n) time, O(n) space.

Follow-up an interviewer may ask. What if the array is sorted and you must use O(1) space? (Two pointers moving inward.)

Problem 12: Find the Second Largest Number

Question. Return the second largest distinct value in an array, or null if there is not one.

Examples.

• [10, 5, 20, 20, 8] → 10
• [5, 5] → null

Approach. Sorting works but costs O(n log n). One pass is enough: keep the largest and the second largest so far. Skip values equal to the largest so duplicates do not count. (A trap: Math.max() of an empty array is -Infinity, so do not use it as a starting value if negative numbers are allowed.)

function secondLargest(nums) {
  let largest = null, second = null;
  for (const x of nums) {
    if (largest === null || x > largest) {
      second = largest;
      largest = x;
    } else if (x !== largest && (second === null || x > second)) {
      second = x;
    }
  }
  return second;
}

for (const data of [[10, 5, 20, 20, 8], [5, 5], [1, 2], [7], [], [-3, -1, -2], [4, 4, 3]]) {
  console.log(JSON.stringify(data), "->", secondLargest(data));
}

Output:

[10,5,20,20,8] -> 10
[5,5] -> null
[1,2] -> 1
[7] -> null
[] -> null
[-3,-1,-2] -> -2
[4,4,3] -> 3

Complexity. O(n) time, O(1) space.

Follow-up an interviewer may ask. How would you find the k-th largest? (A min-heap of size k, or sort and index when n is small.)

Problem 13: Maximum Subarray Sum (Kadane's Algorithm)

Question. Find the largest sum of any contiguous part of an array of integers.

Examples.

• [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6 (the part [4, -1, 2, 1])

Approach. Walk through the array keeping the best sum of a subarray ending here. At each number either extend the previous subarray or start fresh, whichever is bigger: current = Math.max(x, current + x). The answer is the largest value seen. This is Kadane's algorithm.

function maxSubarray(nums) {
  let best = nums[0], current = nums[0];
  for (let i = 1; i < nums.length; i++) {
    current = Math.max(nums[i], current + nums[i]);
    best = Math.max(best, current);
  }
  return best;
}

console.log(maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
console.log(maxSubarray([5]));
console.log(maxSubarray([-3, -1, -2]));
console.log(maxSubarray([1, 2, 3]));

Output:

6
5
-1
6

Complexity. O(n) time, O(1) space.

Follow-up an interviewer may ask. How do you also return which subarray it is? (Track the start index when you restart, and the best start and end.)

Problem 14: Flatten a Nested Array

Question. Turn an array that contains arrays (to any depth) into one flat array.

Examples.

• [1, [2, [3, [4]], 5]] → [1, 2, 3, 4, 5]

Approach. The built-in is arr.flat(Infinity). In an interview you are usually asked to write it yourself: go through the items; if an item is an array, flatten it recursively, otherwise keep it. reduce with spread keeps it short.

function flatten(arr) {
  return arr.reduce((flat, item) => (Array.isArray(item) ? flat.concat(flatten(item)) : flat.concat(item)), []);
}

function flattenIterative(arr) {
  const stack = [...arr], out = [];
  while (stack.length) {
    const item = stack.pop();
    if (Array.isArray(item)) stack.push(...item);
    else out.push(item);
  }
  return out.reverse();
}

console.log(flatten([1, [2, [3, [4]], 5]]));
console.log(flatten([]), flatten([[], [[]], [1]]));
console.log(flattenIterative([1, [2, [3, [4]], 5]]));
console.log([1, [2, [3, [4]], 5]].flat(Infinity));

Output:

[ 1, 2, 3, 4, 5 ]
[] [ 1 ]
[ 1, 2, 3, 4, 5 ]
[ 1, 2, 3, 4, 5 ]

Complexity. O(n) time for n items in total. The recursive version uses O(d) stack for nesting depth d; the iterative version uses an explicit stack.

Follow-up an interviewer may ask. How would you flatten only one or two levels? (Pass a depth to your function, or use flat(2).)

Problem 15: Rotate an Array

Question. Rotate an array to the right by k places: the last k items move to the front.

Examples.

• [1, 2, 3, 4, 5, 6, 7], k = 3 → [5, 6, 7, 1, 2, 3, 4]

Approach. Use k % n so a large k wraps around and an empty array is handled. Then slice does the job: the last k items followed by the rest. The in-place trick is to reverse the whole array, then reverse the first k items and the remaining ones.

function rotateRight(nums, k) {
  if (nums.length === 0) return [];
  k %= nums.length;
  return k === 0 ? [...nums] : [...nums.slice(-k), ...nums.slice(0, -k)];
}

console.log(rotateRight([1, 2, 3, 4, 5, 6, 7], 3));
console.log(rotateRight([1, 2, 3], 4));
console.log(rotateRight([1, 2, 3], 0));
console.log(rotateRight([], 5));
console.log(rotateRight([9], 100));

Output:

[
  5, 6, 7, 1,
  2, 3, 4
]
[ 3, 1, 2 ]
[ 1, 2, 3 ]
[]
[ 9 ]

Complexity. O(n) time, O(n) space (the in-place reversal approach uses O(1) extra space).

Follow-up an interviewer may ask. Rotate it in place with O(1) extra space. (Three reversals.)