Ctrl K

Swap Columns So Both Rows Climb

Hard
You are given two rows of numbers of the same length, top and bottom. Think of them as a two-row table where column i is the pair top[i], bottom[i]. In one move you pick a column and swap its upper and lower numbers. Return the smallest number of moves after which both rows are strictly increasing. It is guaranteed that this can be done.
Example 1
top=[1, 6, 3, 8], bottom=[2, 2, 7, 9] → 1

Swap column 1: the top row becomes [1, 2, 3, 8] and the bottom row [2, 6, 7, 9], both strictly increasing after a single swap.

Example 2
top=[1, 2, 3], bottom=[4, 5, 6] → 0

Both rows are already strictly increasing.

Example 3
top=[5, 2, 7, 4], bottom=[1, 6, 3, 8] → 2
Constraints
  • 2 ≤ len(top) = len(bottom) ≤ 10⁵
  • 0 ≤ top[i], bottom[i] ≤ 2·10⁵
  • Making both rows increasing is possible
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsWater Between Walls HardBiggest Solid Panel Block HardProfit From Two Trades HardEvery Way to Space the Words HardCrossing the Cave Hard
loading Python…
Input
top=[1, 6, 3, 8], bottom=[2, 2, 7, 9]
Expected
1

Run checks the first 3 tests in your browser. Submit checks all 32 tests on the server, hidden ones included.