Problem

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.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5

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 <= 10^5
  • The input is generated such that events is sorted in increasing order of timei.

Solution

Method 1: Track Maximum Push Time

Intuition

For each event, compute the time taken to push the button (difference from previous event). Track the maximum time and the smallest index with that time.

Approach

  • For the first event, the time is its own time value.
  • For subsequent events, the time is the difference from the previous event’s time.
  • Track the maximum time and the smallest index with that time.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <vector>
using namespace std;
class Solution {
public:
    int buttonWithLongestPushTime(vector<vector<int>>& events) {
        int maxTime = events[0][1], res = events[0][0];
        for (int i = 1; i < events.size(); ++i) {
            int t = events[i][1] - events[i-1][1];
            if (t > maxTime || (t == maxTime && events[i][0] < res)) {
                maxTime = t;
                res = events[i][0];
            }
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func buttonWithLongestPushTime(events [][]int) int {
    maxTime, res := events[0][1], events[0][0]
    for i := 1; i < len(events); i++ {
        t := events[i][1] - events[i-1][1]
        if t > maxTime || (t == maxTime && events[i][0] < res) {
            maxTime = t
            res = events[i][0]
        }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int buttonWithLongestPushTime(int[][] events) {
        int maxTime = events[0][1];
        int res = events[0][0];
        for (int i = 1; i < events.length; i++) {
            int t = events[i][1] - events[i-1][1];
            if (t > maxTime || (t == maxTime && events[i][0] < res)) {
                maxTime = t;
                res = events[i][0];
            }
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun buttonWithLongestPushTime(events: Array<IntArray>): Int {
        var maxTime = events[0][1]
        var res = events[0][0]
        for (i in 1 until events.size) {
            val t = events[i][1] - events[i-1][1]
            if (t > maxTime || (t == maxTime && events[i][0] < res)) {
                maxTime = t
                res = events[i][0]
            }
        }
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def buttonWithLongestPushTime(self, events):
        max_time = events[0][1]
        res = events[0][0]
        for i in range(1, len(events)):
            t = events[i][1] - events[i-1][1]
            if t > max_time or (t == max_time and events[i][0] < res):
                max_time = t
                res = events[i][0]
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn button_with_longest_push_time(events: Vec<Vec<i32>>) -> i32 {
        let mut max_time = events[0][1];
        let mut res = events[0][0];
        for i in 1..events.len() {
            let t = events[i][1] - events[i-1][1];
            if t > max_time || (t == max_time && events[i][0] < res) {
                max_time = t;
                res = events[i][0];
            }
        }
        res
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)