Loading page…
Practice problem · easy
Your payments app has a small tile game on its rewards page. A row of cells holds reward tiles. Each tile shows a number of points, and a blank cell holds nothing.
When a player swipes left, every tile slides left over the blanks. Two equal tiles that meet merge into one tile with the sum of their points. A tile that was made by a merge cannot merge again in the same swipe. You are asked to compute the row after one swipe.
Write slide_left(row).
row[i] is the points on the tile in cell i. A 0 is a blank cell.0) at the right.row in place with O(1) extra memory, then return it. The judge checks only the row you return.Input: row = [2, 0, 2, 4, 4, 4]
Output: [4, 8, 4, 0, 0, 0]The read pointer read visits every cell. The write pointer write marks where the next tile goes. The flag can_merge is true when the last kept tile was copied, so it may still merge.
| read | row[read] | What happens | write after | can_merge after | Tiles kept so far |
|---|---|---|---|---|---|
| 0 | 2 | no tile to merge with: write it | 1 | true | 2 |
| 1 | 0 | blank: skip | 1 | true | 2 |
| 2 | 2 | equal to the last kept tile: merge, 2 + 2 = 4 | 1 | false | 4 |
| 3 | 4 | the last tile is merged: write it | 2 | true | 4, 4 |
| 4 | 4 | equal to the last kept tile: merge, 4 + 4 = 8 | 2 | false | 4, 8 |
| 5 | 4 | the last tile is merged: write it | 3 | true | 4, 8, 4 |
Three tiles are kept. The cells from write to the end become blanks.
Input: row = [2, 2, 2, 2]
Output: [4, 4, 0, 0]The first two tiles merge into 4. The next two merge into another 4. The two 4s do not merge: each one was made by a merge.
Input: row = [4, 4, 8]
Output: [8, 8, 0]The two 4s merge into an 8. That new 8 does not merge with the 8 after it.
1 ≤ row.length ≤ 100,000 (cells in one row)0 ≤ row[i] ≤ 1,000,000 (points on a tile, 0 for a blank)Playing the swipe like the animation moves each tile one cell per pass. A tile may travel about n cells, and each pass checks n cells. That is about n × n checks: 10^10 at n = 100,000, over 100 seconds at 10^8 a second. Aim for one pass over the row.
A merged tile holds at most 2 × 1,000,000, because a merged tile never merges again. That fits in a 32-bit integer.
slide_left · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.