README_EN.md

comments	difficulty	edit_url	rating	source	tags
true	Easy	https://github.com/doocs/leetcode/edit/main/solution/3300-3399/3386.Button%20with%20Longest%20Push%20Time/README_EN.md	1255	Weekly Contest 428 Q1	Array

3386. Button with Longest Push Time

中文文档

Description

You are given a 2D array events which represents a sequence of events where a child pushes a series of buttons on a keyboard.

Each events[i] = [indexi, timei] indicates that the button at index indexi was pressed at time timei.

• The array is sorted in increasing order of time.
• The time taken to press a button is the difference in time between consecutive button presses. The time for the first button is simply the time at which it was pressed.

Return the index of the button that took the longest time to push. If multiple buttons have the same longest time, return the button with the smallest index.

 

Example 1:

Input: events = [[1,2],[2,5],[3,9],[1,15]]

Output: 1

Explanation:

• Button with index 1 is pressed at time 2.
• Button with index 2 is pressed at time 5, so it took 5 - 2 = 3 units of time.
• Button with index 3 is pressed at time 9, so it took 9 - 5 = 4 units of time.
• Button with index 1 is pressed again at time 15, so it took 15 - 9 = 6 units of time.

Example 2:

Input: events = [[10,5],[1,7]]

Output: 10

Explanation:

• Button with index 10 is pressed at time 5.
• Button with index 1 is pressed at time 7, so it took 7 - 5 = 2 units of time.

 

Constraints:

• 1 <= events.length <= 1000
• events[i] == [indexi, timei]
• 1 <= indexi, timei <= 105
• The input is generated such that events is sorted in increasing order of timei.

Solutions

Solution 1: Single Pass

We define two variables $\textit{ans}$ and $t$, representing the index of the button with the longest press time and the press time, respectively.

Next, we start traversing the array $\textit{events}$ from index $k = 1$. For each $k$, we calculate the press time of the current button $d = t2 - t1$, where $t2$ is the press time of the current button and $t1$ is the press time of the previous button. If $d > t$ or $d = t$ and the index $i$ of the current button is less than $\textit{ans}$, we update $\textit{ans} = i$ and $t = d$.

Finally, we return $\textit{ans}$.

The time complexity is $O(n)$, where $n$ is the length of the array $\textit{events}$. The space complexity is $O(1)$.

Python3

class Solution:
    def buttonWithLongestTime(self, events: List[List[int]]) -> int:
        ans, t = events[0]
        for (_, t1), (i, t2) in pairwise(events):
            d = t2 - t1
            if d > t or (d == t and i < ans):
                ans, t = i, d
        return ans

Java

class Solution {
    public int buttonWithLongestTime(int[][] events) {
        int ans = events[0][0], t = events[0][1];
        for (int k = 1; k < events.length; ++k) {
            int i = events[k][0], t2 = events[k][1], t1 = events[k - 1][1];
            int d = t2 - t1;
            if (d > t || (d == t && ans > i)) {
                ans = i;
                t = d;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int buttonWithLongestTime(vector<vector<int>>& events) {
        int ans = events[0][0], t = events[0][1];
        for (int k = 1; k < events.size(); ++k) {
            int i = events[k][0], t2 = events[k][1], t1 = events[k - 1][1];
            int d = t2 - t1;
            if (d > t || (d == t && ans > i)) {
                ans = i;
                t = d;
            }
        }
        return ans;
    }
};

Go

func buttonWithLongestTime(events [][]int) int {
	ans, t := events[0][0], events[0][1]
	for k, e := range events[1:] {
		i, t2, t1 := e[0], e[1], events[k][1]
		d := t2 - t1
		if d > t || (d == t && i < ans) {
			ans, t = i, d
		}
	}
	return ans
}

TypeScript

function buttonWithLongestTime(events: number[][]): number {
    let [ans, t] = events[0];
    for (let k = 1; k < events.length; ++k) {
        const [i, t2] = events[k];
        const d = t2 - events[k - 1][1];
        if (d > t || (d === t && i < ans)) {
            ans = i;
            t = d;
        }
    }
    return ans;
}