Two-Heat Results Board

Easytwo pointersAlso known as Merge Sorted Array

A swimming gala runs the 50 m race in two heats. The results board already shows heat 1, fastest time first, and below it there are exactly enough blank rows (shown as 0) for every swimmer in heat 2.

Heat 2's times arrive on a separate sheet, also sorted fastest first. The board has no spare rows for scratch work, so you have to slot heat 2 into the board itself and end up with one combined ranking.

Your task

Write mergeHeats(board, filled, heat2). The first filled entries of board are heat 1's times in non-decreasing order. The remaining heat2.length entries are 0 placeholders. heat2 is also sorted in non-decreasing order.

Change board in place so it holds all the times sorted in non-decreasing order. Return nothing. Do not build a new list and copy it back: use only O(1) extra space.

mergeHeats(board: int[], filled: int, heat2: int[]) → void (changes board in place)

Examples

Example 1

Input

board = [52, 58, 71, 0, 0]
filled = 3
heat2 = [55, 64]

Output

[52, 55, 58, 64, 71]

Why

Heat 1 is 52, 58, 71 and heat 2 is 55, 64. Together, fastest first: 52, 55, 58, 64, 71. The two blank rows are gone.

Example 2

Input

board = [40, 0, 0, 0]
filled = 1
heat2 = [33, 47, 61]

Output

[33, 40, 47, 61]

Why

Heat 2's 33 beats everyone, so it must end up in row 0, where heat 1's 40 currently sits. Writing from the front would destroy the 40 before it is moved.

Constraints

0 ≤ filled, heat2.length ≤ 1,000
board.length = filled + heat2.length
1 ≤ every real time ≤ 1,000,000 (hundredths of a second)

Start with brute force

Copy heat 2 into the blank rows, then sort the whole board. Or merge into a fresh list and copy it back.

The first costs O((m + n) log(m + n)) and throws away the fact that both heats were already sorted. The second runs in linear time but needs a second board, which the task rules out. The backward merge gets linear time and no extra list.

Hints

0 of 4 shown

Hint 1
In the second example, try filling the board from the top. What happens to 40 when 33 is written into row 0?
Hint 2
Writing from the front overwrites heat 1 times you still need. Where on the board is there free space you can write into without losing anything?
Hint 3
The blanks are at the end. Fill the board from the last row backwards, placing the slowest remaining time each step. Which two times are candidates for the slowest?
Hint 4
Keep three indexes: i on heat 1's last real time, j on heat 2's last time, and k on the board's last row. Write the larger of board[i] and heat2[j] at k, step that pointer and k back. Stop when heat 2 is used up; heat 1's leftovers are already in place.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

The free space is at the bottom of the board, so fill it from the bottom. The slowest time overall must be the last of heat 1 or the last of heat 2, so each step compares just those two.

Trace [52, 58, 71, 0, 0], heat 2 [55, 64]:

i on 71, j on 64, k = 4. 71 is slower. Board row 4 = 71. Board: [52, 58, 71, 0, 71].
i on 58, j on 64, k = 3. 64 is slower. Row 3 = 64. Board: [52, 58, 71, 64, 71].
i on 58, j on 55, k = 2. 58 is slower. Row 2 = 58. Board: [52, 58, 58, 64, 71].
i on 52, j on 55, k = 1. 55 is slower. Row 1 = 55. Board: [52, 55, 58, 64, 71]. Heat 2 is used up, so stop.

Writing never destroys a time you still need: k is always ahead of i, and the gap between them is exactly the number of heat 2 times still to place (k = i + j + 1). And when heat 2 runs out, the remaining heat 1 times are already sorted and in place, so there is nothing to copy. The reverse case is not free: if heat 1 runs out first, the loop keeps copying heat 2, which is why the loop runs on j.

Reference solution

function mergeHeats(board, filled, heat2) {
  let i = filled - 1;       // last real heat 1 time
  let j = heat2.length - 1; // last heat 2 time
  let k = board.length - 1; // next row to fill, from the bottom
  while (j >= 0) {
    if (i >= 0 && board[i] > heat2[j]) {
      board[k--] = board[i--]; // heat 1 has the slowest remaining time
    } else {
      board[k--] = heat2[j--];
    }
  }
  // any heat 1 times left are already in their final rows
}

def merge_heats(board, filled, heat2):
    i = filled - 1       # last real heat 1 time
    j = len(heat2) - 1   # last heat 2 time
    k = len(board) - 1   # next row to fill, from the bottom
    while j >= 0:
        if i >= 0 and board[i] > heat2[j]:
            board[k] = board[i]  # heat 1 has the slowest remaining time
            i -= 1
        else:
            board[k] = heat2[j]
            j -= 1
        k -= 1
    # any heat 1 times left are already in their final rows

TimeO(m + n)Every step places one time into its final row.

SpaceO(1)Three indexes; the board itself holds the result.

Learn the idea: Merge Sort Two Pointers

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code