88. Shared Favourite
Two friends each ranked their favourite street-food stalls from most to least preferred. The array a holds the first friend's ranking and b holds the second friend's, where position 0 is the top choice. Within one list every stall name is distinct, and at least one stall appears in both lists.
For every stall that appears in both lists, add its position in a to its position in b. Return all shared stalls whose position sum is the smallest among shared stalls. The order of the returned names does not matter.
Example 1
- Input:
- a = ["tacos","pizza","sushi","ramen"]b = ["ramen","sushi","burger"]
- Output:
- ["ramen","sushi"]
- Explanation:
Sushi has index sum 2+1=3 and ramen has 3+0=3; both are the smallest, so both are returned in any order.
Example 2
- Input:
- a = ["idli","dosa","vada"], b = ["dosa","upma"]
- Output:
- ["dosa"]
- Explanation:
Only dosa is shared, with index sum 1+0=1.
Constraints
1 ≤ a.length, b.length ≤ 1000
1 ≤ a[i].length, b[i].length ≤ 30; names consist of English letters and digits
Names within each list are distinct; at least one name is shared.
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
Expected complexity
- Time
- O(n + m)
- Space
- O(n)