Lesson 4: Programs 16-20: Matrices, Search, Stacks and Words

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 16: Transpose a Matrix

Question. Swap the rows and columns of a matrix (an array of arrays).

Examples.

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

Approach. Element (row, column) moves to (column, row). Build the result by taking, for each column index, the item from every row. map on the first row gives a neat version.

function transpose(matrix) {
  if (matrix.length === 0) return [];
  return matrix[0].map((_, col) => matrix.map((row) => row[col]));
}

const m = [[1, 2, 3], [4, 5, 6]];
console.log(transpose(m));
console.log(transpose([[7]]));
console.log(transpose([]));
console.log(transpose(transpose(m)));

Output:

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

Complexity. O(r x c) time and space for an r x c matrix.

Follow-up an interviewer may ask. Rotate a square matrix 90 degrees clockwise. (Transpose, then reverse each row.)

Problem 17: Binary Search

Question. Given a sorted array, return the position of a target, or -1 if it is not there.

Examples.

• [1, 3, 5, 7, 9], 7 → 3
• [1, 3, 5, 7, 9], 4 → -1

Approach. Look at the middle item. If it is the target you are done; if the target is smaller, discard the right half; otherwise discard the left half. Each step halves the search space. Use Math.floor((low + high) / 2) and the condition low <= high.

function binarySearch(nums, target) {
  let low = 0, high = nums.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

const data = [1, 3, 5, 7, 9];
console.log([1, 7, 9, 4, 0, 10].map((t) => binarySearch(data, t)));
console.log(binarySearch([], 3), binarySearch([5], 5));

Output:

[ 0, 3, 4, -1, -1, -1 ]
-1 0

Complexity. O(log n) time, O(1) space. (The array must already be sorted.)

Follow-up an interviewer may ask. How would you find the first occurrence in an array with duplicates? (Keep searching left after a match.) Why does sort() need a compare function for numbers? (It sorts as text by default.)

Problem 18: Valid Parentheses

Question. Given a string of brackets ()[]{}, return true if every opening bracket is closed by the right kind, in the right order.

Examples.

• "()[]{}" → true
• "(]" → false
• "([)]" → false

Approach. Use a stack (an array with push and pop). Push each opening bracket. For a closing bracket, the top of the stack must be its matching opener; pop it. At the end the stack must be empty.

function isValid(s) {
  const pairs = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const ch of s) {
    if (Object.values(pairs).includes(ch)) {
      stack.push(ch);
    } else if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}

for (const text of ["()[]{}", "(]", "([)]", "{[]}", "", "((", "))", "a(b)c"]) {
  console.log(JSON.stringify(text), isValid(text));
}

Output:

"()[]{}" true
"(]" false
"([)]" false
"{[]}" true
"" true
"((" false
"))" false
"a(b)c" true

Complexity. O(n) time, O(n) space for the stack.

Follow-up an interviewer may ask. How would you find the length of the longest valid substring? (Track indexes on the stack.)

Problem 19: Merge Two Sorted Arrays

Question. Merge two sorted arrays into one sorted array.

Examples.

• [1, 4, 7], [2, 3, 9] → [1, 2, 3, 4, 7, 9]

Approach. Keep one pointer in each array. Repeatedly take the smaller of the two current items, then move that pointer. When one array runs out, add what is left of the other. This is the merge step of merge sort. (Concatenating and sorting also works but costs O(n log n) and ignores that the inputs are sorted.)

function mergeSorted(a, b) {
  let i = 0, j = 0;
  const result = [];
  while (i < a.length && j < b.length) {
    result.push(a[i] <= b[j] ? a[i++] : b[j++]);
  }
  return result.concat(a.slice(i), b.slice(j));
}

console.log(mergeSorted([1, 4, 7], [2, 3, 9]));
console.log(mergeSorted([], [1, 2]));
console.log(mergeSorted([1, 1], [1]));
console.log([...[1, 4, 7], ...[2, 3, 9]].sort((x, y) => x - y));

Output:

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

Complexity. O(m + n) time and O(m + n) space.

Follow-up an interviewer may ask. How would you merge k sorted arrays? (A min-heap holding the next item of each array: O(N log k).)

Problem 20: Word Frequency: The Most Common Words

Question. Given a text, return the n most frequent words, ignoring case and punctuation.

Examples.

• "the cat and the hat and the bat", n = 2 → [['the', 3], ['and', 2]]

Approach. Lower-case the text, pull out the words with a regular expression, count them in a Map, then sort the entries by count (largest first) and take n. sort is stable, so words with equal counts keep the order in which they first appeared.

function topWords(text, n) {
  const words = text.toLowerCase().match(/[a-z']+/g) ?? [];
  const counts = new Map();
  for (const w of words) counts.set(w, (counts.get(w) ?? 0) + 1);
  return [...counts].sort((a, b) => b[1] - a[1]).slice(0, n);
}

const text = "The cat and the hat. And the bat! It's the cat's hat.";
console.log(topWords(text, 3));
console.log(topWords("", 3));
console.log(topWords("One fish, two fish.", 5));

Output:

[ [ 'the', 4 ], [ 'and', 2 ], [ 'hat', 2 ] ]
[]
[ [ 'fish', 2 ], [ 'one', 1 ], [ 'two', 1 ] ]

Complexity. O(n) time to count; the sort adds O(k log k) for k distinct words.

Follow-up an interviewer may ask. How would you do it for a file too big for memory? (Count in chunks and merge, or use a streaming approximate counter.)

What to do next

• Re-solve each problem tomorrow without looking, then explain it out loud.
• Write a few extra test cases for each: empty input, one item, duplicates, very large values.
• Practise related problems on sites such as LeetCode and HackerRank, starting with the "easy" ones in each topic.
• Compare with the Python: 20 Interview Programs course: the same ideas, a different language.

Good luck with your interviews. Understanding the pattern behind each problem matters more than memorising code.