FastPrep
Problem · Array

Rearrange Songs by Author

Learn this problem
● MediumZomato / Eternal logoZomato / EternalFULLTIMEOA

Problem statement

You are given a 2D string array songs. Each row is [author, song], and every row identifies one distinct song record.

Rearrange all records so that no two consecutive records have the same author. At each position, choose the eligible author with the largest number of unplaced songs. If eligible authors have equal remaining counts, choose the lexicographically smaller author. Within one author, emit songs in lexicographic order.

Return the complete rearranged 2D array. If no valid complete rearrangement exists, return an empty 2D array.

Function

rearrangeSongs(songs: String[][]) → String[][]

Examples

Example 1

songs = [["A","alpha"],["A","amber"],["B","beta"],["C","coda"]]return = [["A","alpha"],["B","beta"],["A","amber"],["C","coda"]]

Author A starts with two songs, so it is selected first. Authors B and C then tie with one song; B wins lexicographically. The remaining records alternate without equal adjacent authors.

Example 2

songs = [["A","one"],["A","two"],["A","three"],["B","solo"]]return = []

After placing two records from author A around the only B record, two A records would still need to be adjacent. A complete valid arrangement is impossible.

Constraints

  • 1 <= songs.length <= 200000
  • songs[i].length == 2
  • 1 <= songs[i][0].length, songs[i][1].length <= 100
  • Every row is a distinct [author, song] pair.

More Zomato / Eternal problems

drafts saved locally
public String[][] rearrangeSongs(String[][] songs) {
  // write your code here
}
songs[["A","alpha"],["A","amber"],["B","beta"],["C","coda"]]
expected[["A", "alpha", "B", "beta", "A", "amber", "C", "coda"]]
checking account