406. Ticket Line Time
At a school fair every visitor stands in one line at the ticket booth. tickets[i] is how many tickets the visitor at position i (counting from 0 at the front) wants. The clerk serves the visitor at the front for exactly one second and hands over a single ticket; if that visitor still wants more, they walk to the back of the line, otherwise they leave.
Given tickets and the position k of one particular visitor, return how many seconds pass until visitor k has received every ticket they wanted. Simulating the line works, but there is a direct formula that needs only one pass over the array.
Example 1
- Input:
- tickets = [4,2,5,3], k = 1
- Output:
- 6
- Explanation:
Visitor 1 needs 2 tickets, so they are served twice. In that time visitor 0 is served twice, and visitors 2 and 3, who stand behind, are served once each: 2 + 2 + 1 + 1 = 6 seconds.
Example 2
- Input:
- tickets = [2,6,3], k = 2
- Output:
- 8
- Explanation:
Visitor 2 needs 3 tickets. Visitor 0 can only be served 2 times, visitor 1 gets 3 turns, and visitor 2 gets 3: 2 + 3 + 3 = 8 seconds.
Constraints
1 ≤ tickets.length ≤ 105
1 ≤ tickets[i] ≤ 104
0 ≤ k < tickets.length
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)